算法
算法

经典算法

位运算

两个相同的数异或结果为0，任何数与0异或结果都是其本身

1
2
3
4
5
6
7
// 判断基偶数
n & 1

// 交换两个数，使用异或
a = a ^ b;
b = a ^ b;
a = a ^ b;

只出现一次的元素

1
2
3
4
5
6
7
8
// 136. 只出现一次的数字：两个相同的数异或结果为0，任何数与0异或结果都是其本身
public int singleNumber(int[] nums) {
    int res = 0;
    for (int i = 0; i< nums.length; i++){
        res ^= nums[i];
    }
    return res;
}

比特位计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 338. 比特位计数
public int[] countBits(int n) {
    int[] res = new int[n];
    res[0] = 0;
    for (int i = 1; i < n; i++) {
        res[i] = res[i & (i - 1)] + 1;
    }
    return res;
}

// 通过奇偶性判断，奇数二进制码中1的个数 等于小于他的偶数+1
public int[] countBits2(int n) {
    int[] res = new int[n];
    res[0] = 0;
    for (int i = 1; i < n; i++) {
        res[i] = (i & 1) == 1 ? res[i - 1] + 1 : res[i >> 1];
    }
    return res;
}

汉明距离

通过X&(X-1)可以清楚低位的1

1
2
3
4
5
6
7
8
// 461. 汉明距离
public int hammingDistance(int x, int y) {
    int count = 0;
    for (int xor = x ^ y; xor != 0; xor &= xor -1 ) {
        count++;
    }
    return count;
}

数组中消失的元素

遍历数组若对应位置的值，将值作为数组下标，找到数组中的元素加上N，最终数组元素中小于等于N的值的数组下标为消失的元素

1
448. 找到所有数组中消失的数字

滑动窗口

给定一个字符串s 、一个字符串t，返回s中涵盖t所有字符的最小子串，若s中不存在涵盖t所有字符的子串，则返回空字符串"" 

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
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> has = new HashMap<>();
public String minWindow(String s, String t) {
    for (int i = 0; i < t.length(); i++) {
        need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
    }
    int l = 0, r = -1;
    int ansLen = Integer.MAX_VALUE, ansL = -1, ansR = -1;
    while (r < s.length()) {
        r++;
        if (r < s.length() && need.containsKey(s.charAt(r))) {
            has.put(s.charAt(r), has.getOrDefault(s.charAt(r), 0) + 1);
        }
        while (check() && l <= r) {
            if (r - l + 1 < ansLen) {
                ansLen = r - l + 1;
                ansL = l;
                ansR = l + ansLen;
            }
            if (need.containsKey(s.charAt(l))) {
                has.put(s.charAt(l), has.getOrDefault(s.charAt(l), 0) - 1);
            }
            l++;
        }
    }
    return ansL == -1 ? "" : s.substring(ansL, ansR);
}

private boolean check() {
    for (Character key : need.keySet()) {
        if (has.getOrDefault(key, 0) < need.get(key)) {
            return false;
        }
    }
    return true;
}

缺失的第一个正数

对于一个长度为N的数组，其中没有出现的最小正整数只能在1到N+1中，若1到N都出现了则答案是N+1，否则答案在1到N中，首先对数组进行遍历，将出现过的且在1到N范围内的数全部打上标记，这里打的标记是将其置为负数，若全部被打过标记了最终返回N + 1，否则返回第一个未出现负数的下标加一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int firstMissingPositive(int[] nums) {
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        if (nums[i] <= 0) { // 将数组中小于0的数走置为N + 1
            nums[i] = len + 1;
        }
    }
    for (int i = 0; i < len; i++) { // 将出现过的数标记为负数
        int num = Math.abs(nums[i]);
        if (num <= len) {
            nums[num - 1] = -Math.abs(nums[num - 1]);
        }
    }
    for (int i = 0; i < len; i++) {
        if (nums[i] > 0) { // 找出第一个不为负数的数的下标，即为未出现的数
            return i + 1;
        }
    }
    return len + 1;
}

回溯法

数字n代表生成括号的对数，生成所有可能的并且有效的括号组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    backtrack(res, new StringBuilder(), 0, 0, n);
    return res;
}
public void backtrack(List<String> res, StringBuilder sb, int open, int close, int max) {
    if (sb.length() == max * 2) {
        res.add(sb.toString());
        return;
    }
    if (open < max) {
        sb.append("(");
        backtrack(res, sb, open + 1, close, max);
        sb.deleteCharAt(sb.length() - 1);
    }
    if (close < open) {
        sb.append(")");
        backtrack(res, sb, open, close + 1, max);
        sb.deleteCharAt(sb.length() - 1);
    }
}

全排列

给定一个不含重复数字的数组nums ，返回其所有可能的全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> markList = new ArrayList<>();
    for (int num : nums) {
        markList.add(num);
    }
    backtrack(nums.length, res, markList, 0);
    return res;
}
public void backtrack(int n, List<List<Integer>> res, List<Integer> markList, int first) {
    if (first == n) {
        res.add(new ArrayList<>(markList));
    }
    for (int i = first; i < n; i++) {
        Collections.swap(markList, first, i);
        backtrack(n, res, markList, first + 1);
        Collections.swap(markList, first, i);
    }
}

