年度回顾

力扣 Rewind’23 - 年度回顾 (leetcode.cn)

image-20231221191916111

数组

一维

除自身以外数组的乘积

238. 除自身以外数组的乘积 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] productExceptSelf(int[] nums) {
    int len = nums.length;
    int[] ans = new int[len];
    // 数组的含义是当前位置左边或者右边的乘积
    int[] L = new int[len];
    int[] R = new int[len];
    L[0] = 1;
    for (int i = 1; i < len; i++) {
        L[i] = L[i - 1] * nums[i - 1];
    }
    R[len - 1] = 1;
    for (int i = len - 2; i >= 0; i--) {
        R[i] = R[i + 1] * nums[i + 1];
    }
    for (int i = 0; i < len; i++) {
        ans[i] = L[i] * R[i];
    }
    return ans;
}

下一个排列

31. 下一个排列 - 力扣（LeetCode）

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
public void nextPermutation(int[] nums) {
    int i = nums.length - 2;
    // 3621 后往前找，找到第一个不是递增的3，找到第一个比前面大的6，交换
    while(i >= 0 && nums[i] >= nums[i + 1]){
        i--;
    }
    if(i >= 0){
        int j = nums.length - 1;
        while(j >= 0 && nums[i] >= nums[j]){
            j--;
        }
        swap(nums, i, j);
    }
    reverse(nums, i + 1);
}

public void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

public void reverse(int[] nums, int start) {
    int left = start, right = nums.length - 1;
    while (left < right) {
        swap(nums, left, right);
        left++;
        right--;
    }
}

按规则计算统计结果

LCR 191. 按规则计算统计结果 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[] statisticalResult(int[] arrayA) {
    if (arrayA.length == 0) return arrayA;
    int len = arrayA.length;
    // 当前位置左边的所有乘积
    int[] L = new int[len];
    // 当前位置右边的所有乘积
    int[] R = new int[len];
    L[0] = 1;
    for (int i = 1; i < len; i++) {
        L[i] = L[i - 1] * arrayA[i - 1];
    }
    R[len - 1] = 1;
    for (int i = len - 2; i >= 0; i--) {
        R[i] = R[i + 1] * arrayA[i + 1];
    }
    int[] ans = new int[len];
    for (int i = 0; i < len; i++) {
        ans[i] = L[i] * R[i];
    }
    return ans;
}

数组中重复的数据

442. 数组中重复的数据 - 力扣（LeetCode）

下标交换法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<Integer> findDuplicates(int[] nums) {
    // 把每个数都放到下标位置，比如nums[0] = 4，那么看nums[3]是否是4，不是就交换
    for (int i = 0; i < nums.length; i++) {
        while (nums[i] != nums[nums[i] - 1]) {
            swap(nums, i, nums[i] - 1);
        }
    }
    // 如果下标位置和对应的值不符合，就说明重复了
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (i != nums[i] - 1) {
            res.add(nums[i]);
        }
    }
    return res;
}

public void swap(int[] nums, int index1, int index2) {
    int temp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = temp;
}

负号标记法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<Integer> findDuplicates(int[] nums) {
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        int x = Math.abs(nums[i]);
        // 如果下标位置>0，说明第一次遇到，把他标记为负号
        if (nums[x - 1] > 0) {
            nums[x - 1] = -nums[x - 1];
        } else {
            // 否则，加入结果集
            res.add(x);
        }
    }
    return res;
}

缺失的第一个正数

41. 缺失的第一个正数 - 力扣（LeetCode）

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 firstMissingPositive(int[] nums) {
    int n = nums.length;
    // 让 nums 里面的数字属于 [1~n]
    for (int i = 0; i < n; i++) {
        // 第一个不存在的整数最大也就是 n + 1
        if (nums[i] <= 0) nums[i] = n + 1;
    }
    // i 是下标
    for (int i = 0; i < n; i++) {
        // num 代表当前下标的数字绝对值
        int num = Math.abs(nums[i]);
        // 这个数字要当下标，就要 - 1
        int index = num - 1;
       // 符合下标范围的就 负号
        if(index < n){
            nums[index] = -Math.abs(nums[index]);
        }
    }
    // 第一个不是负号的就是缺失的
    for (int i = 0; i < n; i++) {
        if (nums[i] > 0) return i + 1;
    }
    // 下标范围被占满了
    return n + 1;
}

在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

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
public int[] searchRange(int[] nums, int target) {
    // 找左值
    int left = lowerBound(nums, target);
    if (left >= nums.length || nums[left] != target) {
        return new int[]{-1, -1};
    }
    // 找右值
    int right = lowerBound(nums, target + 1) - 1;
    return new int[]{left, right};
}
// 写法二：左闭右闭区间
private int lowerBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // 左闭右闭区间
    while (left <= right) {
        int mid = (left + right) / 2;
        // 相等就一直找最左的
        if (nums[mid] >= target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}
// 写法二：左闭右开区间
private int lowerBound(int[] nums, int target) {
    int left = 0, right = nums.length;
    // 左闭右开区间
    while (left < right) {
        int mid = (left + right) / 2;
        // 相等就一直找最左的
        if (nums[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

二维

旋转图像

48. 旋转图像 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void rotate(int[][] matrix) {
    int n = matrix.length;
    int count = 0;
    // 左上-右下 对角交换
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < count; j++) {
            swap(matrix, i, j, j, i);
        }
        count++;
    }
    // 中间垂直线交换
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n / 2; j++) {
            swap(matrix, i, j, i, n - 1 - j);
        }
    }
}

private void swap(int[][] matrix, int a1, int b1, int a2, int b2) {
    int temp = matrix[a1][b1];
    matrix[a1][b1] = matrix[a2][b2];
    matrix[a2][b2] = temp;
}

矩阵置零

73. 矩阵置零 - 力扣（LeetCode）

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
public void setZeroes(int[][] matrix) {
    // 用第一行和第一列记录此行或者此列是否需要被修改
    int m = matrix.length;
    int n = matrix[0].length;
    boolean flagRow0 = false;
    boolean flagCol0 = false;
    //由于后面会被修改，所以提前记录好是否需要改变这一行或列
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) {
            flagCol0 = true;
            break;
        }
    }
    for (int j = 0; j < n; j++) {
        if (matrix[0][j] == 0) {
            flagRow0 = true;
            break;
        }
    }
    // 标记
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if(matrix[i][j] == 0){
                matrix[0][j] = matrix[i][0] = 0;
            }
        }
    }
    // 替换0
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if(matrix[0][j] == 0 || matrix[i][0] == 0){
                matrix[i][j] = 0;
            }
        }
    }
    // 替换标志位
    if (flagCol0) {
        for (int i = 0; i < m; i++) {
            matrix[i][0] = 0;
        }
    }
    if (flagRow0) {
        for (int j = 0; j < n; j++) {
            matrix[0][j] = 0;
        }
    }
}

螺旋矩阵

54. 螺旋矩阵 - 力扣（LeetCode）

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
public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res = new LinkedList<>();
    int m = matrix.length, n = matrix[0].length;
    // 四个变量控制
    int left = 0, right = n - 1;
    int top = 0, bottom = m - 1;
    // 剩余要打印的数字
    int count = m * n;
    while (count > 0) {
        for (int j = left; j <= right && count > 0; j++) {
            res.add(matrix[top][j]);
            count--;
        }
        top++;
        for (int i = top; i <= bottom && count > 0; i++) {
            res.add(matrix[i][right]);
            count--;
        }
        right--;
        for (int j = right; j >= left && count > 0; j--) {
            res.add(matrix[bottom][j]);
            count--;
        }
        bottom--;
        for (int i = bottom; i >= top && count > 0; i--) {
            res.add(matrix[i][left]);
            count--;
        }
        left++;
    }
    return res;
}

搜索二维矩阵 II

240. 搜索二维矩阵 II - 力扣（LeetCode）

z字法：对某个节点来说，上边是小的，右边是大的，组成一个you’xu

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 public boolean searchMatrix(int[][] matrix, int target) {
    int row = matrix.length - 1;
    int col = 0;
    // 从左下角开始往右上角走
    while (row >= 0 && col < matrix[0].length) {
        if (matrix[row][col] == target) {
            return true;
        }
        if (matrix[row][col] > target) {
            row--;
        }else {
            col++;
        }
    }
    return false;
}

合并区间

56. 合并区间 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[][] merge(int[][] intervals) {
    // 合并区间，自然需要有序，两个元素，第一个有序
    Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
    int[][] ans = new int[intervals.length][2];
    ans[0] = intervals[0];
    // 当前答案区间的位置
    int index = 0;
    for (int i = 1; i < intervals.length; i++) {
        // 合并，当前区间的左边界 <= 答案区间的右边界 [1,6][3,4]
        if (ans[index][1] >= intervals[i][0]) {
            // 更换答案右边界
            ans[index][1] = Math.max(ans[index][1], intervals[i][1]);
        }
        // 不合并
        else {
            // 当前区间加入答案
            ans[++index] = intervals[i];
        }
    }
    return Arrays.copyOf(ans, index + 1);
}

字符串

字符串相加

415. 字符串相加 - 力扣（LeetCode）

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
public String addStrings(String num1, String num2) {
    // 双指针，从后往前，需要一个进位标志
    char[] s1 = num1.toCharArray();
    char[] s2 = num2.toCharArray();
    int p1 = s1.length - 1, p2 = s2.length - 1;
    int flag = 0;
    StringBuilder ans = new StringBuilder();
    while (p1 >= 0 || p2 >= 0) {
        int num = 0;
        // 短的字符串已经处理完了
        if (p1 < 0) {
            num = s2[p2--] - '0' + flag;
        } else if (p2 < 0) {
            num = s1[p1--] - '0' + flag;
        }
        // 对位两数相加
        else {
            num = s2[p2--] - '0' + s1[p1--] - '0' + flag;
        }
        // 取余，进位
        if (num >= 10) {
            flag = 1;
            num %= 10;
        } else flag = 0;
        // 添加到答案
        ans.append(num);
    }
    // 还有个进位要处理
    if (flag == 1) {
        ans.append(1);
    }
    return ans.reverse().toString();
}

替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

找不到原题了

LCR 122. 路径加密 - 力扣（LeetCode）

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
public String replaceSpace(String s) {
    
    int cnt = 0;
	// 计算出有多少空格
    for(int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if(c == ' '){
            cnt++;
        }
    }
    // 申请char[]存储空间
    char[] res = new char[s.length() + 2 * cnt];
    int index = 0;
    // 遍历s ，空格替换
    for(int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if(c != ' '){
            res[index++] = c;
        }else{
            res[index++] = '%';
            res[index++] = '2';
            res[index++] = '0';
        }
    }
    return new String(res);
}

