如何判断链表有环

给定一个链表，判断链表中是否有环。

循环判断

从头节点开始，依次遍历单链表中的每一个节点。没遍历一个新节点，就从头检查新节点之前的所有节点，查看是否相同。若存在相同节点证明链表是有环的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        int total = 2;
        ListNode cur = head.next;
        while (cur != null) {
            int start = 1;
            ListNode node = head;
            while (node != cur) {
                node = node.next;
                start++;
            }
            if (start != total) return true;
            total++;
            cur = cur.next;
        }
        return false;
    }
}

该算法遍历一遍的同时，内部也在从头遍历一次，所以时间复杂度为O(n^2)

没有创造新的内存空间，空间复杂度为O(1)

Set集合

创建一个Set集合，遍历链表并将节点加入Set集合，当出现重复的元素，即加入Set集合失败即代表有环出现。

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (!set.add(head)) return true;
            head = head.next;
        }
        return false;
    }
}

该算法是遍历一遍链表，所以时间复杂度为O(n)

将所有节点加入Set集合存储，空间复杂度也为O(n)

双指针

使用两个指针，一个每次前进两个，一个每次前进一个，若是出现两个指针指向一个节点，代表链表有环。因为快指针提前入环，总会追上慢指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;
    }
}

只用循环一次链表，所以时间复杂度为O(n)

不用创建额外的空间，所以空间复杂度为O(1)

求出环的长度

快慢节点重合的时候，在继续前进并记录前进的次数，下次重合，就是快指针（速度是慢指针的两倍）比慢指针多走了一圈，可以理解为前进的次数就是环的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public ListNode getCycleLength(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        int length = 1;
        fast = fast.next.next;
        slow = slow.next;
        while (fast != slow) {
			fast = fast.next.next;
            slow = slow.next;
            length++;
        }
        return length;
    }
}

判断入环点

假设链表头节点到入环点的距离是D，从入环点到两个指针首次相遇点为S1，从两个指针首次相遇点到入环点的距离为S2。

设慢指针的移动速度为一个节点，快指针的移动速度为两个节点。

故两个指针首次相遇时，两个指针所走的距离如下

慢指针行走的距离为D + S1

快指针的速度是慢指针的两倍，所以相当于比慢指针多走了N圈，故行走的距离为D + S1 + N * (S1 + S2)

因为快指针的速度是慢指针的两倍，所以快指针的行走距离应该为慢指针的两倍，所以有

2(D + S1) = D + S1 + N * (S1 + S2)

经过整理可以得到

D = (N - 1)(S1 + S2) + S2

也就是说，链表头节点到入环点的的距离相当于从首次相遇点绕环N - 1圈后再回到入环点的距离。