素数

暴力算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int countPrimes(int n) {
    int ans = 0;
    for (int i = 2; i < n; ++i) {
        ans += isPrime(i) ? 1 : 0;
    }
    return ans;
}
public boolean isPrime(int x) {
    // i若能被x整除，则x/i肯定能被x整除，因此只需判断i和根号x之中较小的即可
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}
埃氏筛
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int eratosthenes(int n) {
    boolean[] isPrime = new boolean[n]; // false表示是一个素数，true表示合数
    int ans = 0;
    for (int i = 2; i < n; i++) {
        if (!isPrime[i]) {
            ans += 1;
            // 将合数标记为true，j = i * i 从 2 * i 优化而来，系数2会随着遍历递增（j += i，相当于递增了系数2），
            // 每一个合数都会有两个比本身要小的因子(0,1除外)，2 * i必然会遍历到这两个因子，当2递增到大于根号n时，
            // 其实后面的已经无需再判断（或者只需判断后面一段），而2到根号n、实际上在 i 递增的过程中已经计算过了，i实际上就相当于根
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = true;
            }
        }
    }
    return ans;
}

删除有序数组中重复项

1
2
3
4
5
6
7
8
9
10
11
public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

数组的中心索引

1
2
3
4
5
6
7
8
9
10
11
12
13
// 数组中某一个下标，左右两边的元素之和相等，该下标即为中心索引
public int pivotIndex(int[] nums) {
    int sum1 = Arrays.stream(nums).sum();
    int sum2 = 0;
    for (int i = 0; i < nums.length; i++) {
        sum2 += nums[i];
        if (sum1 == sum2) {
            return i;
        }
        sum1 = sum1 - nums[i];
    }
    return -1;
}

平方根

不使用sqrt(x)函数的情况下，得到x的平方根的整数部分

二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
public int binarySearch(int x) {
    int left = 0, right = x, index = -1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (mid * mid <= x) {
            index = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return index;
}
牛顿迭代

假设平方根为i，则i和x/i必然都是x的因子，而x/i必然等于i ，推导出i + x / i = 2 * i，得出i = (i + x / i) / 2，由此得出解法，i可以任选一个值，只要上述公式成立，i必然就是x的平方根，若不成立(i + x / i) / 2得出的值进行递归，直至得出正确解

1
2
3
4
5
6
7
8
9
10
11
12
13
public int newton(int x) {
    if (x == 0) return 0;
    return (int) sqrts(x, x);
}

public double sqrts(double i, int x) {
    double res = (i + x / i) / 2;
    if (res == i) {
        return i;
    } else {
        return sqrts(res, x);
    }
}

三个数的最大乘积

一个整型数组nums ，在数组中找出由三个数字组成的最大乘积，分三种情况，最大的三个正数相乘、最小的两个负数和最大的一个正数相乘

排序
1
2
3
4
5
public int sort(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 3] * nums[n - 2] * nums[n - 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
public int getMaxMin(int[] nums) {
    // 最小的和第二小的
    int min1 = 0, min2 = 0;
    // 最大的、第二大的和第三大的
    int max1 = 0, max2 = 0, max3 = 0;
    for (int x : nums) {
        if (x < min1) {
            min2 = min1;
            min1 = x;
        } else if (x < min2) {
            min2 = x;
        }
        if (x > max1) {
            max3 = max2;
            max2 = max1;
            max1 = x;
        } else if (x > max2) {
            max3 = max2;
            max2 = x;
        } else if (x > max3) {
            max3 = x;
        }
    }
    return Math.max(min1 * min2 * max1, max1 * max2 * max3);
}

两数之和

从数组中找出两个数满足相加之和等于目标数target

暴力解法
1
2
3
4
5
6
7
8
9
10
11
public int[] twoSum(int[] nums, int target) {
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return new int[0];
}
哈希表
1
2
3
4
5
6
7
8
9
10
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; ++i) {
        if (map.containsKey(target - nums[i])) {
            return new int[]{map.get(target - nums[i]), i};
        }
        map.put(nums[i], i);
    }
    return new int[0];
}
二分查找（有序）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] twoSearch(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; ++i) {
        int low = i, high = numbers.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (numbers[mid] == target - numbers[i]) {
                return new int[]{i, mid};
            } else if (numbers[mid] > target - numbers[i]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
    }
    return new int[0];
}
双指针（有序）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] twoPoint(int[] numbers, int target) {
    int low = 0, high = numbers.length - 1;
    while (low < high) {
        int sum = numbers[low] + numbers[high];
        if (sum == target) {
            return new int[]{low + 1, high + 1};
        } else if (sum < target) {
            ++low;
        } else {
            --high;
        }
    }
    return new int[]{-1, -1};
}

排序硬币

总共有n枚硬币，将它们摆成一个阶梯形状，第k行必须正好有k枚硬币，找出可形成完整阶梯行的总行数