反转字符串中的单词

151. 反转字符串中的单词 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
public String reverseWords(String s) {
    // 用 Java 的 split 函数
    String[] words = s.split(" ");
    StringBuilder sb = new StringBuilder();
    for (int i = words.length - 1; i >= 0; i--) {
        String word = words[i];
        if (!word.isEmpty()) {
            sb.append(word).append(" ");
        }
    }
    sb.deleteCharAt(sb.length() - 1);
    return sb.toString();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public String reverseWords(String s) {
    // 用 Java 的 split 函数
    int left = s.length() - 1, right = s.length();
    StringBuilder sb = new StringBuilder();
    // 后往前遍历
    while (left >= 0) {
        // 找单词
        while (left >= 0 && s.charAt(left) != ' ') left--;
        // 此时left是空格
        sb.append(s.substring(left + 1, right)).append(" ");
        // 去除连续空格
        while (left >= 0 && s.charAt(left) == ' ') left--;
        right = left + 1;
    }
    // 结尾会多一个空格，开头可能也会多
    return sb.toString().trim();
}

最长回文子串

5. 最长回文子串 - 力扣（LeetCode）

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
public String longestPalindrome(String s) {
    if (s.isEmpty()) {
        return "";
    }
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        // 两种可能
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        // 更新返回的区间
        if (len > end - start + 1) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

public int expandAroundCenter(String s, int left, int right) {
    // 中心向两边遍历，直到两个字符不相等
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}

哈希表

分类

数组、set、map

是否出现相同元素、同类元素、有某种关系的元素（如相加为x）

两数之和

1. 两数之和 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] twoSum(int[] nums, int target) {
    // hash表记录之前遍历过的
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int x = target - nums[i];
        if (map.containsKey(x)) {
            return new int[]{map.get(x), i};
        } else {
            map.put(nums[i], i);
        }
    }
    return new int[]{-1, -1};
}

和为 K 的子数组（和两数之和相似）

当前节点还要一次遍历，考虑用哈希表

560. 和为 K 的子数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    // 和为0的数组有一个空的
    map.put(0, 1);
    int preNum = 0;
    int ans = 0;
    for (int num : nums) {
        preNum += num;
        // 某种关系
        int x = preNum - k;
        if (map.containsKey(x)) {
            ans += map.get(x);
        }
        // 维护哈希表
        map.put(preNum, map.getOrDefault(preNum, 0) + 1);
    }
    return ans;
}

路径总和 III

437. 路径总和 III - 力扣（LeetCode）

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
public int pathSum(TreeNode root, int targetSum) {
    // 当前所有的前缀和
    Map<Long, Integer> prefix = new HashMap<Long, Integer>();
    // 用来判断根节点是否自己是一个路径
    prefix.put(0L, 1);
    return dfs(root, prefix, 0, targetSum);
}

// 从下往上计算，路径和是当前节点前缀和-之前的某个节点的前缀和
public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
    if (root == null) {
        return 0;
    }
    // cur是当前的前缀和
    int ret = 0;
    curr += root.val;

    // 计算当前节点的前缀和是否符合条件
    ret = prefix.getOrDefault(curr - targetSum, 0);
    // 加入前缀和
    prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
    // 加上左右子树的答案
    ret += dfs(root.left, prefix, curr, targetSum);
    ret += dfs(root.right, prefix, curr, targetSum);
    // 退出前缀和
    prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);

    return ret;
}

字母异位词分组

49. 字母异位词分组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<List<String>> groupAnagrams(String[] strs) {
    // map存放（排序后的字符串，所有字母异位词的集合）
    final HashMap<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
        // 转成数组排序
        final char[] array = str.toCharArray();
        String oldArray = new String(array);
        Arrays.sort(array);
        List<String> strings = map.get(new String(array));
        if (strings == null) {
            strings = new ArrayList<>();
        }
        strings.add(oldArray);
        map.put(new String(array), strings);
    }
    final List<List<String>> res = new ArrayList<>();
    map.forEach((key, value) -> {
        res.add(map.get(key));
    });
    return res;
}

最长连续序列

128. 最长连续序列 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int longestConsecutive(int[] nums) {
    // 数组转成set，方便后续查找
    final HashSet<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }
    int longestStreak = 0;
    for (int num : nums) {
        int currentNum = num;
        // 遍历set，如果没有比当前值小1的值，就继续往后遍历，HashSet查找
        if (!set.contains(num - 1)) {
            int currentStreak = 1;
            while (set.contains(currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }
            longestStreak = Math.max(longestStreak, currentStreak);
        }
    }
    return longestStreak;
}

字符串中的第一个唯一字符

387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
public int firstUniqChar(String s) {
    char[] dictionary = new char[26];
    char[] chars = s.toCharArray();
    // 遍历两次，第二次就知道字母是否有重复了，>1 就是重复
    for (char c : chars) {
        dictionary[c - 'a']++;
    }
    for (int i = 0; i < chars.length; i++) {
        if (dictionary[chars[i] - 'a'] == 1) return i;
    }
    return -1;
}

栈、队列

单调栈有感，一个是接雨水维护单调递减的栈，一个是计算矩形最大面积维护单调递增的栈，两者都可以从某个柱子往左往右找到更大或者更小的值，这样就会形成凹槽或者突起，那么单调栈可以降低时间复杂度到O(n)，用空间换取时间，每次元素的出栈，都意味着这个元素的右边是第一个更大/更小的元素，弹出后的栈顶元素是左边是第一个更大/更小的元素，这样就可以计算了。

用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）

用s1作为主栈，s2为辅助栈

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
class MyQueue {

    Stack<Integer> S1, S2;

    public MyQueue() {
        S1 = new Stack();
        S2 = new Stack();
    }
    
    public void push(int x) {
        S1.push(x);
    }
    
    public int pop() {
        while(!S1.isEmpty()){
            S2.push(S1.pop());
        }
        int res = S2.pop();
        while(!S2.isEmpty()){
            S1.push(S2.pop());
        }
        return res;
    }
    
    public int peek() {
        while(!S1.isEmpty()){
            S2.push(S1.pop());
        }
        int res = S2.peek();
        while(!S2.isEmpty()){
            S1.push(S2.pop());
        }
        return res;
    }
    
    public boolean empty() {
        return S1.isEmpty();
    }
}

有效的括号

20. 有效的括号 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean isValid(String s) {
    char[] chars = s.toCharArray();
    // 用栈的特性，或者快慢指针也行应该
    Stack<Character> S = new Stack<>();
    HashMap<Character, Character> map = new HashMap<>(3);
    map.put('(', ')');
    map.put('[', ']');
    map.put('{', '}');
    for (char c : chars) {
        if (c == '(' || c == '[' || c == '{') {
            S.push(c);
        } else {
            if(S.isEmpty()){
                return false;
            }else {
                Character popC = S.pop();
                if (!map.get(popC).equals(c)) return false;
            }
        }
    }
    return S.isEmpty();
}

接雨水

42. 接雨水 - 力扣（LeetCode）

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
public int trap(int[] height) {
    // 维护一个单调递减的栈，存放下标
    Stack<Integer> S = new Stack();
    S.push(0);
    // 返回值
    int sum = 0;
    // 循环遍历每个柱子
    for (int i = 1; i < height.length; i++) {
        Integer top = S.peek();
        // 发现柱子高度比栈顶元素小，加入栈
        if (height[i] < height[top]) {
            S.push(i);
        }
        // 高度相同，取右边的柱子计算
        else if (height[i] == height[top]) {
            S.pop();
            S.push(i);
        }
        // 大于说明有坑，则弹出栈顶元素为底部，开始计算横向，底部和两边的最小差值和左右两边距离的乘积
        // 循环计算，一直到栈顶元素比当前柱子高，才说明没有坑了
        else {
            while(!S.isEmpty() && height[i] > height[S.peek()]){
                int mid = S.pop();
                if(!S.isEmpty()){
                    int left = S.peek();
                    int width = i - left - 1;
                    int high = Math.min(height[i], height[left]) - height[mid];
                    sum += width * high;
                }
            }
            S.push(i);
        }
    }
    return sum;
}

最小栈

155. 最小栈 - 力扣（LeetCode）

辅助栈

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
class MinStack {

    // 再用一个存放最小值的栈
    // 如果在栈内存放一个值，那么需要判断是否是当前所有元素中最小的
    // 如果在栈弹出一个值，那么直接弹出就好了，因为下一层的最小值和本层无关
    // 最小栈每层代表的是当前层往前的元素的最小值

    Deque<Integer> xStack;
    Deque<Integer> minStack;

    public MinStack() {
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        xStack.push(val);
        minStack.push(Math.min(minStack.peek(), val));
    }
    
    public void pop() {
        xStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return xStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

辅助数字代替辅助栈

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
class MinStack {

    Deque<Integer> xStack;
    // 用一个数字代替最小栈
    // 当push的时候看看当前值，如果比最小值小，那么需要记录下最小值（也就是在push当前值之前先push最小值）
    int min = Integer.MAX_VALUE;

    public MinStack() {
        xStack = new LinkedList<Integer>();
    }
    
    public void push(int val) {
        // 当前值更小
        if(val <= min){   
            // 将之前的最小值保存
            xStack.push(min);
            // 更新最小值
            min = val;
        }
        xStack.push(val);
    }
    
    public void pop() {
        int val = xStack.pop();
        // 如果当前是最小值，说明还需要再pop一个，看push就懂了
        if(val == min){
            min = xStack.pop();
        }
    }
    
    public int top() {
        return xStack.peek();
    }
    
    public int getMin() {
        return min;
    }
}

验证栈序列

946. 验证栈序列 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean validateStackSequences(int[] pushed, int[] popped) {
    Stack<Integer> S = new Stack<>();
    int length = pushed.length;
    int j = 0;
    // 模拟栈的弹出
    // 一直加，直到当前 pushed[] 的元素 == popped[] 位置的元素，说明要弹出了
    for (int i = 0; i < length; i++) {
        S.push(pushed[i]);
        while (!S.isEmpty() && S.peek() == popped[j]){
            S.pop();
            // 更换下次比较的元素
            j++;
        }
    }
    return S.isEmpty();
}

链表

1、删除

删除有删一个、或者是一段区间：

  • 一个的话用prev节点下一个对比val找就行
  • 一段区间需要一个基准值slow指针，一个fast指针对比slow找区间，最后的区间是[slow, fast)，区间可能有1个节点或者多个节点

2、反转链表

找到要反转的区间[startNode, endNode]，用prev和nex记录区间子链表的前驱后继节点，用于反转后再加入链表

反转一般用三指针，while条件一般是cur != null 或者是 prev != endNode

3、合并有序链表

两个或者多个有序链表的合并，双指针判断递归处理，多个考虑归并处理（用递归拆解成小问题，即每次只合并两个链表）

重排链表

143. 重排链表 - 力扣（LeetCode）

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
public void reorderList(ListNode head) {
    if (head == null) {
        return;
    }
    // 1.找到中点 mid
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode mid = slow;
    // 2.反转后半链表
    ListNode l1 = head;
    ListNode l2 = mid.next;
    mid.next = null;
    l2 = reverseList(l2);
    // 3.合并链表
    mergeList(l1, l2);
}

private void mergeList(ListNode l1, ListNode l2) {
    ListNode p1, p2;
    while (l1 != null && l2 != null) {
        // 记住下一个
        p1 = l1.next;
        p2 = l2.next;
        // 连接
        l1.next = l2;
        l2.next = p1;
        // 移动指针
        l2 = p2;
        l1 = p1;
    }
}

private ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode nex = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nex;
    }
    return prev;
}