故从头节点出发，与首次相遇点出发，两者均以一个节点的速度，两者相遇点即为入环点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) {
                fast = head;
                while(fast != slow) {
                   fast = fast.next;
                   slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}

最小栈的实现

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

  • push(x) —— 将元素 x 推入栈中。
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。

这里需要使用到辅助栈来实现，将每次最小的元素都放到辅助栈中，若即入栈的元素比最小元素小，辅助栈中就放入该最小元素，否则就放入之前最小的元素。当栈出栈后，辅助栈也跟着出栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class MinStack {
    Stack<Integer> min;
    Stack<Integer> stack;
    public MinStack() {
        stack = new Stack<>();
        min = new Stack<>();
    }
    
    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push(val);
            min.push(val);
        } else {
            stack.push(val);
            if (val < min.peek()) {
                min.push(val);
            } else {
                min.push(min.peek());
            }
        }
    }
    
    public void pop() {
        if (stack.isEmpty()) {}
        stack.pop();
        min.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

如何求出最大公约数

求出两个正整数的最大公约数。

枚举

从较小整数的一半开始遍历到2，首次出现了两个正整数都整除的数，则该数就是两个正整数的最大公约数。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int getGreatestCommonDivisor(int a, int b) {
        int max = Math.max(a, b);
        int min = Math.min(a, b);
        if (max % min == 0) {
            return min;
        }
        for (int i =  min / 2; i > 1; i--) {
            if (min % i == 0 && max % i == 0) {
                return i;
            }
        }
        return 1;
    }

时间复杂度为O(min(a, b))

辗转相除法（欧几里得算法）

这个方法基于一个定理：

两个正整数a和b（a > b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。

1
2
3
4
5
6
7
8
public static int getGreatestCommonDivisor(int a, int b) {
    int max = Math.max(a, b);
    int min = Math.min(a, b);
    if (max % min == 0) {
        return min;
    }
    return getGreatestCommonDivisor(max % min, min);
}

时间复杂度近似为O(log(max(a, b))，当两个正整数很大的时候，a % b的计算性能很差。

更相减损术

两个正整数a和b（a > b），它们的最大公约数等于a - b的差值c和较小数b的最大公约数。

1
2
3
4
5
6
7
8
public static int getGreatestCommonDivisor(int a, int b) {
    if (a == b) {
        return a;
    }
    int max = Math.max(a, b);
    int min = Math.min(a, b);
    return getGreatestCommonDivisor(max - min, min);
}

避免了大数取模的计算，但是算法性能不稳定，最坏的时间复杂度为O(max(a, b))

更优算法

  • 当a和b均为偶数时，gcd(a,b) = 2 gcd(a / 2, b / 2) = 2 gcd(a >> 1, b >> 1) = gcd(a >> 1, b >> 1) << 1;
  • 当a为偶数，b为奇数时，gcd(a, b) = gcd(a / 2, b) = gcd(a >> 1, b);
  • 当a为奇数，b为偶数时，gcd(a, b) = gcd(a, b / 2) = gcd(a, b >> 1);
  • 当a和b均为奇数时，先利用更相减损术运算一次，gcd(a, b) = gcd(b, a - b)，此时a - b必是偶数，然后进行上面情况的运算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int getGreatestCommonDivisor(int a, int b) {
    if (a == b) {
        return a;
    }
    if ((a & 1) == 0 && (b & 1) == 0) {
        return getGreatestCommonDivisor(a >> 1, b >> 1) << 1;
    } else if ((a & 1) == 0 && (b & 1) != 0) {
        return getGreatestCommonDivisor(a >> 1, b);
    } else if ((a & 1) != 0 && (b & 1) == 0) {
        return getGreatestCommonDivisor(a, b >> 1);
    } else {
        int max = Math.max(a, b);
        int min = Math.min(a, b);
        return getGreatestCommonDivisor(max - min, min);
    }
}

进行简化之后为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int getGreatestCommonDivisor(int a, int b) {
    if (a == b) {
        return a;
    }
    if ((a & 1) == 0 && (b & 1) == 0) {
        return getGreatestCommonDivisor(a >> 1, b >> 1) << 1;
    } else if ((a & 1) == 0) {
        return getGreatestCommonDivisor(a >> 1, b);
    } else if ((b & 1) == 0) {
        return getGreatestCommonDivisor(a, b >> 1);
    } else {
        int max = Math.max(a, b);
        int min = Math.min(a, b);
        return getGreatestCommonDivisor(max - min, min);
    }
}

这是更相减损法与位运算的结合方法，算法性能稳定，而且使用了位运算，时间复杂度为O(log(max(a, b)))

判断一个数是否为2的整数次幂

判断一个正整数是否为2的整数次幂

枚举

计算出2的整数次幂，依次递增，若是出现了大于该数的2次幂（并没有等于的），就证明该数不是2的整数次幂。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean isPowerOfTwo(int n) {
        int num = 1;
        while (num <= n) {
            if (num == n) return true;
            num = num << 1;
        }
        return false;
    }
}

算法的时间复杂度为O(logn)。

n & (n - 1) == 0

每一个2的整数次幂转换为二进制，都是1开头后面都是0的数串。

将该整数次幂减一，就得到二进制全为1的数串。

这两个数取按位与运算，就会出现每一位数都不一样，所以结果为0。

所以不为0的就不是2的整数次幂了。

1
2
3
4
5
class Solution {
    public boolean isPowerOfTwo(int n) {
        return (n & n - 1) == 0;
    }
}

n & -n == n

n & -n可以得到最低位的1的位置，即最低位为1其余全是0的数串，如果是2的整数次幂的话，那么该数串其实表示的就是本身。

1
2
3
4
5
class Solution {
    public boolean isPowerOfTwo(int n) {
        return (n & -n) == n;
    }
}

无序数组排序后的最大相邻差

有一个无序整数型数组，如何求出该数组排序后的任意两个相邻元素的最大差值？

排序后求最大差值

1
2
3
4
5
6
7
8
9
10
11
public static int getMaxSortedDistance(int[] array) {
    Arrays.sort(array);
    int max = -1;
    for (int i = 1; i < array.length; i++) {
        int temp = array[i] - array[i - 1];
        if (temp > max) {
            max = temp;
        }
    }
    return max;
}

将数组进行快速排序O(nlogn)，然后进行遍历O(n)，所以总的时间复杂度为O(nlogn)

空间复杂度就是该数组O(n)

计数排序

使用计数排序，找出新数组最多连续出现0的次数加1，就是最大相邻差了。

当数组的数差值不是很大的情况下，效率很高，但是差值很大的情况，数组的长度会很大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public static int getMaxSortedDistance(int[] array) {
    // 求出数组的最大值和最小值
    int max = array[0];
    int min = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
        if (array[i] < min) {
            min = array[i];
        }
    }
    int d = max - min;
    // 最大值和最小值相等，证明数组的所有数相等
    if (d == 0) {
        return 0;
    }
    // 计数排序
    int[] arr = new int[d + 1];
    for (int i : array) {
        arr[i - min]++;
    }
    int maxDistance = 0;
    
    // 寻找最长连续的0
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == 0) {
            int temp = i;
            while (arr[temp] == 0) {
                temp++;
            }
            if (temp - i > maxDistance) {
                maxDistance = temp - i;
            }
        }
    }
    return maxDistance + 1;
}