迭代
1
2
3
4
5
6
7
8
9
public static int arrangeCoins(int n) {
    for (int i = 1; i <= n; i++) {
        n = n - i;
        if (n <= i) {
            return i;
        }
    }
    return 0;
}
二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int arrangeCoins(int n) {
    int low = 0, high = n;
    while (low <= high) {
        int mid = (high - low) / 2 + low;
        int cost = ((mid + 1) * mid) / 2;
        if (cost == n) {
            return mid;
        } else if (cost > n) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return high;
}
牛顿迭代

使用牛顿迭代求平方根(x + n/x)/2，1 + 2 + 3 + ...+ x = n即x(x+1)/2 = n推导出x = 2n - x

1
2
3
4
5
6
7
8
public static double sqrts(double x, int n) {
    double res = (x + (2 * n - x) / x) / 2;
    if (res == x) {
        return x;
    } else {
        return sqrts(res, n);
    }
}

合并有序数组

合并后排序
1
2
3
4
public void merge(int[] nums1, int m, int[] nums2, int n) {
    System.arraycopy(nums2, 0, nums1, m, n);
    Arrays.sort(nums1);
}
双指针（从前往后）
1
2
3
4
5
6
7
8
9
10
11
12
13
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int[] nums1_copy = new int[m];
    System.arraycopy(nums1, 0, nums1_copy, 0, m); //拷贝数组1
    int p1 = 0; // 指向数组1的拷贝
    int p2 = 0; // 指向数组2
    int p = 0;  // 指向数组1
    // 将数组1当成空数组，比较数组1的拷贝和数组2，将较小的放入空数组
    while ((p1 < m) && (p2 < n))
        nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++];
    // 数组2和数组1不等长，将多出的元素拷贝
    if (p1 < m) System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
    if (p2 < n) System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
}
双指针（从后往前）
1
2
3
4
5
6
7
8
public void merge3(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1;
    int p2 = n - 1;
    int p = m + n - 1;
    while ((p1 >= 0) && (p2 >= 0))
        nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];
    System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
}

子数组最大平均数（滑动窗口）

1
2
3
4
5
6
7
8
9
10
11
12
13
public double findMaxAverage(int[] nums, int k) {
    int sum = 0;
    int n = nums.length;
    for (int i = 0; i < k; i++) {
        sum += nums[i];
    }
    int maxSum = sum;
    for (int i = k; i < n; i++) {
        sum = sum - nums[i - k] + nums[i];
        maxSum = Math.max(maxSum, sum);
    }
    return 1.0 * maxSum / k;
}

找零

每位顾客只买一杯柠檬水，向你付5元、10元或20元，必须给每个顾客正确找零，每一杯柠檬水的售价为5元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean lemonadeChange(int[] bills) {
    int five = 0, ten = 0;
    for (int bill : bills) {
        if (bill == 5) {
            five++;
        } else if (bill == 10) {
            if (five == 0) {
                return false;
            }
            five--;
            ten++;
        } else {
            if (five > 0 && ten > 0) {
                five--;
                ten--;
            } else if (five >= 3) {
                five -= 3;
            } else {
                return false;
            }
        }
    }
    return true;
}

三角形最大周长

1
2
3
4
5
6
7
8
9
public int largestPerimeter(int[] nums) {
    Arrays.sort(nums);
    for (int i = nums.length - 1; i >= 2; --i) {
        if (nums[i - 2] + nums[i - 1] > nums[i]) {
            return nums[i - 2] + nums[i - 1] + nums[i];
        }
    }
    return 0;
}

无重复最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    int maxLen = 0, rightIndex = -1;
    Set<Character> window = new HashSet<>();
    for (int i = 0; i < s.length(); i++) {
        if (i != 0) {
            window.remove(s.charAt(i - 1));
        }
        while (rightIndex + 1 < s.length() && !window.contains(s.charAt(rightIndex + 1))) {
            window.add(s.charAt(rightIndex + 1));
            rightIndex++;
        }
        maxLen = Math.max(rightIndex - i + 1, maxLen);
    }
    return maxLen;
}

三数之和

一个包含n个整数的数组nums，判断nums中是否存在三个元素a，b，c ，使得a + b + c = 0，找出所有和为0且不重复的三元组

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
public List<List<Integer>> threeSum(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    // 枚举 a
    for (int first = 0; first < n; ++first) {
        // 需要和上一次枚举的数不相同
        if (first > 0 && nums[first] == nums[first - 1]) {
            continue;
        }
        // c 对应的指针初始指向数组的最右端
        int third = n - 1;
        int target = -nums[first];
        // 枚举 b
        for (int second = first + 1; second < n; ++second) {
            // 需要和上一次枚举的数不相同
            if (second > first + 1 && nums[second] == nums[second - 1]) {
                continue;
            }
            // 需要保证 b 的指针在 c 的指针的左侧
            while (second < third && nums[second] + nums[third] > target) {
                --third;
            }
            // 如果指针重合，随着 b 后续的增加
            // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
            if (second == third) {
                break;
            }
            if (nums[second] + nums[third] == target) {
                List<Integer> list = new ArrayList<Integer>();
                list.add(nums[first]);
                list.add(nums[second]);
                list.add(nums[third]);
                ans.add(list);
            }
        }
    }
    return ans;
}