相交链表

160. 相交链表 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    // 两个指针同时遍历，空了就从对方头重新走一遍对方的路，终会遇见
    while (pA != pB) {
        pA = pA == null ? pB : pA.next;
        pB = pB == null ? pA : pB.next;
    }
    // 相遇或者走完两个链表最后到了null
    return pA;
}

环形链表

141. 环形链表 - 力扣（LeetCode）

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

环形链表 II

142. 环形链表 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode detectCycle(ListNode head) {
    // 环结构都可以用快慢指针，满指针一次走一步，快指针一次走两步
    // 数学推导，当快慢指针第一次相遇，只需要让两个指针，一个从起点开始走，一个从相遇点开始走，两个指针会在环的入口相遇
    ListNode slow = head, fast = head;
    // while循环的条件，首先是考虑遍历链表，即会不会无环
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;  
        if (slow == fast) {
            ListNode p1 = head;
            ListNode p2 = slow;
            while (p1 != p2) {
                p1 = p1.next;
                p2 = p2.next;
            }
            return p1;
        }
    }
    return null;
}

移除链表元素

203. 移除链表元素 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public ListNode removeElements(ListNode head, int val) {
    ListNode hair = new ListNode(-1);
    hair.next = head;
    ListNode cur = hair;
    while (cur != null && cur.next != null) {
        // 删除不一定每次都要指针，可能有重复的
        if (cur.next.val == val) {
            cur.next = cur.next.next;
        }else {
            cur = cur.next;
        }
    }
    return hair.next;
}

删除链表中的节点（特殊）

237. 删除链表中的节点 - 力扣（LeetCode）

1
2
3
4
5
6
public void deleteNode(ListNode node) {
    // 把后一个节点的值赋给自己
    node.val = node.next.val;
    // 此时只需要假装自己是下一个节点，把下一个节点当成自己，把自己删掉就好了
    node.next = node.next.next;
}

删除排序链表中的重复元素

83. 删除排序链表中的重复元素 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode deleteDuplicates(ListNode head) {
    if (head == null) return null;
    ListNode slow = head, fast = head.next;

    // slow == fast，删除fast，可能不止一个，所以要保持slow不动
    // slow != fast，说明slow没有风险，slow可以移动
    // 每次都移动fast，fast指向的是可能相同的数字，fast到结尾结束循环
    while (fast != null) {

        if (slow.val == fast.val) {
            slow.next = fast.next;
        } else {
            slow = slow.next;
        }

        fast = fast.next;
    }

    return head;
}

删除排序链表中的重复元素 II

82. 删除排序链表中的重复元素 II - 力扣（LeetCode）

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
public ListNode deleteDuplicates(ListNode head) {
    if(head == null) return null;
    // prev用来删除元素
    // slow作为基准对比元素是否需要删除
    // fast用来遍历
    ListNode hair = new ListNode(-1);
    hair.next = head;
    ListNode prev = hair;
    ListNode slow = head, fast = head.next;
    while (fast != null) {
        boolean isDelete = false;
        while (fast != null && slow.val == fast.val) {
            fast = fast.next;
            isDelete = true;
        }
        // 此时 slow 和 fast 不同
        // 确定是否需要删除
        if (isDelete) {
   			// 此时前驱节点不用变化
            prev.next = fast;
        } else {
            // 此时前驱节点需要往后一位
            prev = slow;
        }
        // 更新基准
        slow = fast;
        // 指针移动
        if(fast != null) fast = fast.next;
    }
    return hair.next;
}

反转链表

206. 反转链表 - 力扣（LeetCode）

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode reverseList(ListNode head) {
    // 三指针，prev，cur，nex
    // cur -> nex 要转成 cur -> prev
    ListNode prev = null;
    ListNode cur = head;
    ListNode nex = null;
    while (cur != null) {
        // 记录cur的下一个节点，否则无法继续反转
        nex = cur.next;
        // 反转
        cur.next = prev;
        // 指针移动，执行下一次反转
        prev = cur;
        cur = nex;
    }
    return prev;
}

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode reverseList(ListNode head) {
        return reverseList(null, head);
    }

    public ListNode reverseList(ListNode p1, ListNode p2) {
        // 没有下一个节点，返回当前节点
        if (p2 == null) return p1;
        // 记录cur的下一个节点，否则无法继续递归反转
        ListNode nex = p2.next;
        // 每次都让后面的指向前面的就好了，即 p2 -> p1
        p2.next = p1;
        return reverseList(p2, nex);
    }

反转链表 II

92. 反转链表 II - 力扣（LeetCode）

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
public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode hair = new ListNode(-1);
    hair.next = head;
    // 一个前驱节点，一个后继节点，方便连接反转后的链表
    ListNode prev = hair, nex = null;
    ListNode p = hair;
    int count = 0;
    // 循环结束， p == left
    while (count < left) {
        prev = p;
        p = p.next;
        count++;
    }
    // 反转的子链表的左边开头
    ListNode start = p;
    // 循环结束， p == right
    while (count < right) {
        p = p.next;
        count++;
    }
    // 反转的子链表的右边结尾
    ListNode end = p;
    nex = end.next;
    // 断开连接
    prev.next = null;
    reverse(start, end);
    prev.next = end;
    start.next = nex;
    return hair.next;
}

public void reverse(ListNode leftNode, ListNode rightNode) {
    ListNode pre = null;
    ListNode cur = leftNode;
    ListNode nex;
    while (pre != rightNode) {
        nex = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nex;
    }
}

K 个一组翻转链表

25. K 个一组翻转链表 - 力扣（LeetCode）

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
public ListNode reverseKGroup(ListNode head, int k) {
        ListNode hair = new ListNode(-1);
        hair.next = head;

        ListNode cur = head;
        ListNode prev = hair, nex;
        while (cur != null) {
            ListNode start = cur, end;
            // 找区间
            int count = 0;
            while (count < k - 1 && cur != null) {
                cur = cur.next;
                count++;
            }
            end = cur;
            // 最后一组没到条件不用反转
            if(end == null){
                return hair.next;
            }
            // 反转
            prev.next = null;
            nex = cur != null ? cur.next : null;
            reverseList(start, end);
            prev.next = end;
            start.next = nex;
            // 继续循环
            cur = start.next;
            prev = start;
        }
        return hair.next;
    }


    public void reverseList(ListNode head, ListNode tail) {
        // 链表区间[left, right)
        ListNode left = head;
        ListNode cur = left;
        ListNode prev = null, nex;
        while (prev != tail) {
            nex = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nex;
        }
    }

随机链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

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
public Node copyRandomList(Node head) {
    if (head == null) return null;
    // cur是用来遍历的指针
    Node cur = head;
    // 第一次遍历把 1 -> 2 -> 3 变成 1 -> 1' -> 2 -> 2' -> 3 -> 3'
    // 此时 next指针已经复制完成，还差 random指针
    while (cur != null) {
        Node nex = cur.next;
        Node newNode = new Node(cur.val);
        cur.next = newNode;
        newNode.next = nex;
        cur = nex;
    }
    // 第二次遍历搞定复制 random指针
    cur = head;
    while (cur != null) {
        if(cur.random != null) cur.next.random = cur.random.next;
        cur = cur.next.next;
    }
    // 分离链表
    Node hair = new Node(-1);
    Node p = hair;
    cur = head;
    // cur指向1，p指向1‘，交替向后分离
    while (cur != null) {
        p.next = cur.next;
        p = cur.next;
        cur.next = p.next;
        cur = cur.next;
    }
    return hair.next;
}

Hash表法

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
public Node copyRandomList(Node head) {
    if(head==null) {
        return null;
    }
    //创建一个哈希表，key是原节点，value是新节点
    Map<Node,Node> map = new HashMap<Node,Node>();
    Node p = head;
    //将原节点和新节点放入哈希表中
    while(p!=null) {
        Node newNode = new Node(p.val);
        map.put(p,newNode);
        p = p.next;
    }
    p = head;
    //遍历原链表，设置新节点的next和random
    while(p!=null) {
        Node newNode = map.get(p);
        //p是原节点，map.get(p)是对应的新节点，p.next是原节点的下一个
        //map.get(p.next)是原节点下一个对应的新节点
        if(p.next!=null) {
            newNode.next = map.get(p.next);
        }
        //p.random是原节点随机指向
        //map.get(p.random)是原节点随机指向  对应的新节点 
        if(p.random!=null) {
            newNode.random = map.get(p.random);
        }
        p = p.next;
    }
    //返回头结点，即原节点对应的value(新节点)
    return map.get(head);
}

合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

递归法

1
2
3
4
5
6
7
8
9
10
11
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list2 == null) return list1;
    if (list1 == null) return list2;
    if (list1.val < list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode hair = new ListNode(-1);
    ListNode cur = hair;
    // 比较，然后小的给新链表
    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            cur.next = new ListNode(list1.val);
            list1 = list1.next;
        } else {
            cur.next = new ListNode(list2.val);
            list2 = list2.next;
        }
        cur = cur.next;
    }
    if (list1 != null) cur.next = list1;
    if (list2 != null) cur.next = list2;
    return hair.next;
}

合并 K 个升序链表

23. 合并 K 个升序链表 - 力扣（LeetCode）

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 ListNode mergeKLists(ListNode[] lists) {
    return merge(lists, 0, lists.length - 1);
}

private ListNode merge(ListNode[] lists, int l, int r) {
    if (l > r) return null;
    if (l == r) return lists[l];
    int mid = (l + r) / 2;
    // 用自底向上的归并排序
    ListNode leftMerge = merge(lists, l, mid);
    ListNode rightMerge = merge(lists, mid + 1, r);
    return mergeTwoList(leftMerge, rightMerge);
}
// 合并两个有序链表
private ListNode mergeTwoList(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) {
        l1.next = mergeTwoList(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoList(l1, l2.next);
        return l2;
    }
}