桶排序

记录桶内的最大和最小值，统计出每一个桶的最大值，和这个桶右侧非空桶的最小值的差，数值最大的差即为题目所求，故时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public static int getMaxSortedDistance(int[] array) {
    // 求出数组的最大值和最小值
    int max = array[0];
    int min = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
        if (array[i] < min) {
            min = array[i];
        }
    }
    int d = max - min;
    // 最大值和最小值相等，证明数组的所有数相等
    if (d == 0) {
        return 0;
    }

    // 初始化桶
    int bucketNum = array.length;
    Bucket[] buckets = new Bucket[bucketNum];
    Arrays.fill(buckets,new Bucket());

    // 遍历原始数组，确定每个桶的最大值和最小值
    for (int i : array) {
        int index = ((i - min) * (bucketNum - 1) / d);
        if (buckets[index].min == null || buckets[index].min > i) {
            buckets[index].min = i;
        }
        if (buckets[index].max == null || buckets[index].max < i) {
            buckets[index].max = i;
        }
    }

    // 遍历桶，找到最大差值
    int leftMax = buckets[0].max;
    int maxDistance = 0;
    for (int i = 1; i < buckets.length; i++) {
        if (buckets[i].min == null) {
            continue;
        }
        if (buckets[i].min - leftMax > maxDistance) {
            maxDistance = buckets[i].min - leftMax;
        }
        leftMax = buckets[i].max;
    }
    return maxDistance;
}

private static class Bucket {
    Integer min;
    Integer max;
}

用栈实现队列

用栈来模拟一个队列，要求实现队列的两个基本操作：入队和出队。

使用一个栈明显是不能实现队列的，所以需要一个辅助栈。设这两个栈为a和b。