排序链表

148. 排序链表 - 力扣（LeetCode）

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
public ListNode sortList(ListNode head) {
    if (head == null) return null;
    // 自底向上归并排序
    // 获取链表长度
    int length = 0;
    ListNode p = head;
    while (p != null) {
        p = p.next;
        length++;
    }
    ListNode hair = new ListNode(-1);
    hair.next = head;
    // 每次合并两个子链表，子链表长度每次 * 2
    // len是当前合并的每条子链表的长度
    for (int len = 1; len < length; len *= 2) {
        ListNode prev = hair, cur = hair.next;
        while (cur != null) {
            ListNode l1 = cur;
            // 找到第一个子链表尾巴
            for (int i = 1; i < len && cur.next != null; i++) {
                cur = cur.next;
            }
            ListNode l2 = cur.next;
            // 避免影响合并，断开连接
            cur.next = null;
            // 找到第二个子链表尾巴
            cur = l2;
            for (int i = 1; i < len && cur != null && cur.next != null; i++) {
                cur = cur.next;
            }
            ListNode nex = null;
            // 避免影响合并，断开连接
            if (cur != null) {
                nex = cur.next;
                cur.next = null;
            }
            // 合并完连接到前驱节点
            ListNode merged = merge(l1, l2);
            prev.next = merged;
            // 移动前驱节点
            while (prev.next != null) {
                prev = prev.next;
            }
            // 移动指针，下一次合并
            cur = nex;
        }
    }
    return hair.next;
}

/**
 * 合并有序链表
 */
private ListNode merge(ListNode head1, ListNode head2) {
    if (head1 == null) return head2;
    if (head2 == null) return head1;
    if (head1.val <= head2.val) {
        head1.next = merge(head1.next, head2);
        return head1;
    } else {
        head2.next = merge(head2.next, head1);
        return head2;
    }
}

堆

数组中的第K个最大元素

215. 数组中的第K个最大元素 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int findKthLargest(int[] nums, int k) {
    // 小顶堆
    PPriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (n1, n2) -> {
        return n1 - n2;
    });
    for (int i = 0; i < k; i++) {
        minHeap.add(nums[i]);
    }

    for (int i = k; i < nums.length; i++) {
        Integer topNode = minHeap.peek();
        // 保证里面k个数是数组中最大的k个数，每次淘汰k个数中最小的
        if (nums[i] > topNode) {
            minHeap.poll();
            minHeap.add(nums[i]);
        }
    }
    // 堆顶就是第k大
    return minHeap.peek();
}

数据流的中位数

295. 数据流的中位数 - 力扣（LeetCode）

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
PriorityQueue<Integer> queMin;
PriorityQueue<Integer> queMax;

public MedianFinder() {
    queMin = new PriorityQueue<>((n1, n2) -> (n2 - n1));
    queMax = new PriorityQueue<>((n1, n2) -> (n1 - n2));
}

public void addNum(int num) {
    if (queMin.isEmpty()) {
        queMin.offer(num);
    } else if (num < queMin.peek()) {
        queMin.offer(num);
        // 维持大小根堆的长度差值 < 1
        if (queMin.size() > queMax.size() + 1) {
            queMax.offer(queMin.poll());
        }
    } else {
        // 包括queMax.isEmpty() || num >= queMin.peek()
        queMax.offer(num);
        // 维持小根堆的长度 >= 大根堆的长度，这样返回中位数比较好判断
        if(queMax.size() > queMin.size()){
            queMin.offer(queMax.poll());
        }
    }
}

public double findMedian() {
    if (queMin.size() == queMax.size() + 1) {
        return queMin.peek();
    }
    return (queMin.peek() + queMax.peek()) / 2.0;
}

丑数 II

264. 丑数 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int nthUglyNumber(int n) {
    int[] factors = new int[]{2, 3, 5};
    // 为了丑数堆没有重复元素
    Set<Long> seen = new HashSet<Long>();
    // 丑数堆
    PriorityQueue<Long> minHeap = new PriorityQueue<>();
    seen.add(1L);
    minHeap.offer(1L);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        // 如果 x 是丑数，那么 2x、3x、5x也是丑数，添加到丑数堆里
        long curr = minHeap.poll();
        ans = (int) curr;
        for (int factor : factors) {
            long next = curr * factor;
            if (seen.add(next)) {
                minHeap.offer(next);
            }
        }
    }
    return ans;
}

三指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int nthUglyNumber(int n) {
    // 每个位置代表第几个丑数
    int[] ans = new int[n + 1];
    ans[1] = 1;
    for (int i2 = 1, i3 = 1, i5 = 1, i = 2; i <= n; i++) {
        // ans[]是丑数，那么 a,b,c 也是丑数，每次找出最小的存入ans，也就维护了一个递增的丑数组
        int a = 2 * ans[i2];
        int b = 3 * ans[i3];
        int c = 5 * ans[i5];
        int min = Math.min(a, Math.min(b, c));
        // 比较过一次就不能再用了
        if (min == a) i2++;
        if (min == b) i3++;
        if (min == c) i5++;
        // 更新丑数组
        ans[i] = min;
    }
    return ans[n];
}

树

递归的时间复杂度：目前不清楚

递归的空间复杂度：目前不清楚

树的题目首先要想的就是递归去解决，因为每个节点都有左子树和右子树这样相同的结构

遍历的话，一般dfs就是用递归，还有一个是bfs层序遍历，很多题目都是在遍历的基础上去做的

中序遍历二叉搜索树的话，是一个递增的数组

如果要修改树的结构，可能需要用到pre指针记录父节点位置

1、遍历

  • DFS：前序、中序、后序，用递归或者栈模拟（while条件 root != null || ! stack.isEmpty() ）
  • BFS：层序，用队列模拟（while条件 ! queue.isEmpty() ）

二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣（LeetCode）

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> S = new Stack<>();
    // 根 左 右
    while (root != null || !S.isEmpty()) {
        while (root != null) {
            S.push(root);
            // 根
            ans.add(root.val);
            root = root.left;
        }
        // 左完的根
        root = S.pop();
        // 右
        root = root.right;
    }
    return ans;
}

二叉树的中序遍历

94. 二叉树的中序遍历 - 力扣（LeetCode）

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
List<Integer> ans;
public List<Integer> inorderTraversal(TreeNode root) {
    ans = new ArrayList<>();
    dfs(root);
    return ans;
}

private void dfs(TreeNode root) {
    if (root == null) return;
    dfs(root.left);
    ans.add(root.val);
    dfs(root.right);
}

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> S = new Stack<>();
    // 左 根 右
    while (root != null || !S.isEmpty()) {
        // 左
        while (root != null) {
            S.push(root);
            root = root.left;
        }
        // 根
        root = S.pop();
        ans.add(root.val);
        // 右
        root = root.right;
    }
    return ans;
}

二叉树的后序遍历

145. 二叉树的后序遍历 - 力扣（LeetCode）

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
List<Integer> ans;
public List<Integer> inorderTraversal(TreeNode root) {
    ans = new ArrayList<>();
    dfs(root);
    return ans;
}

private void dfs(TreeNode root) {
    if (root == null) return;
    dfs(root.left);
    dfs(root.right);
    ans.add(root.val);
}

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> S = new Stack<>();
    // 左 右 根
    // 根 右 左 处理，然后反转
    while (root != null || !S.isEmpty()) {
        while (root != null) {
            S.push(root);
            // 根
            ans.add(root.val);
            root = root.right;
        }
        root = S.pop();
        root = root.left;
    }
    Collections.reverse(ans);
    return ans;
}

二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new LinkedList<>();
    if (root == null) return res;
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        List<Integer> ans = new LinkedList<>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        res.add(new ArrayList<>(ans));
    }
    return res;
}

二叉树的右视图

199. 二叉树的右视图 - 力扣（LeetCode）

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
```



## 二叉树的锯齿形层序遍历

[103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/)

```java
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    // 一个队列
    List<List<Integer>> res = new LinkedList<>();
    if(root == null)return res;
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    // 变量控制是否需要反转，第一次不用反转
    boolean flag = false;
    // 层序遍历
    while (!queue.isEmpty()){
        // for循环，一个变量控制是否需要反转
        int size = queue.size();
        LinkedList<Integer> ans = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if(node.left!=null) queue.add(node.left);
            if(node.right!=null) queue.add(node.right);
        }
        if(flag) Collections.reverse(ans);
        flag = !flag;
        res.add(new ArrayList<>(ans));
    }
    return res;
}

二叉搜索树中第K小的元素

230. 二叉搜索树中第K小的元素 - 力扣（LeetCode）

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int count;
int ans;

public int kthSmallest(TreeNode root, int k) {
    // 中序遍历
    count = k;
    dfs(root);
    return ans;
}

private void dfs(TreeNode root) {
    if (root == null) return;
    dfs(root.left);
    // 根，处理
    if (count == 0) {
        return;
    }
    if (--count == 0) {
        ans = root.val;
    }
    dfs(root.right);
}

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int kthSmallest(TreeNode root, int k) {
    // 中序遍历
    Stack<TreeNode> S = new Stack<>();
    while (root != null || !S.isEmpty()) {
        // 左
        while (root != null) {
            S.push(root);
            root = root.left;
        }
        // 根，开始逻辑处理
        root = S.pop();
        if (--k == 0) {
            return root.val;
        }
        // 右
        root = root.right;
    }
    return -1;
}

二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
public int maxDepth(TreeNode root) {
    // 叶子节点没有深度
    if (root == null) return 0;
    int l = maxDepth(root.left);
    int r = maxDepth(root.right);
    // 左右子树最大深度 + 自己的 1 个深度
    return Math.max(l, r) + 1;
}

二叉树的最近公共祖先

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 递归返回条件
    if (root == null || root == p || root == q) return root;
    // 目标节点是否在左子树，不是返回null
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    // 目标节点是否在右子树，不是返回null
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left == null) return right;
    if (right == null) return left;
    // 两边都有目标节点，根节点就是答案
    return root;
}

二叉搜索树的最近公共祖先

235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else if (root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor(root.right, p, q);
    }else {
        return root;
    }
}

验证二叉树的前序序列化

用数组的方式来进行树的遍历，有点意思的

331. 验证二叉树的前序序列化 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int index = 0;
String[] s;

public boolean isValidSerialization(String preorder) {
    s = preorder.split(",");
    dfs();
    return s.length - 1 == index;
}

private void dfs() {

    if(index >= s.length) return;
    if (Objects.equals(s[index], "#")) return;
    // 递归左子树
    index++;
    dfs();
    // 递归右子树
    index++;
    dfs();
}

二叉树的序列化与反序列化

297. 二叉树的序列化与反序列化 - 力扣（LeetCode）

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
String str = "";

// 序列化方法
public String serialize(TreeNode root) {
    rserialize(root);
    return str;
}

private void rserialize(TreeNode root) {
    // 前序遍历，序列化
    if (root == null) {
        str += "None,";
    } else {
        str += str.valueOf(root.val) + ",";
        rserialize(root.left);
        rserialize(root.right);
    }
}

// 反序列化方法
public TreeNode deserialize(String data) {
    String[] dataArray = data.split(",");
    LinkedList<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
    return rdeserialize(dataList);
}

private TreeNode rdeserialize(LinkedList<String> dataList) {
    if(dataList.getFirst().equals("None")){
        dataList.removeFirst();
        return null;
    }
    // 将数组转化为树
    TreeNode root = new TreeNode(Integer.parseInt(dataList.getFirst()));
    dataList.removeFirst();
    root.left = rdeserialize(dataList);
    root.right = rdeserialize(dataList);
    return root;
}

二叉搜索树与双向链表

https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
LinkedList<TreeNode> nodeList = new LinkedList<>();

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;
        // 中序遍历，把数转化为有序数组，然后把数组再转化为链表
        inorder(pRootOfTree);
        for (int i = 0; i < nodeList.size() - 1; i++) {
            nodeList.get(i).right = nodeList.get(i + 1);
            nodeList.get(i + 1).left = nodeList.get(i);
        }
        return nodeList.get(0);
    }

    void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        nodeList.add(root);
        inorder(root.right);
    }

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
// 在遍历的时候就构建好了链表，利用二叉搜索树的中序遍历的有序性，栈内依次弹出较小的节点
TreeNode head = null;
TreeNode prev = null;

public TreeNode Convert(TreeNode pRootOfTree) {
    if (pRootOfTree == null) return null;
    // 中序遍历，把数转化为有序数组，然后把数组再转化为链表
    inorder(pRootOfTree);

    return head;
}

void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    // prev == null，说明是二叉搜索树中最小的节点
    if (prev == null) {
        head = root;
        prev = root;
    } else {
        // prev不为null，构建链表
        prev.right = root;
        root.left = prev;
        prev = root;
    }
    inorder(root.right);
}

从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

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
private Map<Integer, Integer> indexMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {
    int n = preorder.length;
    // 构造哈希映射，帮助我们快速定位根节点
    indexMap = new HashMap<Integer, Integer>();
    for (int i = 0; i < n; i++) {
        indexMap.put(inorder[i], i);
    }
    return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}

public TreeNode buildTree(int[] preorder, int[] inorder, int pre_start, int pre_end, int in_start, int in_end) {
    if (pre_start > pre_end) {
        return null;
    }
    // 子树的根节点
    int root_val = preorder[pre_start];
    TreeNode root = new TreeNode(root_val);
    // 找到根节点
    int index = indexMap.get(root_val);
    // 根节点左边有多少个数
    int leftNum = index - in_start;
    // 构建左右子树
    root.left = buildTree(preorder, inorder, pre_start + 1, pre_start + leftNum, in_start, index - 1);
    root.right = buildTree(preorder, inorder, pre_start + leftNum + 1, pre_end, index + 1, in_end);
    return root;
}

另一棵树的子树

572. 另一棵树的子树 - 力扣（LeetCode）

暴力递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    return dfs(root, subRoot);
}

// 遍历大树的节点
private boolean dfs(TreeNode s, TreeNode t) {
    if (s == null) return false;
    return check(s, t) || dfs(s.left, t) || dfs(s.right, t);
}

// 检测这个节点开始的子树和目标子树的相同情况
private boolean check(TreeNode s, TreeNode t) {
    if (s == null && t == null) return true;
    if (s == null || t == null || s.val != t.val) return false;
    return check(s.left, t.left) && check(s.right, t.right);
}

翻转二叉树

226. 翻转二叉树 - 力扣（LeetCode）

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
public TreeNode invertTree(TreeNode root) {
    // 终止条件
    if (root == null) return null;
    // 每层递归都是交换左右子树
    TreeNode leftNode = root.left;
    TreeNode rightNode = root.right;
    root.left = rightNode;
    root.right = leftNode;
    invertTree(root.left);
    invertTree(root.right);
    // 返回
    return root;
}

层序遍历法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public TreeNode invertTree(TreeNode root) {
    LinkedList<TreeNode> queue = new LinkedList<>();
    if (root == null) return null;
    queue.add(root);
    // 层序遍历
    while (!queue.isEmpty()) {
        int size = queue.size();
        // 循环每行的每个节点，调换节点的左右子节点
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            TreeNode leftNode = node.left;
            TreeNode rightNode = node.right;
            node.left = rightNode;
            node.right = leftNode;
            if (node.right != null) queue.add(node.right);
            if (node.left != null) queue.add(node.left);
        }
    }
    return root;
}

对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isSymmetric(TreeNode root) {
    if(root == null) return true;
    return isSymmetric(root.left, root.right);
}

public boolean isSymmetric(TreeNode leftNode, TreeNode rightNode) {

    // 都为null，符合条件
    if (leftNode == null && rightNode == null) return true;
    // 一个为null，不符合条件
    if (leftNode == null || rightNode == null) return false;
    // 都不为null，数值不同，不符合条件
    if (leftNode.val != rightNode.val) return false;

    // 继续递归
    return isSymmetric(leftNode.left, rightNode.right) && isSymmetric(leftNode.right, rightNode.left);
}

迭代法

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
public boolean isSymmetric(TreeNode root) {
    return check(root, root);
}

public boolean check(TreeNode u, TreeNode v) {
    // 层序遍历
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(u);
    queue.offer(v);
    while (!queue.isEmpty()) {
        u = queue.poll();
        v = queue.poll();
        // 判断条件，是否需要继续迭代
        if (u == null && v == null) {
            continue;
        }
        if ((u == null || v == null) || (u.val != v.val)) {
            return false;
        }
        // 两个一组加入，注意这里是左左和右右，左右和右左
        queue.offer(u.left);
        queue.offer(v.right);

        queue.offer(u.right);
        queue.offer(v.left);
    }
    return true;
}

路径总和

112. 路径总和 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean hasPathSum(TreeNode root, int targetSum) {
    return dfs(root, targetSum);
}

public boolean dfs(TreeNode root, int targetSum) {
    if (root == null) return false;
    // 叶子节点才比较
    if(root.left == null && root.right == null){
        return root.val == targetSum;
    }
    // 递归左右子树
    return dfs(root.left, targetSum - root.val) || dfs(root.right, targetSum - root.val);
}

路径总和 II

113. 路径总和 II - 力扣（LeetCode）

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
List<List<Integer>> res = new LinkedList<>();
LinkedList<TreeNode> path = new LinkedList<>();

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    dfs(root, targetSum);
    return res;
}

public void dfs(TreeNode root, int targetSum) {
    if (root == null) return;
    // 路径添加
    path.add(root);
    // 叶子节点才比较
    if (root.left == null && root.right == null) {
        if (root.val == targetSum) {
            // 符合条件，加入答案
            LinkedList<Integer> ans = new LinkedList<>();
            for (TreeNode treeNode : path) {
                ans.add(treeNode.val);
            }
            res.add(new ArrayList<>(ans));
        }
    }
    // 递归左子树
    dfs(root.left, targetSum - root.val);
    // 回溯
    if (root.left != null) path.removeLast();
    // 递归右子树
    dfs(root.right, targetSum - root.val);
    // 回溯
    if (root.right != null) path.removeLast();
}

二叉树中的最大路径和

124. 二叉树中的最大路径和 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int ans = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    dfs(root);
    return ans;
}

int dfs(TreeNode root) {
    if (root == null) return 0;
    int leftVal = Math.max(dfs(root.left), 0);
    int rightVal = Math.max(dfs(root.right), 0);
    // 当前节点最大路径和
    int maxRoad = root.val + leftVal + rightVal;
    ans = Math.max(ans, maxRoad);
    // 返回的是当前节点作为子节点的贡献，只能取左边或者右边树枝的最大贡献
    return root.val + Math.max(leftVal, rightVal);
}

二叉树的直径

543. 二叉树的直径 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 节点的个数
int ans = 1;

public int diameterOfBinaryTree(TreeNode root) {
    // 遍历的基础上，每个节点都算一次以这个节点为根节点的最长路径
    depth(root);
    // 路径要节点数 - 1
    return ans - 1;
}

public int depth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 左子树的深度
    int left = depth(root.left);
    // 右子树的深度
    int right = depth(root.right);
    // 计算路径
    ans = Math.max(ans, left + right + 1);
    // 返回本节点为根节点的树的深度
    return Math.max(right, left) + 1;
}

图

岛屿数量

nettee的DFS题解无敌

200. 岛屿数量 - 力扣（LeetCode）

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
public int numIslands(char[][] grid) {
    int res = 0;
    int m = grid.length;
    int n = grid[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 发现这个位置是陆地才开始遍历这个岛屿
            if (grid[i][j] == '1') {
                res++;
                // 这里遍历的意义是淹没这个岛屿，不然会重复判断
                dfs(grid, i, j);
            }
        }
    }
    return res;
}

private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') return;
    // 淹没这个位置，保证后续不会重复遍历这个位置，只要遍历过，说明这个位置是属于同一个岛屿的
    grid[i][j] = '0';
    // 遍历这个岛的上下左右
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

二分算法

坚持一个原则，可以是左闭右闭（下标从最小到最大）

每次循环都需要缩小查找的数组的范围，right = mid or right = mid - 1，但是left= mid会造成死循环（比如数组两个数的时候）

x 的平方根