a栈用来存储入队的元素，入队的元素直接压入a栈就好。

b栈用来存储出队的元素，出队的元素就直接推出b栈就好。

当b栈是空的，就将a栈的所有元素出栈压入a栈，这样出栈的顺序就相反了，即符合先进先出了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class CQueue {

    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        if(!stack2.isEmpty()) {
            return stack2.pop();
        }
        if(stack1.isEmpty()) {
            return -1;
        }
        while(!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
    
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

删除k个数字后的最小值

给出一个整数，从该整数中去掉k个数字，要求剩下的数字形成的新整数尽可能小。应该如何选取被去掉的数字？

从左往右，第一位大于它右边的数，将该数删了就会让整个数值降低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static String removeKDigits(String num, int k) {
    int newLength = num.length() - k;
    char[] stack = new char[num.length()];
    int top = 0;
    for (int i = 0; i < num.length(); i++) {
        char c = num.charAt(i);
        while (top > 0 && stack[top - 1] > c && k > 0) {
            top -= 1;
            k -= 1;
        }
        stack[top++] = c;
    }
    int offset = 0;
    while (offset < newLength && stack[offset] == '0') {
        offset++;
    }
    return offset == newLength ? "0" : new String(stack,offset,newLength - offset);
}

如何实现大整数相加

给出两个很大的正整数，要求实现程序求出两个整数之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public static String bigNumberSum(String bigNumberA, String bigNumberB) {
    int maxLen = Math.max(bigNumberA.length(), bigNumberB.length()) + 1;
    // 将两个大数逆序存储到数组中
    int[] arrA = new int[maxLen]; 
    for (int i = 0; i < bigNumberA.length(); i++) {
        arrA[i] = bigNumberA.charAt(bigNumberA.length() - i - 1) - '0';
    }
    int[] arrB = new int[maxLen];
    for (int i = 0; i < bigNumberB.length(); i++) {
        arrB[i] = bigNumberB.charAt(bigNumberB.length() - i - 1) - '0';
    }
    // 进行运算
    int[] res = new int[maxLen];
    for (int i = 0; i < res.length; i++) {
        int temp = res[i];
        temp += arrA[i] + arrB[i];
        if (temp >= 10) {
            temp -= 10;
            res[i + 1]++;
        }
        res[i] = temp;
    }
    
    // 将结果逆序
    StringBuilder str = new StringBuilder();
    boolean findFirst = false;
    for (int i = res.length - 1; i >= 0; i--) {
        if (!findFirst) {
            if (res[i] == 0) {
                continue;
            }
            findFirst = true;
        }
        str.append(res[i]);
    }
    return str.toString();
}

金矿问题

​ 很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不同。例如又得金矿储量是500kg黄金，需要5个工人来挖掘；有的金矿储量是200kg黄金，需要3个工人来挖掘……

​ 如果参与挖矿的工人的总数是10.每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。要用程序求出，要想得到尽可能多的黄金，应该选取挖取那几座金矿？

这题就是一道背包问题，根据题意可知这是01背包的问题，有两种状态转移的情况，选或者是不选。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
 * @param w 工人数量
 * @param p 金矿开采所需的工人数量
 * @param g 金矿储量
 */
public static int getBestGoldMining(int w, int[] p, int[] g) {
    int[] res = new int[w + 1];
    for (int i = 1; i <= g.length; i++) {
        for (int j = w; j >= 1; j--) {
            if (j >= p[i - 1]) {
                res[j] = Math.max(res[j],res[j - p[i - 1]] + g[i - 1]);
            }
        }
    }
    return res[w];
}

寻找缺少的整数

在一个无序数组里有99个不重复的正整数，范围从1到100，唯独缺少1个1~100中的整数。如何找出整个缺少的整数。

哈希表

创建一个哈希表，将1到100这100个数全部存入key中，遍历整个数组，将存在的key都删掉，剩下的key就是缺少的整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int getBestGoldMining(int[] arr) {
    Map<Integer, Integer> map = new HashMap<>(100);
    for (int i = 1; i <= 100; i++) {
        map.put(i,i);
    }
    for (int i : arr) {
        map.remove(i);
    }
    int res = 0;
    for (int key : map.keySet()) {
      res = key;  
    }
    return res;
}

先排序后寻找

将数组进行排序，然后逐个寻找。

1
2
3
4
5
6
7
8
9
10
11
12
public static int getBestGoldMining(int[] arr) {
    Arrays.sort(arr);
    if (arr[0] != 1) {
        return 0;
    }
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i] + 1 != arr[i + 1]) {
            return arr[i] + 1;
        }
    }
    return 100;
}