69. x 的平方根 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int mySqrt(int x) {
    int l = 0, r = x;
    while (l <= r) {
        int mid = (l + r) / 2;
        if ((long)mid * mid == x) {
            return mid;
        } else if ((long)mid * mid > x) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return r;
}

二分查找

704. 二分查找 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 public int search(int[] nums, int target) {
    int l = 0, r = nums.length;
    while (l < r) {
        int mid = (l + r) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return -1;
}

搜索旋转排序数组

33. 搜索旋转排序数组 - 力扣（LeetCode）

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
public int search(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    // 第一次二分，找旋转点，就是第一个 < nums[0] 的
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (nums[mid] >= nums[0]) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    if (target >= nums[0]) {
        // 目标在左半边数组
        l = 0;
    } else {
        // 目标在右半边数组
        l = l + 1;
        r = nums.length - 1;
    }
    // 第二次二分，找目标，我们正常的有序数组的二分
    while (l < r) {
        int mid = (l + r) / 2;
        if (target > nums[mid]) {
            l = mid + 1;
        } else if (target <= nums[mid]) {
            r = mid;
        }
    }
    return nums[r] == target ? r : -1;
}

寻找旋转排序数组中的最小值 II

154. 寻找旋转排序数组中的最小值 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
public int findMin(int[] nums) {
    int l = 0;
    int r = nums.length - 1;
    // 二分法
    while (l < r) {
        int mid = l + (r - l) / 2;
        // 如果mid选择和右边界比较，当 mid 和 end相等时，mid向左看，一定是先局部下降的，所以可以end-- 找最小值
        if (nums[mid] > nums[r]) l = mid + 1;
        else if (nums[mid] < nums[r]) r = mid;
        else r--;
    }
    return nums[l];
}

双指针

  • 替换数组的两个位置的元素
  • 比较两个位置的元素是否相等

移动零

283. 移动零 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void moveZeroes(int[] nums) {
    // 左指针对准0，右指针对准非0
    int l = 0, r = 1;
    while (r < nums.length) {
        // 为0才有必要交换
        if(nums[l] == 0){
            // 找非0
            while (r < nums.length && nums[r] == 0) {
                r++;
            }
            // 替换0
            if(r < nums.length){
                nums[l] = nums[r];
                nums[r] = 0;
            }
        }
        //指针移动
        l++;
        r++;
    }
}

合并两个有序数组

88. 合并两个有序数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void merge(int[] nums1, int m, int[] nums2, int n) {
    // 倒序双指针
    int p1 = m - 1, p2 = n - 1;
    // 标记答案的指针，每次选出最大的放进去
    int tail = m + n - 1;
    // 最终选择的那个数
    int cur;
    while (p1 >= 0 || p2 >= 0) {
        // 一个选完了，直接放另一个
        if (p1 < 0) {
            cur = nums2[p2--];
        } else if (p2 < 0) {
            cur = nums1[p1--];
        }
        // 对比选择大的
        else if(nums1[p1] > nums2[p2]){
            cur = nums1[p1--];
        }else {
            cur = nums2[p2--];
        }
        nums1[tail--] = cur;
    }
}

按奇偶排序数组

905. 按奇偶排序数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] sortArrayByParity(int[] nums) {
    // 两个指针，如果左指针是奇数，同时右指针是偶数，交换
    int left = 0, right = nums.length - 1;
    while (left < right) {
        while (left < nums.length && nums[left] % 2 == 0) {
            left++;
        }
        while (right >= 0 && nums[right] % 2 == 1) {
            right--;
        }
        // 交换
        if (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        // 刨除这两个元素，继续交换
        left++;
        right--;
    }
    return nums;
}

删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode removeNthFromEnd(ListNode head, int n) {
    // 快慢指针，先让快指针走n + 1步，快指针为空的时候，用慢指针删除下一个节点
    // -1 1 2 3 4 5， n == 2
    // 虚拟头节点是为了不用区分删除头节点
    ListNode hair = new ListNode(-1, head);
    ListNode slow = hair, fast = hair;
    while (n-- >= 0) {
        fast = fast.next;
    }
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return hair.next;
}

环形链表 II

142. 环形链表 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode detectCycle(ListNode head) {
    // 环结构都可以用快慢指针，满指针一次走一步，快指针一次走两步
    // 数学推导，当快慢指针第一次相遇，只需要让两个指针，一个从起点开始走，一个从相遇点开始走，两个指针会在环的入口相遇
    ListNode slow = head, fast = head;
    // while循环的条件，首先是考虑遍历链表，即会不会无环
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            ListNode p1 = head;
            ListNode p2 = slow;
            while (p1 != p2) {
                p1 = p1.next;
                p2 = p2.next;
            }
            return p1;
        }
    }
    return null;
}

三数之和

15. 三数之和 - 力扣（LeetCode）

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
public List<List<Integer>> threeSum(int[] nums) {
    // 排序后的比较好用双指针
    // for遍历确定下第一个数 注意去重
    // 双指针确认后面的两个数值
    List<List<Integer>> res = new ArrayList();
    Arrays.sort(nums);
    for(int i = 0; i < nums.length; i++){
        // 去重，一定是在这个位置，和前一个位置（运动方向的反向）判断的
        if(nums[i] > 0) return res;
        if (i > 0 && nums[i] == nums[i - 1]) {  
            continue;
        }
        // 双指针
        int left = i + 1;
        int right = nums.length - 1;
        while(left < right){
            int sum = nums[i] + nums[left] + nums[right];
            if(sum < 0) left++;
            else if(sum > 0) right--;
            else {
                res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                // 为了避免出现重复答案，所以用了while
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                // 这里的可以是正常的添加完之后移动双指针
                // 或者是前面两个while，比如-1 0 1 1，然后经过了while右指针在第一个1，所以要移动两个指针
                left++;
                right--;
            }
        }
    }
    return res;
}

滑动窗口

  • 字符串的滑动窗口问题【也可以理解为字串的问题】：
    • 只有一个字符串：窗口内没有重复
    • 有两个字符串需要比对：找覆盖了目标串的窗口、和目标串相同字母的窗口
  • 数组的滑动窗口问题【也可以理解为子数组的问题】：窗口内的最大值、窗口的目标值为k

无重复字符的最长子串

3. 无重复字符的最长子串 - 力扣（LeetCode）

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
public int lengthOfLongestSubstring(String s) {
    Set<Character> map = new HashSet<>();
    // 维护窗口的指针
    int left = 0, right = 0;
    // 窗口的长度
    int len = 0;
    // 答案
    int ans = 0;
    char[] chars = s.toCharArray();
    while (right < chars.length) {
        // 窗口内有这个字符
        if (map.contains(chars[right])) {
            // 左指针一直移动到找到窗口内的同样字符
            while (chars[left] != chars[right]) {
                // 记得哈希表去掉
                map.remove(chars[left]);
                left++;
                len--;
            }
            // 去掉窗口的相同字符
            left++;
        } else {
            // 窗口内没有这个字符
            map.add(chars[right]);
            len++;
        }
        ans = Math.max(ans, len);
        // 右指针往后探
        right++;
    }
    return ans;
}

滑动窗口最大值

239. 滑动窗口最大值 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] maxSlidingWindow(int[] nums, int k) {
    // 递减队列保存的是下标
    Deque<Integer> queue = new LinkedList<>();
    int[] res = new int[nums.length - k + 1];
    for (int i = 0; i < nums.length; i++) {
        // 大值一定比小值先进入队列，否则小值不存在
        // 维护队列 -- 下标在窗口内
        while (!queue.isEmpty() && queue.peekFirst() < i - (k - 1)) {
            queue.pollFirst();
        }
        // 维护递减
        while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {
            queue.pollLast();
        }
        queue.offer(i);
        // 返回值
        if (i >= k - 1) {
            res[i - (k - 1)] = nums[queue.peekFirst()];
        }
    }
    return res;
}

找到字符串中所有字母异位词

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

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
public List<Integer> findAnagrams(String s, String p) {
    int sLen = s.length(), pLen = p.length();

    if (sLen < pLen) {
        return new ArrayList<Integer>();
    }

    List<Integer> ans = new ArrayList<Integer>();
    // 两个窗口
    int[] sCount = new int[26];
    int[] pCount = new int[26];
    for (int i = 0; i < pLen; ++i) {
        ++sCount[s.charAt(i) - 'a'];
        ++pCount[p.charAt(i) - 'a'];
    }
	// 每次都比较两个窗口（数组每个元素）是否相同
    if (Arrays.equals(sCount, pCount)) {
        ans.add(0);
    }

    for (int i = 0; i < sLen - pLen; ++i) {
        --sCount[s.charAt(i) - 'a'];
        ++sCount[s.charAt(i + pLen) - 'a'];

        if (Arrays.equals(sCount, pCount)) {
            ans.add(i + 1);
        }
    }

    return ans;
}

最小覆盖子串

76. 最小覆盖子串 - 力扣（LeetCode）

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 String minWindow(String s, String t) {
    // 还需要多少这个字符，负号表示不需要
    int[] need = new int[128];
    for (int i = 0; i < t.length(); i++) {
        need[t.charAt(i)]++;
    }
    int left = 0, right = 0;
    // 得出返回区间
    int start = 0;
    int len = Integer.MAX_VALUE;
    // count为窗口内的还需要的字符个数
    int count = t.length();
    while (right < s.length()) {
        char c = s.charAt(right);
        if (need[c] > 0) {
            count--;
        }
        need[c]--;
        if (count == 0) {
            // 去除不属于 t 的字符，缩小窗口长度
            while (left < right && need[s.charAt(left)] < 0) {
                need[s.charAt(left)]++;
                left++;
            }
            // 更新答案
            if (right - left + 1 < len) {
                len = right - left + 1;
                start = left;
            }
            // 维护窗口
            need[s.charAt(left)]++;
            left++;
            count++;
        }
        right++;
    }
    return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}

回溯算法

回溯算法的模板

循环的次数

确定返回的条件

剪枝优化

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

树枝去重和数层去重，used[i - 1]为true就是树枝，false就是数层

  1. 排列：

  2. 组合：

    我举过例子，如果是一个集合来求组合的话，就需要startIndex，例如：77.组合，216.组合总和III。

    如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合

    去重问题：数组排序才能去重

    有startIndex才能树枝去重，没有的话只能数层去重

    • used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
    • used[i - 1] == false，说明同一树层candidates[i - 1]使用过

  3. 子集：

  4. 分割字符串：和组合问题类似

  5. 棋盘：

括号生成

22. 括号生成 - 力扣（LeetCode）

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
List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder();

public List<String> generateParenthesis(int n) {
    backTracking(0, 0, n);
    return res;
}

public void backTracking(int left, int right, int n) {
    if (sb.length() == 2 * n) {
        res.add(new String(sb));
        return;
    }
    // 每层选左还是右
    // 先一直选左
    if (left < n) {
        sb.append("(");
        backTracking(left + 1, right, n);
        sb.deleteCharAt(sb.length() - 1);
    }
    // 回溯时当左大于右 可以把之前的选左换成选右
    if (left > right) {
        sb.append(")");
        backTracking(left, right + 1, n);
        sb.deleteCharAt(sb.length() - 1);
    }
}

全排列

46. 全排列 - 力扣（LeetCode）

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
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
boolean[] used;

public List<List<Integer>> permute(int[] nums) {
    used = new boolean[nums.length];
    backTraveling(nums);
    return res;
}

void backTraveling(int[] nums){
    if(path.size() == nums.length){
        res.add(new ArrayList<>(path));
        return;
    }
    // for循环就是树的一层
    for (int i = 0; i < nums.length; i++) {
        // 选过了不选
        if(used[i]) continue;
        used[i] = true;
        path.add(nums[i]);
        // 一次递归就进入树的下一层
        backTraveling(nums);
        path.removeLast();
        used[i] = false;
    }
}

全排列 II

47. 全排列 II - 力扣（LeetCode）

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
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
boolean[] used;

public List<List<Integer>> permuteUnique(int[] nums) {
    used = new boolean[nums.length];
    Arrays.sort(nums);
    backTraveling(nums);
    return res;
}

void backTraveling(int[] nums) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        // 树枝去重，每个位置在一个路径只能用一次
        if(used[i]) continue;
        // 数层去重，比如[1, 1, 2]，如果第一层选2，第二层只需要选一次1，!used[i - 1]保证不是树枝
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
        used[i] = true;
        path.add(nums[i]);
        backTraveling(nums);
        path.removeLast();
        used[i] = false;
    }
}

单词搜索

79. 单词搜索 - 力扣（LeetCode）

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
public boolean exist(char[][] board, String word) {
    for(int i = 0; i < board.length; i++) {
        for(int j = 0; j < board[0].length; j++) {
            if (backTracking(board, word, i, j, 0)) return true;
        }
    }
    return false;
}

// i,j是当前位置，index是当前位置要匹配word的字母
boolean backTracking(char[][] board, String word, int i, int j, int index) {
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || word.charAt(index) != board[i][j])
        return false;
    if (index == word.length() - 1) {
        return true;
    }
    boolean ans;
    char c = board[i][j];
    board[i][j] = ' ';
    ans = backTracking(board, word, i + 1, j, index + 1) ||
            backTracking(board, word, i - 1, j, index + 1) ||
            backTracking(board, word, i, j + 1, index + 1) ||
            backTracking(board, word, i, j - 1, index + 1);
    board[i][j] = c;
    return ans;
}

机器人的运动范围

LCR 130. 衣橱整理 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
boolean[][] visited;

public int wardrobeFinishing(int m, int n, int cnt) {
    visited = new boolean[m][n];
    // 这些位置是不可达的，先标记
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i / 10 + i % 10 + j / 10 + j % 10 > cnt) {
                visited[i][j] = true;
            }
        }
    }
    return dfs(0, 0, m, n);
}

int dfs(int i, int j, int m, int n) {
    // 位置不可达，中止条件
    if (i >= m || j >= n || visited[i][j]) {
        return 0;
    }
    // 记录访问过，避免重复访问
    visited[i][j] = true;
    return 1 + dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
}

复原 IP 地址

93. 复原 IP 地址 - 力扣（LeetCode）

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
List<String> ans;

public List<String> restoreIpAddresses(String s) {
    ans = new LinkedList<>();
    backTraveling(s, 0, 0);
    return ans;
}

void backTraveling(String s, int start, int pointNum) {
    if (pointNum == 3) {
        if (isValid(s, start, s.length() - 1)) {
            ans.add(s);
        }
        return;
    }
    for (int i = start; i < s.length(); i++) {
        if (!isValid(s, start, i)) break;                                             
        s = s.substring(0, i + 1) + "." + s.substring(i + 1);    //在str的后⾯插⼊⼀个逗点
        pointNum++;
        backTraveling(s, i + 2, pointNum);
        pointNum--;
        s = s.substring(0, i + 1) + s.substring(i + 2);// 回溯删掉逗点
    }
}

private boolean isValid(String s, int start, int end) {
    if (start > end) {
        return false;
    }
    if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
        return false;
    }
    int num = 0;
    for (int i = start; i <= end; i++) {
        if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法
            return false;
        }
        num = num * 10 + (s.charAt(i) - '0');
        if (num > 255) { // 如果⼤于255了不合法
            return false;
        }
    }
    return true;
}

贪心算法

局部最优解堆叠成全局最优解

动态规划

将问题拆成若干份小问题

  1. 确定dp的含义
  2. 用0边界确定初始化
  3. 列出状态方程
  4. 优化

爬楼梯

70. 爬楼梯 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
public int climbStairs(int n) {
    int[] dp = new int[n + 2];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        // 每一层由前一层、前两层上来
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

编辑距离

72. 编辑距离 - 力扣（LeetCode）

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
public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    // dp[i][j] 标识 word1从 0 ~ i-1 位变成 word2 的步数
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;
    }
    char[] arr1 = word1.toCharArray();
    char[] arr2 = word2.toCharArray();
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // 两个指针对比字符相同
            if (arr1[i - 1] == arr2[j - 1]) {
                // 什么都不用干
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 进行替换、增加、删除
                // 步数 + 1
                dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
            }
        }
    }
    return dp[m][n];
}

最长公共子序列

1143. 最长公共子序列 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length();
    int n = text2.length();
    // 标识 0~i-1 与 0~j-1 的最长公共子序列
    int[][] dp = new int[m + 1][n + 1];
    // 初始化：由于当一方为0，没有交集，不用初始化
    char[] s1 = text1.toCharArray();
    char[] s2 = text2.toCharArray();
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // 两个指针对比字符相同
            if (s1[i - 1] == s2[j - 1]) {
                // 长度 + 1
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // 取之前的最大值
                dp[i][j] = Math.max(dp[i - 1][j - 1], Math.max(dp[i - 1][j], dp[i][j - 1]));
            }
        }
    }
    return dp[m][n];
}

统计结果概率

LCR 185. 统计结果概率 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public double[] statisticsProbability(int num) {
    // 当 i == 1，初始化 1 个骰子的概率
    double[] pre = {1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d};
    for (int i = 2; i <= num; i++) {
        double[] cur = new double[6 * i - (i - 1)];
        // 当前 i 个骰子，拆成 i - 1 个骰子的点数 + 1 个骰子的点数
        for (int j = 0; j < pre.length; j++) {
            for (int k = 0; k < 6; k++) {
                // 比如说 10 点的概率 == 所有可能的 前 i - 1 个骰子的概率 * 1 个骰子的概率(1/6)
                cur[j + k] += pre[j] * (1 / 6d);
            }
        }
        pre = cur;
    }
    return pre;
}

整数拆分

343. 整数拆分 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int integerBreak(int n) {
    int[] dp = new int[n + 1];
    // 2 = 1 + 1，1 * 1 = 1
    dp[2] = 1;
    // 从dp[3]开始
    for (int i = 3; i <= n; i++) {
        // i == j + (i - j)
        // dp[i] = dp[j] + dp[i - j]
        for (int j = 1; j <= i - j; j++) {
            dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
        }
    }
    return dp[n];
}

解码方法

91. 解码方法 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int numDecodings(String s) {
    int[] dp = new int[s.length() + 1];
    // 空字符串可以有 1 种解码方法，解码出一个空字符串
    dp[0] = 1;
    for (int i = 1; i <= s.length(); i++) {
        if (s.charAt(i - 1) != '0') {
            dp[i] += dp[i - 1];
        }
        if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0')) <= 26) {
            dp[i] += dp[i - 2];
        }
    }
    return dp[s.length()];
}

珠宝的最高价值

LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
public int jewelleryValue(int[][] frame) {
    int m = frame.length, n = frame[0].length;
    int[][] dp = new int[m + 1][n + 1];
    // dp只和上面和左边有关，所以都是0，也就不用初始化了
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
        }
    }
    return dp[m][n];
}

打家劫舍

股票

买卖股票的最佳时机