求和

计算出1~100的和，然后减去数组中元素的和，剩下的就是所缺少的整数了。

1
2
3
4
5
6
7
public static int getBestGoldMining(int[] arr) {
    int res = 5050;
    for (int i : arr) {
        res -= i;
    }
    return res;
}

求只出现一次的数

​ 一个无序数组里有若干个正整数，范围是1~100，其中99个整数都出现了偶数次，只有一个整数出现了奇书次，如何找到这个出现奇数次的整数？

可以将数与数出现的次数当成Key和Value放入哈希表，然后寻找出现次数为1的，和上述哈希表的做法差不多，就不深入了。

这里可以使用异或运算，先了解异或运算的规律。

  1. 两个相同的数异或，结果等于0
  2. 任何数与0异或，结果等于本身
  3. 异或运算符合交换律

故将数组中的数进行异或，偶数次的数异或会变成0，奇数次的数就会留着。

1
2
3
4
5
6
7
public static int getBestGoldMining(int[] arr) {
    int res = 0;
    for (int i : arr) {
        res ^= i;
    }
    return res;
}

LRU（最近最少使用算法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
package com.yww;

import java.util.HashMap;

/**
 * @ClassName LRUCache
 * @author yww
 */
public class LRUCache {

    /**
     * 头节点
     */
    private Node head;
    /**
     * 尾节点
     */
    private Node end;
    /**
     * 缓存的个数
     */
    private int limit;
    /**
     * 哈希表缓存
     */
    private HashMap<String, Node> map;

    class Node {
        public Node pre;
        public Node next;
        public String key;
        public String value;
        Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    public LRUCache(int limit) {
        this.limit = limit;
        map = new HashMap<>();
    }

    /**
     * 通过key获取缓存节点
     */
    public String get(String key) {
        Node node = map.get(key);
        if (node == null) {
            return null;
        }
        refreshNode(node);
        return node.value;
    }

    /**
     * 放入缓存，若key存在，更新value值
     */
    public void put(String key, String value) {
        Node node = map.get(key);
        if (node == null) {
            if (map.size() >= limit) {
                String oldKey = removeNode(head);
                map.remove(oldKey);
            }
            node = new Node(key, value);
            addNode(node);
            map.put(key,node);
        } else {
            node.value = value;
            refreshNode(node);
        }
    }

    /**
     * 通过key删除缓存
     */
    public void remove(String key) {
        Node node = map.get(key);
        removeNode(node);
        map.remove(key);
    }

    /**
     * 刷新被访问的节点
     */
    private void refreshNode(Node node) {
        if (node == end) {
            return;
        }
        removeNode(node);
        addNode(node);
    }

    /**
     * 删除节点
     */
    private String removeNode(Node node) {
        if (node == head && node == end) {
            head = null;
            end = null;
        } else if (node == end) {
            end = end.pre;
            end.next = null;
        } else if (node == head) {
            head = head.next;
            head.pre = null;
        } else {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        return node.key;
    }

    /**
     * 尾部插入节点
     */
    private void addNode(Node node) {
        if (end != null) {
            end.next = node;
            node.pre = end;
            node.next = null;
        }
        end = node;
        if (head == null) {
            head = node;
        }
    }

}