121. 买卖股票的最佳时机 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxProfit(int[] prices) {
    // 0是没有，1是有，dp[i][j]：下标为 i 这一天结束的时候，手上持股状态为 j 时，我们持有的现金数
    int[][] dp = new int[prices.length][2];
	// 初始化
    dp[0][0] = -prices[0];
    dp[0][1] = 0;

    for (int i = 1; i < prices.length; i++) {
        // 第i天有股票，是从第i-1天本来就有，第i-1天没有，今天买的
        // 第i天有股票，是从第i-1天本来就没有，第i-1天有，今天卖的
        dp[i][0] = Math.max(dp[i - 1][0], - prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
    }

    return dp[prices.length - 1][1];
}

子序列，子数组

一个序列 or 数组，可能和前面任何一个位置的状态都有关

两个序列 or 数组，只和 dp[i - 1][j - 1]、dp[i][j - 1]、dp[i - 1][j]有关

dp[i][j]表示的意思是s的前i个字母中匹配t的前j个字母的字母个数，或者是总数

最长递增子序列

300. 最长递增子序列 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int lengthOfLIS(int[] nums) {
    // dp 代表当前这个数在末尾的子序列长度
    int[] dp = new int[nums.length];
    int ans = Integer.MIN_VALUE;
    // 初始化
    Arrays.fill(dp, 1);
    for (int i = 1; i < nums.length; i++) {
        // 遍历前面的每一个数字
        for (int j = 0; j < i; j++) {
            // 当前数字比前面的数字大，才说明可以成为一个递增子序列
            if (nums[i] > nums[j]) {
                // 修改 dp[]
                dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
        }
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}

最大子数组和

53. 最大子数组和 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
public int maxSubArray(int[] nums) {
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int res = dp[0];
    for (int i = 1; i < nums.length; i++) {
        // 状态转移方程
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        res = Math.max(res, dp[i]);
    }

    return res;
}
1
2
3
4
5
6
7
8
9
10
public int maxSubArray(int[] nums) {
    // 常量代替数组
    int x = nums[0];
    int res = nums[0];
    for (int i = 1; i < nums.length; i++) {
        x = Math.max(x + nums[i], nums[i]);
        res = Math.max(x, res);
    }
    return res;
}

数位dp

数字 1 的个数

233. 数字 1 的个数 - 力扣（LeetCode）

密码锁法，用 cur 区分左右两边的数字

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
 public int countDigitOne(int n) {
    int res = 0;
    int high = n / 10;
    int cur = n % 10;
    int low = 0;
    int digit = 1; // 求个位的 1 的个数
    while (high != 0 || cur != 0) {
        if (cur == 0) {
            // 1204 假设当前 cur == 0，digit == 10
            // 其他三位从 000 ~ 124 出现了 12次 xx10 ~ xx19，即十位出现 120次 1
            res += high * digit;
        } else if (cur == 1) {
            // 1214 假设当前 cur == 1，digit == 10
            // 其他三位从 000 ~ 124 出现了 12次 xx10 ~ xx19，和 0 ~ 4 次 1，即十位出现 120 + 5 次 1
            res += high * digit + low + 1;
        } else {
            // 1234 假设当前 cur == 3，digit == 10
            // 其他三位从 000 ~ 124 出现了 13次 xx10 ~ xx19，即十位出现 130次 1
            res += (high + 1) * digit;
        }
        // low 的位数 + 1
        low += cur * digit;
        // cur 往左移动
        cur = high % 10;
        // high 的位数 - 1
        high /= 10;
        digit *= 10;
    }
    return res;
}

排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 0; i < 10; i++) {
    for (int j = 1; j < 10 - i; j++) {
        if (nums[j - 1] > nums[j]) {
            swap(nums, j - 1, j);
        }
    }
}

private static void swap(int[] nums, int i, int j) {
    int temp = nums[i] ^ nums[j];
    nums[i] = temp ^ nums[i];
    nums[j] = temp ^ nums[j];
}

快速排序

以第一个数为基准的写法

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
private static void quicksort(int[] nums) {
    sort(nums, 0, nums.length - 1);
}

private static void sort(int[] nums, int l, int r) {
    if (l >= r) return;
    // 递归排序基数
    int index = partition(nums, l, r);
    // 递归排序基数左边的数组
    sort(nums, l, index - 1);
    // 递归排序基数右边的数组
    sort(nums, index + 1, r);
}
// 递归排序基数
private static int partition(int[] nums, int l, int r) {
    // 第一个数最为基准数
    int temp = nums[l];
    int i = l, j = r;
    while (i < j) {
        // 找到第一个比temp小的数字
        while (nums[j] >= temp && i < j) {
            j--;
        }
        // 找到第一个比temp大的数字
        while (nums[i] <= temp && i < j) {
            i++;
        }
        swap(nums, i, j);
    }
    // 将基准数交换到合适的位置，如果数组本身有序，可能自己和自己交换
    swap(nums, l, i);
    return i;
}

private static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

三路快排优化

前端学习数据结构与算法系列(八)：快速排序与三路快排-腾讯云开发者社区-腾讯云 (tencent.com)

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
public int[] sortArray(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums;
}

private void quickSort(int[] nums, int l, int r) {
    // 终止条件
    if (l >= r) return;
    // 递归排序基数
    int[] index = partition(nums, l, r);
    // 递归排序基数左边的数组
    quickSort(nums, l, index[0]);
    // 递归排序基数右边的数组
    quickSort(nums, index[1], r);
}

private int[] partition(int[] nums, int l, int r) {
    int base = nums[l];
    // 总共3个区间，<p、==p、>p
    // lt代表的是<p的右边界，gt代表的是>p的左边界
    // 初始化标识三个区间都是0
    int lt = l, gt = r + 1;
    for (int i = l + 1; i < gt; ) {
        if (nums[i] == base) {
            i++;
        } else if (nums[i] > base) {
            // 不 i++的原因是，i位置要一直换，直到拿到小的
            swap(nums, gt - 1, i);
            gt--;
        } else {
            // i++的原因是，lt前面的数已经是符合条件的<p，所以换个<p的过来没问题
            swap(nums, lt + 1, i);
            lt++;
            i++;
        }
    }
    // 只剩下基准值没有交换了
    swap(nums, l, lt);
    lt--;
    return new int[]{lt, gt};
}

void swap(int[] nums, int left, int right) {
    int temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
}

归并排序

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 static void gbSort(int[] nums){
    sort(nums, 0, nums.length - 1);
}

public static void sort(int[] nums, int l, int r) {
    if (l >= r) return;

    int mid = l + (r - l) / 2;
    // 分
    sort(nums, l, mid);
    sort(nums, mid + 1, r);
    // 治
    merge(nums, l, mid, r);
}

private static void merge(int[] nums, int l, int mid, int r) {
    int[] temp = new int[nums.length];
    int i = l, j = mid + 1;
    // 区间的左边界
    int index = l;
    // 合并子数组，l 到 mid 是左数组，mid + 1 到 r 是右数组
    while (i <= mid && j <= r) {
        if (nums[i] < nums[j]) {
            temp[index++] = nums[i++];
        } else {
            temp[index++] = nums[j++];
        }
    }
    while (i <= mid) {
        temp[index++] = nums[i++];
    }
    while (j <= r) {
        temp[index++] = nums[j++];
    }
    // 代替原来这个区间的的无序子数组
    for (int k = l; k <= r; k++) {
        nums[k] = temp[k];
    }
}

进制和位运算

二进制中1的个数

191. 位1的个数 - 力扣（LeetCode）

循环遍历法

1
2
3
4
5
6
7
8
public int hammingWeight(int n) {
    int count = 0;
    // 每次和一位进行与操作
    for (int i = 0; i < 32; i++) {
        if ((n & (1 << i)) != 0) count++;
    }
    return count;
}

位运算优化

1
2
3
4
5
6
7
8
9
10
public int hammingWeight(int n) {
    int count = 0;
    // n & (n - 1) 可以把最后一个1去掉
    // 不断循环去1
    while (n != 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

Pow(x, n)

50. Pow(x, n) - 力扣（LeetCode）

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public double myPow(double x, int n) {
    long N = n;
    return N > 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}

private double quickMul(double x, long N) {
    // 递归中止条件
    if (N == 0) return 1.0;
    // 分治
    double y = quickMul(x, N / 2);
    // 偶数次幂
    // x^6 == x^3 * x^3
    if (N % 2 == 0) {
        return y * y;
    } else {
        return y * y * x;
    }
}

二进制拆解法

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
public double myPow(double x, int n) {
    long N = n;
    return N > 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}

private double quickMul(double x, long N) {
    double ans = 1.0;
    // 初始贡献值
    double x_contribution = x;
    // 77 = (1001101)
    // x^77 = x * x^4 * x^8 * x^64
    while (N > 0) {
        // 是1才需要记录贡献
        if (N % 2 == 1) {
            ans *= x_contribution;
        }
        // 从右向左，每一位的贡献都是右一位的两倍
        x_contribution *= x_contribution;
        N /= 2;
    }
    return ans;
}

// 骚的
public double myPow(double x, int n) {
    long N = n;
    return N > 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}

private double quickMul(double x, long N) {
   double ans = 1.0;
    // 初始贡献值
    double x_contribution = x;
    // 77 = (1001101)
    // x^77 = x * x^4 * x^8 * x^64
    while (N > 0) {
        // 是1才需要记录贡献
        // 和hashmap计算下标一样的操作
        if ((N & 1) == 1) {
            ans *= x_contribution;
        }
        // 从右向左，每一位的贡献都是右一位的两倍
        x_contribution *= x_contribution;
        N >>= 1;
    }
    return ans;
}

只出现一次的数字 III

260. 只出现一次的数字 III - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] singleNumber(int[] nums) {
    int xor = 0;
    for (int num : nums) {
        xor ^= num;
    }
    // 经过上述计算，现在的 xor 不为 0
    // 可以发现这两个只出现1次的数在某一位 异或 为 1，通过这一位 1 可以把他们分成两组
    // 不妨找出最右边的 1 ，xor & (-xor) 即 xxx1000 & (xxx0111 + 1)
    int lsb = xor & (-xor);
    int ans1 = 0, ans2 = 0;
    for (int num : nums) {
        if ((num & lsb) != 0) {
            ans1 ^= num;
        } else {
            ans2 ^= num;
        }
    }
    return new int[]{ans1, ans2};
}

其它

轮转数组

189. 轮转数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void rotate(int[] nums, int k) {
    k %= nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
}

public void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

比较版本号

165. 比较版本号 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int compareVersion(String version1, String version2) {
    // 切割字符串
    String[] ss1 = version1.split("\\."), ss2 = version2.split("\\.");
    int n = ss1.length, m = ss2.length;
    int i = 0, j = 0;
    // 每一部分对位比较
    while (i < n || j < m) {
        int a = 0, b = 0;
        if (i < n) a = Integer.parseInt(ss1[i++]);
        if (j < m) b = Integer.parseInt(ss2[j++]);
        if (a != b) return a > b ? 1 : -1;
    }
    return 0;
}

文物朝代判断

LCR 186. 文物朝代判断 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean checkDynasty(int[] places) {
    Arrays.sort(places);
    // 0的数量
    int count = 0;
    // 最大牌位置在最后，那么最小牌位置在 0 + count
    for (int i = 0; i < places.length - 1; i++) {
        if (places[i] == 0) count++;
        // 不能重复
        else if (places[i] == places[i + 1]) return false;
    }
    // 6 7 8 9 10 第一个非0和最大数相差 <= 4，全是0也是对的
    return places[4] - places[count] <= 4;
}

设计机械累加器

LCR 189. 设计机械累加器 - 力扣（LeetCode）

1
2
3
4
public int mechanicalAccumulator(int target) {
    boolean x = target > 1 && (target += mechanicalAccumulator(target - 1)) > 0;
    return target;
}

破冰游戏

LCR 187. 破冰游戏 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
public int iceBreakingGame(int num, int target) {
    // 最后一个人的位置一定是0
     int ans = 0;
    // 最后一轮剩下2个人s，所以从2开始反推
    for (int i = 2; i <= num; i++) {
        ans = (ans + target) % i; // 每次循环右移，把杀的人补回去，改变活着的人的位置
    } 
    return ans;
}

多数元素

169. 多数元素 - 力扣（LeetCode）

占领高地法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int majorityElement(int[] nums) {
    int ans = 0;
    // 占领高地法，最后一定是多数元素占领高地
    int count = 0;
    // 每次派一个士兵冲上高地
    for(int i = 0; i < nums.length; i++){
        // 没人就标记我方占领高地
        if(count == 0){
            ans = nums[i];
        }
        // 发现是队友，则我军人数+1
        if(ans == nums[i]){
            count++;
        }else{
            // 否则换掉对方一个人
            count--;
        }
    }
    return ans;
}

多数元素 II

229. 多数元素 II - 力扣（LeetCode）

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
public List<Integer> majorityElement(int[] nums) {
    int element1 = 0;
    int element2 = 0;
    int count1 = 0;
    int count2 = 0;
    for (int num : nums) {
        // 每次都增强友军或者增强盟军
        if (count1 > 0 && num == element1) {
            count1++;
        } else if (count2 > 0 && num == element2) {
            count2++;
        } else if (count1 == 0) {
            element1 = num;
            count1++;
        } else if (count2 == 0) {
            element2 = num;
            count2++;
        } 
        // 如果和两军都敌对，则相互抵消1次
        else {
            count1--;
            count2--;
        }
    }
    int cnt1 = 0;
    int cnt2 = 0;
    for (int num : nums) {
        if (count1 > 0 && num == element1) {
            cnt1++;
        }
        if (count2 > 0 && num == element2) {
            cnt2++;
        }
    }
    // 检测元素出现的次数是否满足要求
    List<Integer> res = new ArrayList<>();
    if (count1 > 0 && cnt1 > nums.length / 3) {
        res.add(element1);
    }
    if (count2 > 0 && cnt2 > nums.length / 3) {
        res.add(element2);
    }

    return res;
}