本文准备把常见的算法题中，不同的题型进行分类整理，相信将相同类型的思路放在一起能够起到事半功倍的效果。本分类很大程度参考了灵神的题单和题解，感谢灵神！

遍历和哈希表

1. 两数之和

梦开始的地方，利用哈希表将2次遍历简化为1次。我们采用枚举右，寻找左的方法，将当前遍历到的 j 作为两数中的一个，去哈希表中寻找左边的另一个数 target - j，如果能找到就是一个解；然后将自身添加到哈希表中，等待后续右边的数来找自己。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> idx = new HashMap<>(); // 创建一个空哈希表
        for (int j = 0; ; j++) { // 枚举 j
            int x = nums[j];
            // 在左边找 nums[i]，满足 nums[i]+x=target
            if (idx.containsKey(target - x)) { // 找到了
                return new int[]{idx.get(target - x), j}; // 返回两个数的下标
            }
            idx.put(x, j); // 保存 nums[j] 和 j
        }
    }
}

前缀和

303. 区域和检索 - 数组不可变

核心是“任意子数组的和，都可以表示为两个前缀和的差”，前缀和数组得开辟 n+1 长度，并且定义 pres[i] 为 [0,i-1] 范围内的元素和（或者理解为 i 个数字的和），并令 pres[0]=0 表示零个数字的和，想象如下两个数组：

1
2
[_, 0, 1, 2, 3, ...] : 原数组nums
[0, 1, 2, 3, 4, ...] : 前缀和pres

从而任意闭区间子数组的和：nums[i] + ... + nums[j] = pres[j + 1] - pres[i]，考虑特殊情况 nums[0] = pres[1] - pres[0]

560. 和为 K 的子数组

两数之和的思想“枚举右，维护左”：当枚举到右边界 j 时，当前的前缀和 pre[j] 是一个确定的数值，目标和 k 也是常量。此时我们唯一的未知数是左边界 i 及其对应的前缀和 pre[i]。为了找到满足条件的子数组，我们将公式变形为 pre[i] = pre[j] - k。这个变形意味着：为了让子数组和为 k，我们必须在当前位置 j 之前，找到一个特定的前缀和值，这个值必须等于 pre[j] - k。
哈希表中存放的元素是历史数据，即从索引 0 到 j-1 的所有前缀和出现的次数。这对应了“维护左”的操作：随着 j 的向右移动，每一个计算过的 pre[j] 都会在下一轮循环中变成历史（即可能的 pre[i]），因此需要被存入哈希表以供未来查询。哈希表存在的意义就是记录过去所有可能的“切入点”状态。

437. 路径总和 III

这题必须一边求前缀和，一边枚举路径的终点，并用哈希表来看之前有多少个起点是满足条件的。

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
class Solution {
    private int targetSum;
    private Map<Long, Integer> hashMap;
    private int ans = 0;

    public int pathSum(TreeNode root, int targetSum) {
        this.targetSum = targetSum;
        hashMap = new HashMap<>();
        hashMap.put(0L, 1); // 先将虚拟前缀和0补齐，需要累加的次数为1
        this.dfs(root, 0);
        return this.ans;
    }

    private void dfs(TreeNode node, long prefixSum) {
        if (node == null) { return; }
        
        prefixSum += node.val;
        // 每次计算最终答案时，使用的当前前缀和prefixSum。必须保证当前的没加到哈希表中；而上个前缀和肯定已经被加到哈希表中
        this.ans += hashMap.getOrDefault(prefixSum - this.targetSum, 0);

        hashMap.put(prefixSum, 1 + hashMap.getOrDefault(prefixSum, 0));
        this.dfs(node.left, prefixSum);
        this.dfs(node.right, prefixSum);
        hashMap.put(prefixSum, hashMap.get(prefixSum) - 1); // 回溯当前的值，至少为1
    }
}

304. 二维区域和检索 - 矩阵不可变

这个题是二维的前缀和问题，用到了类似容斥原理的内容，建议查看灵神的题解，讲的非常清晰

可以再看看此题 221. 最大正方形，是类似的思想，但是动态规划题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class NumMatrix {
    int[][] prefixSum;
    public NumMatrix(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        prefixSum = new int[n + 1][m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                prefixSum[i + 1][j + 1] = prefixSum[i][j + 1] + prefixSum[i + 1][j] - prefixSum[i][j] + matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return prefixSum[row2 + 1][col2 + 1] - prefixSum[row1][col2 + 1] - prefixSum[row2 + 1][col1] + prefixSum[row1][col1];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

滑动窗口

定长滑动窗口

1456. 定长子串中元音的最大数目

可以背一下模板，如果窗口大小为 k，总长度为 n，则：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = nums.length; // 数组长度
j = 0; // 窗口的右边界
for 0 <= j < n {
	1. 右端点进入窗口，例如累加值，算最值等等
	
	i = j - k + 1;
	if (i < 0) {
		continue; // 窗口大小还没有到k，不进行统计
	}
	
	2. 操作ans，此时是一个合法的窗口
	
	3. 左端点离开窗口
}

76. 最小覆盖子串

写一个方法比较两个哈希表是否相等，每一次移动左端点都需要遍历子串中的字母类型数量，复杂度挺高；

可以使用一个 less 变量将这部分复杂度优化到 O(1)，该变量维护目前子串中有 less 种字母的出现次数小于 t 中字母的出现次数，初始值为 t 中不同字母个数。字母数的哈希表仍要维护，初始为 t 的情况，每次在 p 中遇到相应字母则减一，减完后如果为零，说明这类字母已经被覆盖了，此时 less 减一（有可能被减到负值，但我们只关注到达零时的那一次）；当 less 被减到零时，说明全被覆盖了，此时就右移左端点，并让字母数的哈希表中的相应字母自增（有可能是无关字母，这些字母不管），如果自增前是零，说明马上要缺少一类字母被覆盖，需要将 less 加一，这时候又该继续右移右端点了

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
class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> tMap = new HashMap<>();
        char[] sc = s.toCharArray(), tc = t.toCharArray();
        for (int i = 0; i < tc.length; i++) {
            tMap.put(tc[i], tMap.getOrDefault(tc[i], 0) + 1);
        }
        int less = tMap.size(), ans = sc.length + 1; // less表示子串还剩多少种字母没有覆盖目标字符串t
        String ansStr = "";
        Map<Character, Integer> sMap = new HashMap<>(tMap);
        int i = 0;
        for (int j = 0; j < sc.length; j++) {
            sMap.put(sc[j], sMap.getOrDefault(sc[j], 0) - 1);
            if (sMap.get(sc[j]) == 0) {
                less--;
            }
            while (less == 0) {
                if (j - i + 1 < ans) {
                    ans = j - i + 1;
                    ansStr = s.substring(i, j + 1);
                }
                if (sMap.get(sc[i]) == 0) {
                    less++;
                }
                sMap.put(sc[i], sMap.getOrDefault(sc[i], 0) + 1);
                i++;
            }
        }
        return ansStr;
    }
}

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

两种方法，定长滑窗和不定长滑窗。定长滑窗和76. 最小覆盖子串完全一致，就不展开了；不定长的方法，和[3. 无重复字符的最长子串]有点像，这题算是面试top1高频的题了。

变长滑动窗口

模板还是类似定长滑动窗口的，但是左端点就不是直接从右端点算得了，而是要不断右移，直到满足/不满足条件。

3. 无重复字符的最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> mp = new HashMap<>();
        int i = 0, ans = 0; // 最小的答案是0，此时为空串；否则至少是1
        char[] sc = s.toCharArray();
        for (int j = 0; j < sc.length; j++) {
            mp.put(sc[j], mp.getOrDefault(sc[j], 0) + 1);
            // 造成重复的必然是当前新增的，因此不断缩短左端点，直到当前新增的sc[j]不再重复
            while (mp.get(sc[j]) > 1) {
                mp.put(sc[i], mp.get(sc[i]) - 1);
                i++;
            }
            ans = Math.max(ans, j - i + 1);
        }
        return ans;
    }
}

713. 乘积小于 K 的子数组

越短越合法，因此找到个最长的合法子数组，并计算比它短的子数组的个数。注意此处枚举右端点，所以每次计算时要固定右端点，否则会重复计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) { return 0; }
        int prod = 1, n = nums.length;
        int i = 0, ans = 0;
        for (int j = 0; j < n; j++) {
            prod *= nums[j];
            while (prod >= k) {
                prod /= nums[i++];
            }
            // 此时[i,j]满足要求，因此固定j后将i向右偏移的所有子数组都满足要求
            // 因为枚举的是j，所以要固定j，否则会多算
            ans += j - i + 1; // [i,j] ... [j,j]
        }
        return ans;
    }
}

双指针

283. 移动零

这个题我自己第一遍的方法是让两个指针分别指向为零、不为零的元素，并进行交换，但是下面两种做法感觉更精妙，来自灵神。
方法一，把原来的数组直接当成栈，用一个变量维护非零元素的个数，这个变量即为栈顶；遍历完原数组后，把末尾用零元素补齐。该方法在数组全零的情况下最多可能要遍历两次。
方法二，双指针 i0 和 i，维护一个 [i0, i) 的零区间，初始 i0 = i = 0 区间为空。当 i 找到非零元素时，和 i0 交换位置，并同时自增 1；如果 i 遇到零元素，则继续往右移动。

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 void moveZeroes(int[] nums) {
    int stackSize = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            nums[stackSize++] = nums[i];
        }
    }
    while (stackSize < nums.length) {
        nums[stackSize++] = 0;
    }
}
// 方法二：双指针
public void moveZeroes(int[] nums) {
    int i0 = 0, i = 0; // 维护 [i0, i) 为零区间
    for (; i < nums.length; i++) {
        if (nums[i] != 0) {
            int tmp = nums[i];
            nums[i] = nums[i0];
            nums[i0] = tmp;
            i0++;
        }
    }
}

31. 下一个排列

这个题就是要背住做法，或者说背住推导方式。

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
class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return;
        }
        // 1. 寻找nums[i] < nums[i + 1]
        int i = n - 2;
        while (i >= 0 && nums[i] > nums[i + 1]) {
            i--;
        }
        if (i < 0) {
            reverse(nums, 0, n - 1);
            return;
        }
        
        // 2. 寻找nums[i]右侧最小的大于nums[i]的数，至少nums[i + 1] > nums[i]
        // 右侧又是递减的，所以找到第一个小于nums[i]的数，前一个就是
        int j = i + 1;
        while (j < n && nums[j] > nums[i]) {
            j++;
        }
        j--;
        
        // 3. 交换后将后面部分逆序
        swap(nums, i, j);
        reverse(nums, i + 1, n - 1);
    }

    void reverse(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i++, j--);
        }
    }

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

链表

链表的操作就那么几个，很简单但熟练度要高。

反转链表

这个题要注意，链表长度为 n 的话，反转的循环体就执行 n 次，但直接看链表的话好像反转 n - 1 次就够了，这个链表只有两个“->”：0 -> 1 -> 2；但我们得把 null 算进去，相当于本来在尾部的 null 变到头部去了，即：0 -> 1 -> 2 变成 null <- 0 <- 1 <- 2，所以就是要反转 n = 3 次。

还要注意循环不变量，即 pre 和 cur，最开始是 pre 为 null 和 cur 为 head，最后 cur 为 null 和 pre 为 head，所以最后直接返回 pre 即可。这在后面问题的下标处理上比较重要。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ListNode reverseList(ListNode head) {
    // 反转链表无需dummyHead，需要操作n次，其中n是链表长度。
    ListNode pre = null, cur = head;
    int cnt = 0; // 用于验证操作次数
    // 循环终止时，cur为null，pre为last node，也即反转后的头结点
    while (cur != null) {
        cnt++;
        ListNode nxt = cur.next; // 记录一下
        cur.next = pre; // 首次执行循环，pre为null
        pre = cur;
        cur = nxt;
    }
    System.out.printf("%s\n", cnt);
    return pre;
}

92. 反转链表 II

要先找到目标链表的头结点的前一个 node，那么如果目标链表就是第一个，无法统一编码，因此引入冗余头结点；
从冗余头结点开始，操作 n 次 .next，就到达第 n 个节点，因此操作 left - 1 次到达第 left 个节点的前一个；
链表的长度是闭区间 [left, right]，长度为 right - left + 1，所以循环体要循环这么多次；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummyHead = new ListNode(-1, head);
    ListNode p0 = dummyHead;
    for (int i = 0; i < left - 1; i++) {
        p0 = p0.next;
    }

    // 下面和普通反转一致，注意pre无需设置为p0，因为p0的next应该是反转结束后的头结点pre
    ListNode pre = null, cur = p0.next;
    for (int i = 0; i < right - left + 1; i++) {
        ListNode nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }

    // 此时pre是反转后的头结点，cur是下一个
    p0.next.next = cur;
    p0.next = pre;
    return dummyHead.next;
}

25. K 个一组翻转链表

如果能在短时间内熟练手敲出这个题，链表的所有题基本问题不大了，最怕面试时调试半天。

同样是需要设置冗余头节点 dummyHead；注意 p0 的含义，是要进行反转操作的闭区间 [left, right] 的前一个节点，反转是和上面的题类似的，但是反转结束后要将 p0 设置为下一个要反转的起点，即：

p0 -> 2 -> 3 -> 4 反转 2 和 3 后是 p0 -> 2 <- 3 -> 4，此时的 pre = 3, cur = 4，要将 p0.next.next 指向 cur = 4，p0.next 指向 pre = 3，而下一个 p0 是旧的 p0.next = 2

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 ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummyHead = new ListNode(-1, head);
    int n = 0;
    while (head != null) {
        n++;
        head = head.next;
    }

    ListNode p0 = dummyHead;
    for (int i = 0; i < n / k; i++) {
        ListNode pre = null, cur = p0.next;
        for (int j = 0; j < k; j++) { // 长度为k需反转k次
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        p0.next.next = cur;
        ListNode p0Next = p0.next; // 暂存下一个p0的值
        p0.next = pre;

        p0 = p0Next;
    }

    return dummyHead.next;
}

142. 环形链表 II

这个题直接背下来还是挺方便的，无非是快慢指针一起走，如果会相遇则存在环。此时将头结点和慢指针同步走，他们相遇的节点就是环的入口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) { return null; }
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                // 相遇后，让慢指针和头指针直接一起走
                while (head != slow) {
                    head = head.next;
                    slow = slow.next;
                }
                return head;
            }
        }
        return null;
    }
}

147. 对链表进行插入排序

由于每次 curNode 可能会被插入到链表之中，更新时不能使用 curNode = curNode.next，而是应该维护一个 lastSorted 作为已排序链表的末尾，使用 curNode = lastSorted.next 进行更新；
每次遇到 curNode 时，根据它是否比 lastSorted 大，来决定是否要进行插入操作；这样的话，每次执行插入操作时，必然是在 lastSorted 之前的位置，就不会乱掉了。

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 ListNode insertionSortList(ListNode head) {
    ListNode dummyHead = new ListNode(-1, head);
    ListNode curNode = head.next, lastSorted = head;
    while (curNode != null) {        
        if (lastSorted.val <= curNode.val) { // 1. 下一个节点已经大于有序链表的最后一个节点，直接不用插入
            lastSorted = lastSorted.next;
        } else { // 此处必然执行插入操作
            ListNode tarNode = dummyHead;
            // 已经特判过curNode.val并不比lastSorted大
            // 至少当tarNode.next为lastSorted时，会停下来，不可能tarNode.next=curNode
            while (tarNode.next.val <= curNode.val) {
                tarNode = tarNode.next;
            }
            // 此时必然tarNode.next.val > curNode.val
            // 因此将curNode插入到tarNode和tarNode.next之间
            // 1. 将curNode删除
            lastSorted.next = curNode.next;
            // 2. 将curNode插入
            curNode.next = tarNode.next;
            tarNode.next = curNode;
        }
        // 始终是有序链表末节点的下一个(lastSorted.next)，而不是当前节点的下一个(curNode.next)
        curNode = lastSorted.next;
    }
    return dummyHead.next;
}

148. 排序链表

经典归并算法，这里用的是递归实现的分治法，需要额外的空间；也可以用自底向上的迭代法，这个比较复杂就先不考虑了。
注意事项是，从中间断开时，如果是偶数，要取左侧的中间结点，否则必然左边偏长；边界情况是只有1个节点或链表为空；有序链表的合并也是比较高频的题，要保证快速写出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public ListNode sortList(ListNode head) {
        // 链表长度为0或1时无需排序
        if (head == null || head.next == null) {
            return head;
        }

        ListNode midNode = this.middleNode(head);
        ListNode head2 = midNode.next;
        midNode.next = null; // 断开，否则无法判断链表终止

        head = this.sortList(head);
        head2 = this.sortList(head2);

        return this.mergeTwoLists(head, head2);
    }

    // [876. 链表的中间结点]的变种：在偶数时需要取左边的，而非右边的
    public ListNode middleNode(ListNode head) {
        // 想象只有两个节点的链表
        // ListNode slow = head, fast = head; // 偶数时取右侧
        ListNode slow = head, fast = head.next; // 偶数时取左侧
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // [21. 合并两个有序链表]
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode curNode = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                curNode.next = list1;
                list1 = list1.next;
            } else { // 相等的情况可放在任意一侧
                curNode.next = list2;
                list2 = list2.next;
            }
            curNode = curNode.next;            
        }
        curNode.next = list1 == null ? list2 : list1;
        return dummyHead.next;
    }
}

23. 合并 K 个升序链表

这个题可以用最小堆来完成，写法比较简单，注意所用语言是如何定义最小堆的；也可以分治法来做，即类似两两合并、四四合并、八八合并的思想。

146. LRU 缓存

标准库写法：需要重载 protect boolean removeEldestEntry()，返回值表示是否删除 eldest 元素，默认返回 false，需要重载为“超过容量时返回 true”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class LRUCache {
    private final LinkedHashMap<Integer, Integer> mp;
    public LRUCache(int capacity) {
        // initialCapacity=capacity代表容量，loadFactor=0.75F代表加载因子，
        // accessOrder默认为false，表示按存入的顺序；设置为true表示按读取顺序
        this.mp = new LinkedHashMap<>(capacity, 0.75F, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }
    
    public int get(int key) {
        return this.mp.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        this.mp.put(key, value);
    }
}

当然，标准库写法还可以直接继承，这里就不展示了
下面是直接手撕双向链表的方法，注意使用1个冗余头结点就足够了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class LRUCache {
    static class Node {
        int key, val;
        Node prev, next;
        public Node(int key, int val) {
            this.key = key; // 必须要有key，否则删除尾部时，不知道如何从hashmap中删除
            this.val = val;
        }
    }

    private final Map<Integer, Node> hashMap;
    private final Node dummyHead;
    private final int capacity;

    public LRUCache(int capacity) {
        this.hashMap = new HashMap<>(); // 负载因子0.75F
        this.capacity = capacity;
        this.dummyHead = new Node(-1, -1); // 使用一个冗余头结点足够了
        dummyHead.prev = dummyHead;
        dummyHead.next = dummyHead;
    }
    
    public int get(int key) {
        Node tarNode = hashMap.get(key);
        if (tarNode == null) {
            return -1;
        }
        // 存在，将其移动到头结点
        this.delete(tarNode);
        this.addHead(tarNode);
        return tarNode.val;
    }
    
    public void put(int key, int value) {
        Node tarNode = hashMap.get(key);
        if (tarNode != null) {
            this.delete(tarNode);
        }
        Node newNode = new Node(key, value);
        this.hashMap.put(key, newNode);
        this.addHead(newNode);
        if (this.hashMap.size() > this.capacity) {
            this.hashMap.remove(dummyHead.prev.key); // 必须使用key
            this.delete(dummyHead.prev);
        }
    }

    private void delete(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void addHead(Node node) {
        node.next = dummyHead.next;
        node.prev = dummyHead;
        dummyHead.next.prev = node;
        dummyHead.next = node;
    }
}

143. 重排链表

这题有些地方挺细节的，本质是三个题的合体，但是细节在于找中点时要找偏左的，合并时要以第一条链表为主链，将第二条插入进去。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        ListNode mid = findMiddle(head);
        ListNode head2 = mid.next;
        mid.next = null;

        head2 = reverseList(head2);

        mergeList(head, head2);
    }

    // 找中间且偏左
    ListNode findMiddle(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // 反转链表
    ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode nxt = head.next;
            head.next = pre;
            pre = head;
            head = nxt;
        }
        return pre;
    }

    ListNode mergeList(ListNode head1, ListNode head2) {
        // head1和head2一样长，或者head1更长
        while (head2 != null) {
            ListNode nxt1 = head1.next;
            ListNode nxt2 = head2.next;
            head1.next = head2;
            head2.next = nxt1;
            head1 = nxt1;
            head2 = nxt2;
        }
        return head1;
    }
}

430. 扁平化多级双向链表

这个题除了经典的递归分解，但是最后一个节点但有 child 的情况需要特判一下。

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
class Solution {
    public Node flatten(Node head) {
        Node head0 = head;
        flattenWithTail(head0);
        return head;
    }

    Node flattenWithTail(Node head) {
        if (head == null) return null;
        while (head.next != null) {
            if (head.child != null) {
                Node tail = flattenWithTail(head.child);
                tail.next = head.next;
                head.next.prev = tail;
                head.next = head.child;
                head.child.prev = head;
                head.child = null;
            }
            head = head.next;
        }
        if (head.child != null) {
            Node tail = flattenWithTail(head.child);
            head.next = head.child;
            head.child.prev = head;
            head.child = null;
            return tail;
        }
        return head;
    }
}

23. 合并 K 个升序链表

这个题可以用堆的方法 mergeKLists1，也可以用分治的方法 mergeKLists2。

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
class Solution {
    public ListNode mergeKLists1(ListNode[] lists) {
        return lists.length == 0 ? null : merge(lists, 0, lists.length - 1);
    }

    ListNode merge(ListNode[] lists, int i, int j) {
        if (i == j) { return lists[i]; }
        int m = (i + j) / 2;
        ListNode n1 = merge(lists, i, m);
        ListNode n2 = merge(lists, m + 1, j);
        return mergeSortedList(n1, n2);
    }

    ListNode mergeSortedList(ListNode n1, ListNode n2) {
        ListNode dummy = new ListNode(), head = dummy, node;
        while (n1 != null && n2 != null) {
            if (n1.val > n2.val) {
                node = n2;
                n2 = n2.next;
            } else {
                node = n1;
                n1 = n1.next;
            }
            head.next = node;
            head = head.next;
        }
        if (n1 != null) { head.next = n1; }
        if (n2 != null) { head.next = n2; }
        return dummy.next;
    }
    
    public ListNode mergeKLists2(ListNode[] lists) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                pq.add(new int[]{lists[i].val, i});
            }
        }
        ListNode dummyHead = new ListNode(), curNode = dummyHead;
        while (!pq.isEmpty()) {
            int[] min = pq.remove();
            int i = min[1];
            curNode.next = lists[i];
            curNode = curNode.next;
            lists[i] = lists[i].next;
            if (lists[i] != null) {
                pq.add(new int[]{lists[i].val, i});
            }
        }
        return dummyHead.next;
    }
}

1206. 设计跳表

跳表其实挺简单，就是在只有一个链表的基础上，添加多层的索引。

二分查找

你可能觉得二分查找非常简单，它也确实很简单，但我之前理解的二分查找是要判断 mid 是否等于 target 的，这种方式用来查找第一个 >= target 的值就不好使了，所以有必要对下标和边界进行理解。为了巩固基础，可刷灵神的题单。

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

二分查找最好使用开区间，左右端点都是不可取的，即针对长度为 n 的数组进行二分的话，初始化就是 i = -1, j = n；当然闭区间或前闭后开区间也可以，分别是 i = 0, j = n - 1 和 i = 0, j = n；
循环的条件应该是这个区间存在元素，例如开区间应当是 j - i > 1，闭区间是 i <= j，前闭后开区间是 i < j。

如果是要找第一个 >= target 的元素，我们就可以考虑 nums[] 中有一排 target，当 nums[mid] 是这一排 target 中的一个时，我们应该将右端点 j 左移到 mid，而不是将左端点 i 右移到 mid，因为我们找的是第一个 >= target 的元素，右移左端点 i 可能会丢失第一个 >= target 的元素；
同样，我们更不能判断 nums[mid] == target 时就跳出循环，而是将 = target 的情况并入到 > target 或 < target 中，那么并入到哪里呢？这个和循环终止时最终答案的位置有关系。由于要找第一个 >= target 的元素，必须让 j 右边是 >= target 的，i 左边是 < target 的（此处都包含端点 i 和 j，因为是开区间），这样第一个 >= target 的就是 nums[j] 了。同样的，= target 的情况就必须并入 > target 了。

下面的代码就是用于搜索 nums 中第一个 >= target 的元素下标，如果没有这个元素，则返回数组长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
private int searchFirstLargerEqual2(int[] nums, int target) {
    int i = -1, j = nums.length;
    while (j - i > 1) {
        int mid = i + (j - i) / 2;
        if (nums[mid] < target) {
            i = mid; // nums[i]一定小于target，只有nums[j]才可能等于target
        } else {
          	// 相当于找最小的j使得nums[mid] >= target，即第一个大于等于target的下标i
            j = mid;
        }
    }
    return j;
}

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

始终和最后一个元素比较大小，搜索第一个 >= nums[n - 1] 的元素，搜索范围是闭区间 [0, n - 2]；无需特判最小元素是 nums[n - 1] 的情况，因为这种情况下闭区间 [0, n - 2] 找不到它，自然会返回 n - 1。

33. 搜索旋转排序数组

最开始几次循环可能是 nums[m] 和 target 在不同的递增段，此时的主要目的是将它们划分到同一个递增段，往往会是某一边的边界不动，另一边的边界不断收缩。
等他们到达同一个递增段时，此时就是正常的二分搜索。

注意正常的二分搜索始终考虑寻找第一个大于等于 target 的下标，因此在相等的时候要将右边界左移，从而避免漏掉第一个，从而最后答案是 right。开区间的二分搜索是直接 =mid 的。

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
class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int left = -1, right = n - 1;
        while (left + 1 < right) {
            int m = (left + right) / 2;
            // 判断nums[m]和target是否在不同递增段；在不同递增段的情况，只可能刚开始“几次”出现；一旦边界收缩到同一递增段，后续都是同一递增段
            // 此处需要考虑清楚，处于第二段的条件还要包括等于nums[n-1]的
            if (nums[m] <= nums[n - 1] && target > nums[n - 1]) {
                // nums[m]在第二段，target在第一段
                right = m; // 开区间
            } else if (nums[m] > nums[n - 1] && target <= nums[n - 1]) {
                // nums[m]在第一段，target在第二段
                left = m;
            } else { // 在同一个递增段，就是正常的二分
                if (nums[m] < target) {
                    left = m;
                } else { // 等于的情况，应该缩小右侧边界，这样就不会漏掉第一个大于等于的元素
                    right = m;
                }
            }
        }
        return nums[right] == target ? right : -1;
    }
}

4. 寻找两个正序数组的中位数

这个题是真重量级，感觉是hot100最恶心的题目之一了。参照灵神的解析和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    /**
     * 核心：虚拟哨兵映射函数，在nums1和nums2的前后分别添加正负无穷
     * 复杂度：O(1)
     */
    private int getVal(int[] nums, int i) {
        if (i == 0) return Integer.MIN_VALUE;
        else if (i == nums.length + 1) return Integer.MAX_VALUE; // 负无穷已经挤掉一位
      	else {} // 不会出现其他访问
        return nums[i - 1]; // 逻辑下标1对应原数组下标0, 逻辑下标0对应负无穷
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 保证 nums1 是较短的数组，优化二分效率
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length, n = nums2.length;
        // 这里的 left, right 依然映射灵大的 [0, m+1] 逻辑区间
        int left = 0, right = m + 1;
        
      	// 二分目标：寻找最大的i使得满足a[i] <= b[j+1]
      	// 很显然，i越小越满足所以相等的情况需要让左端点右移
        while (left + 1 < right) {
            int i = left + (right - left) / 2; // i相当于mid了，在nums1上进行二分
            int j = (m + n + 1) / 2 - i;
            // 比较a[i] <= b[j+1]，此处使用getVal直接将a和b当成前后添加过无穷后的数组
            if (getVal(nums1, i) <= getVal(nums2, j + 1)) {
              	// 找到最大的i使得上一行的if满足，所以让左端点left右移
                left = i;
            } else {
                right = i;
            }
        }

        int i = left, j = (m + n + 1) / 2 - i;

        // 最终结果计算，同样使用逻辑访问
        int max1 = Math.max(getVal(nums1, i), getVal(nums2, j));
        int min2 = Math.min(getVal(nums1, i + 1), getVal(nums2, j + 1));

        return (m + n) % 2 == 0 ? (max1 + min2) / 2.0 : max1;
    }
}

378. 有序矩阵中第 K 小的元素

使用值域二分，在矩阵左上角和右下角两个值之间的范围内进行查找；本题是240. 搜索二维矩阵 II的进阶版本，注意 hasKthSmaller 的语义，是至少有 k 个元素小于或等于 target。此题还有很多类似的题型，参考灵神题解的题单。

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
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0], right = matrix[n - 1][n - 1];

        // 二分查找，恰好有k个元素小于它的数，即第一个至少有k个元素小于它的数；闭区间
        while (left <= right) {
            int mid = (left + right) / 2;
            // 如果至少有k个元素比它小，首先mid就是符合条件的；我们要找第一个符合条件的，所以左移右端点
            if (hasKthSmaller(matrix, k, n, mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    // 判断是否有至少k个元素小于等于target
    boolean hasKthSmaller(int[][] matrix, int k, int n, int target) {
        int i = n - 1, j = 0;
        int count = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] > target) {
                i--;
            } else if (matrix[i][j] <= target) {
                count += (i + 1);
                j++;
            }
        }
        return count >= k; // 至少有k个
    }
}

719. 找出第 K 小的数对距离

此题类似前一题，但是子问题比前一题复杂一些，子问题是个稍复杂一些的滑动窗口问题（类似713. 乘积小于 K 的子数组）

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
class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int left = 0, right = nums[n - 1] - nums[0]; // 闭区间
        while (left <= right) {
            int mid = (left + right) / 2;
            if (smallerCount(nums, mid) >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return right + 1;
    }

    // 寻找有序数组中nums中，数对距离小于等于x的数量
    int smallerCount(int[] nums, int x) {
        int i = 0, cnt = 0;
        for (int j = 1; j < nums.length; j++) {
            while (nums[j] - nums[i] > x) {
                i++;
            }
            // 最差到j=i，此时等于没加上，下一轮循环j自然会自增，j自增后和i的差距又是1了
            cnt += j - i; // 此处nums[j]和nums[i]差距小于x，且i是最小的，即i取[i,j-1]都可，共j-i个取值
        }
        return cnt;
    }
}

69. x 的平方根

这个题不难，可以用值域二分法做，但右边界不能是 Integer.MAX_VALUE，这样在算 mid * mid 时候会溢出，右边界应该是 Integer.MAX_VALUE 的平方根。

或者也可以使用更高级的牛顿迭代法，直接看代码中的注释。

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
class Solution {
    public int mySqrt(int x) {
        return mySqrt2(x);
    }

    // 二分做法
    public int mySqrt1(int x) {
        // Integer.MAX_VALUE = 2^31-1，(2^31-1)^0.5 = 46340.95000105
        // 右边界必须小于它，否则mid*mid会溢出
        int left = 1, right = Math.min(x, (int)Math.sqrt(Integer.MAX_VALUE));
        // 找最大的数，使其平方小于x
        while (left <= right) {
            int mid = (left + right) / 2;
            if (mid * mid > x) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left - 1;
    }

    // 牛顿迭代法
    public int mySqrt2(int x) {
        // 寻找f1: y=x^2+a的根，假设当前x=x0，则在f1上的点为(x0, x0^2-a)
        // 在(x0, x0^2-a)的切线斜率为2x0，切线为y=2x0(x-x0)+x0^2-a，解得x=(x0+a/x0)/2
        double x0 = (double)x;
        while (true) {
            double x1 = 0.5 * (x0 + x / x0);
            if (Math.abs(x0 - x1) < 1e-7) {
                break; // 精度足够高，退出
            }
            x0 = x1;
        }
        return (int)x0;
    }
}

树和二叉树

最好掌握一下非递归方法实现先中后序遍历。

543. 二叉树的直径

注意递归函数返回值的含义，如果是空则为-1，这样的规定是为了让叶节点返回零，这样传到叶节点父节点那边时，结果就是正确的1了。

108. 将有序数组转换为二叉搜索树

经典用递归来做，注意区间的开闭要提前订好，一般就3种，闭区间、前闭后开区间、开区间。

98. 验证二叉搜索树

3种做法，前序遍历、中序遍历、后续遍历都可以，后续遍历感觉有点不够优雅，暂时先记前两种。

199. 二叉树的右视图

2种做法，比较直观的方法是层次遍历取最后1个；或者也可以用递归的思路做，先访问节点、再分别递归右子树、左子树，递归时记录层数，某个层第一次被访问到时，就是最右侧的节点。

114. 二叉树展开为链表

这个题也是两种做法

方法一：头插法。按照先序遍历反过来的顺序遍历树，这样就能让修改 节点.right 为 head 时，右子树已经被访问完毕，修改完之后再将 head 赋值为刚访问过的节点

方法二：分治。重点要考虑当节点的左右子树的展开链表都得到了，该如何进行合并？这个操作需要左子树链表的末尾节点，否则无法直接接起来，因此将链表末尾设置为递归函数的返回值；合并的具体操作就是，将左子树链表添加到 root -> 右孩子 之间，并把 root 的左孩子置 null。

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

这个题就是注意递归过程的开闭区间的准确性，此处我用了前闭后开区间

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
class Solution {
    int[] preorder, inorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        return buildTree(0, preorder.length, 0, inorder.length);
    }

    // 前闭后开区间
    public TreeNode buildTree(int i1, int j1, int i2, int j2) {
        if (i1 + 1 == j1) { // 用i2和j2也是一样的
            return new TreeNode(preorder[i1]);
        } else if (i1 >= j1) {
            return null;
        }
        int midVal = preorder[i1]; // 根节点
        int midPos = i2;
        while (inorder[midPos] != midVal) { midPos++; }
        int leftLength = midPos - i2;
        int rightLength = j2 - midPos - 1;
        TreeNode leftNode = buildTree(i1 + 1, i1 + 1 + leftLength, i2, midPos);
        TreeNode rightNode = buildTree(j1 - rightLength, j1, midPos + 1, j2);
        return new TreeNode(midVal, leftNode, rightNode);
    }
}

236. 二叉树的最近公共祖先

这题灵神的做法太巧妙了，很难学，建议使用哈希表和BFS做，非常直观。

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
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 1. 建立一个哈希表来记录每个节点的父节点 (Key: 当前节点, Value: 父节点)
        Map<TreeNode, TreeNode> parentMap = new HashMap<>();
        // 根节点没有父节点
        parentMap.put(root, null); 
        
        // 用队列进行标准的层序遍历 (BFS)，把树遍历一遍，记录好所有的父子关系
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        // 只要 p 或 q 还有一个没被存入哈希表，就继续遍历
        while (!parentMap.containsKey(p) || !parentMap.containsKey(q)) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                parentMap.put(node.left, node);
                queue.offer(node.left);
            }
            if (node.right != null) {
                parentMap.put(node.right, node);
                queue.offer(node.right);
            }
        }
        
        // 2. 收集 p 的所有祖先节点 (包括 p 自己)
        Set<TreeNode> pAncestors = new HashSet<>();
        while (p != null) {
            pAncestors.add(p);
            p = parentMap.get(p); // 顺着哈希表往上找爸爸
        }
        
        // 3. 顺着 q 往上找，第一个在 p 的祖先集合里出现的人，就是最近公共祖先
        while (q != null) {
            if (pAncestors.contains(q)) {
                return q;
            }
            q = parentMap.get(q); // 顺着哈希表往上找爸爸
        }
        
        return null;
    }
}

递归和回溯

回溯一般要有个状态变量用于记录，例如说某个下标是否取过；递归函数要有个索引，表示针对某个下标的元素进行操作。

子集型回溯

17. 电话号码的字母组合

78. 子集

两种方法，选或不选，枚举选哪个

划分型回溯

131. 分割回文串

这个题也可以使用选或不选的方式，即每个逗号是否要选择，但这时候必须添加额外的参数 start 记录回文串的起点；或者用枚举选哪个的思路

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
class Solution {
    String s;
    List<String> path = new ArrayList<>();
    List<List<String>> ans = new ArrayList<>();
    public List<List<String>> partition(String s) {
        this.s = s;
        this.dfs1(0, 0);
        // this.dfs2(0);
        return ans;
    }

    // 枚举s中下标为i右边的逗号，即[i,i+1]之间的逗号
    void dfs1(int start, int i) {
        if (i == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }

        String ns = s.substring(start, i + 1); // 枚举的是i右边的逗号，所以是i + 1
        
        // 选逗号，必须是回文
        if (isHuiWen(ns)) {
            path.add(ns);
            dfs1(i + 1, i + 1);
            path.remove(path.size() - 1);
        }
        
        // 不选这个逗号，如果i是最后一位，必须分割；若不是回文，则无需做任何操作
        if (i != s.length() - 1) {
            dfs1(start, i + 1);
        }
    }

    void dfs2(int i) {
        if (i == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int j = i; j < s.length(); j++) {
            String ns = s.substring(i, j + 1); // 取闭区间[i,j]
            if (this.isHuiWen(ns)) {
                path.add(ns);
                this.dfs2(j + 1);
                path.remove(path.size() - 1);
            }
        }
    }

    boolean isHuiWen(String ss) {
        int i = 0, j = ss.length() - 1;
        while (i <= j) {
            if (ss.charAt(i++) != ss.charAt(j--)) {
                return false;
            }
        }
        return true;
    }
}

93. 复原 IP 地址

这个题细节也是比较多，只要选3次，还要处理字符串，判断回文

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
class Solution {
    String s;
    int n;
    List<Integer> path = new ArrayList<>();
    List<String> ans = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        this.s = s;
        this.n = s.length();
        if (n > 12) {
            return ans;
        }
        for (char c : s.toCharArray()) {
            if (!Character.isDigit(c)) {
                return ans;
            }
        }
        dfs(0);
        return ans;
    }

    boolean isValid(String str) {
        if (str.length() == 0) {
            return false;
        } else if (str.length() != 1 && str.charAt(0) == '0') {
            return false;
        }
        int val = Integer.valueOf(str);
        return 0 <= val && val <= 255;
    }

    void judge() {
        String s1 = s.substring(0, path.get(0));
        String s2 = s.substring(path.get(0), path.get(1));
        String s3 = s.substring(path.get(1), path.get(2));
        String s4 = s.substring(path.get(2), n);
        if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
            ans.add(s1 + "." + s2 + "." + s3 + "." + s4);
        }
    }

    // i表示从下标为i开始选，选的是这个下标左侧的
    void dfs(int i) {
        if (path.size() == 3) {
            judge();
            // 当前已经选了0和1，共两个小数点
        }
        for (int j = i + 1; j < n && j - i < 4; j++) {
            path.add(j);
            dfs(j);
            path.remove(path.size() - 1);
        }
    }
}

组合型回溯

77. 组合

这个没给目标数组，cur.add() 时并非是 nums[j]，而是直接 j + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> cur = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        dfs(0, k, n);
        return ans;
    }

    // 表示从[i,n)中选，i并非表示选第几个
    void dfs(int i, int k, int n) {
        if (cur.size() == k) {
            ans.add(new ArrayList<>(cur));
            return;
        }

        for (int j = i; j < n; j++) {
            cur.add(j + 1); // 注意此处的+1只是因为下标是从零开始的
            dfs(j + 1, k, n);
            cur.remove(cur.size() - 1);
        }
    }
}

216. 组合总和 III

22. 括号生成

两种思路，选或不选，或者枚举选哪个；此题还需要维护当前左括号和右括号的个数，选左括号时 leftCount 数量要小于 n，选右括号时，左括号数量要大于右括号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    List<String> ans = new ArrayList<>();
    int leftCount = 0, rightCount = 0; // 得用两个变量来存
    // 如果仅用一个leftCount表示已经放了多少个左括号，那么rightCount=2*leftCount-i

    public List<String> generateParenthesis(int n) {
        dfs(0, n, new StringBuilder());
        return ans;
    }

    public void dfs(int i, int n, StringBuilder path) {
        if (i == 2 * n) {
            ans.add(path.toString());
            return;
        }
        // 第i位置，选或不选

        // 1. 选左括号
        if (leftCount < n) {
            leftCount++;
            path.append("(");
            dfs(i + 1, n, path);
            path.deleteCharAt(path.length() - 1);
            leftCount--;
        }

        // 2. 选右括号
        if (leftCount > rightCount) {
            rightCount++;
            path.append(")");
            dfs(i + 1, n, path);
            path.deleteCharAt(path.length() - 1);
            rightCount--;
        }
    }
}

排列型回溯

46. 全排列

有重复元素的回溯

90. 子集 II

两种方法，枚举第 i 个选或不选，或者枚举要选的元素。关键是这两种方法如何处理有重复元素的情况，详细见注释。

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
class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> cur = new ArrayList<>();
    private int[] nums;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        this.nums = nums;
        Arrays.sort(this.nums); // 排序是为了能更方便地跳过一些元素
        dfs2(0, this.nums.length);
        return ans;
    }

    // 方法一：枚举第i个选或不选
    void dfs1(int i, int n) {
        if (i == n) {
            ans.add(new ArrayList<>(cur));
            return;
        }
        // 1. 选nums[i]
        cur.add(nums[i]);
        dfs1(i + 1, n);
        cur.remove(cur.size() - 1);

        // 2. 不选nums[i]，则后续所有和nums[i]相等的都不选
        i++;
        while (i < n && nums[i] == nums[i - 1]) {
            i++;
        }
        dfs1(i, n);
    }

    // 方法二：从[i,n-1]中枚举要选的元素
    void dfs2(int i, int n) {
        // 每次迭代都要加到ans中
        ans.add(new ArrayList<>(cur));

        for (int j = i; j < n; j++) {
            // 如果选nums[j]，则后面还可以选与nums[j]相等的
            cur.add(nums[j]);
            dfs2(j + 1, n);
            cur.remove(cur.size() - 1);
            // 如果不选nums[j]，则不能再选和nums[j]相等的
            while (j + 1 < n && nums[j + 1] == nums[j]) {
                j++;
            }
        }
    }
}

  1. [40. 组合总和 II]

  2. [491. 非递减子序列]

  3. [47. 全排列 II]

排序

题目：912. 排序数组

快速排序

215. 数组中的第K个最大元素

这是快排的 partition 函数的实现方法，注意 pivot 需要随机选择，否则容易在大量重复元素时退化为 O(n^2) 的复杂度。
说实话这个 partition 的边界问题挺搞的，要做的就是在 nums 的 [left, right] 闭区间上随机选一个数字，将 <= pivot 的放到左边，将 >= pivot 的放到右边，然后返回那个分割左右的索引。
我们先随机选一个数字，将它与 left 交换，接着用相向双指针在 [left + 1, right] 闭区间上不断地将左右元素交换，直到 i > j，当然，i 可能比 j 大不少，想象中间一堆和 pivot 相等的重复元素：

1
2
3
..., pivot, pivot, pivot, pivot, pivot, ...
  ^  | 中间是与一堆与基准相等的重复元素  | ^
  j                                     i

相向双指针找的是大于等于基准的数（等于基准的也要进行交换，这是为了让左右更为平衡）
j-- 无需判断边界，因为当 j 为 left + 1 - 1 时必然循环终止，自然存在边界；
为什么最后要用 j 和 left 交换，因为当循环终止时，如果 i 和 j 都没越界（即处于 [left, right] 的闭区间中），会有 nums[i] > pivot && nums[j] < pivot，如果将 i 与 left 交换，则换过去一个大于基准的值，是错误的划分，而 num[j] 则是满足条件的；另一方面，i 和 j 如果越界了，i 的越界是真越界，而 j 的越界则只是到达 left 的位置，此时相当于 nums[left] 自我交换。

而 i++ 则需要判断边界，i 可能到达 right + 1 的位置，此时是越界的；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 寻找排序后下标为n-k的元素值
        int n = nums.length;
        int left = 0, right = n - 1;
        int idx;
        while (true) {
            idx = partition(nums, left, right);
            if (idx == n - k) {
                break;
            } else if (idx > n - k) {
                right = idx - 1;
            } else {
                left = idx + 1;
            }
        }
        return nums[idx];
    }

    // 划分开区间[left,right]
    int partition(int[] nums, int left, int right) {
        if (right - left <= 0) {
            return left;
        }
        Random random = new Random();
        int pivot = random.nextInt(right - left + 1) + left;
        swap(nums, left, pivot);
        // 让左侧是<=pivot的，右侧是>=pivot的
        int i = left + 1, j = right;
        // 1. 写法1，效率更高，更好记忆
        // while (true) {
        //     while (i <= j && nums[i] < nums[left]) i++;
        //     while (i <= j && nums[j] > nums[left]) j--;
        //     if (i >= j) { break; } // i >= j 或 i > j都可
        //     swap(nums, i++, j--);
        // }
        // 2. 写法2，更容易理解，约束更少
        while (true) {
            while (i <= right && nums[i] <= nums[left]) i++;
            while (nums[j] >= nums[left]) j--;
            if (i > j) { break; }
            swap(nums, i++, j--);
        }
        swap(nums, left, j);
        return j;
    }

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

912. 排序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    Random random = new Random();
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    void quickSort(int[] nums, int left, int right) {
        if (left > right) {
            return;
        }
        int i = partition(nums, left, right); // 见上面的代码
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }
}

归并排序

基于链表的归并排序见148. 排序链表

堆排序

单调栈

单调栈就是用来找左/右边第一个更大/小的元素的，所以可能有4种题意；并且每种题意都可以从左往右/从右往左遍历数组，所以甚至有8种做法。而且我个人暂时无法对单调栈理解得非常到位，时常不知道如何判断该出栈还是入栈。

739. 每日温度

如果要找遍历方向上的下一个更大元素，则让大元素 nums[i] 把栈顶的小元素弹出去，直到栈顶比 nums[i] 更大，此时：
那些被弹出去的小元素，它们在遍历方向上的下一个更大元素都是 nums[i]；nums[i] 在反遍历方向上的下一个更大元素是栈顶。

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[] dailyTemperatures(int[] temperatures) {
    int[] ans = new int[temperatures.length];
    Deque<Integer> st = new ArrayDeque<>(); // 存储下标
    // 方法一：从右往左遍历，当遇到栈顶元素小于等于当前元素时，进行出栈
    for (int i = temperatures.length - 1; i >= 0; i--) {
        while (!st.isEmpty() && temperatures[st.peek()] <= temperatures[i]) { // 注意此处是大于等于
            st.pop();
        }
        if (st.isEmpty()) {
            ans[i] = 0;
        } else {
            ans[i] = st.peek() - i;
        }
        st.push(i);
    }
    // System.out.printf("%s\n", st); // 最后这个栈，存储的是一个前缀最大值序列

    // 方法二：从左往右遍历，如果当前值比栈顶元素大，则当前值为栈顶元素的下一个最大温度
    // for (int i = 0; i < temperatures.length; i++) {
    //     while (!st.isEmpty() && temperatures[st.peek()] < temperatures[i]) { // 注意此处不能是等于
    //         ans[st.peek()] = i - st.peek(); // 得到了栈顶元素的答案
    //         st.pop();
    //     }
    //     st.push(i);
    // }
    return ans;
}

注意等号的取法，假设是寻找更大/更小的元素，则如下：

  1. 当正向遍历时，使用大元素弹出小元素，如果相等则不要弹出，因为此时会去计算弹出元素的正向更大元素（为当前元素），必须是更大的将它弹出；
  2. 当反向遍历时，使用大元素弹出小元素，如果相等也要弹出，因为此时会计算当前元素的反向更大元素（为栈顶），因此栈顶不能和当前元素相等；

当然也可能是大于等于或小于等于的元素，此时要将上面是否带等号的情况反转，见题1475. 商品折扣后的最终价格

496. 下一个更大元素 I

和每日温度类似的，这里是求元素而非下标相关的东西。

503. 下一个更大元素 II

遍历两次，即 for (i = 0; i < 2 * n; i++) {}，并且当 i 作为下标时都使用 i % n。

42. 接雨水

目前学习了两种做法，分别是前后缀分解和单调栈

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
class Solution {
    public int trap(int[] height) {
        // return trap1(height);
        return trap2(height);
    }

    // 方法一：前后缀分解，计算每个下标所能接的雨水高度，相当于竖着计算面积
    // 对于下标i，水的高度应该是min{max{height[0,i)}, max{height(i,n-1]}}，还得再减去自身柱子高度height[i]
    public int trap1(int[] height) {
        int n = height.length;
        if (n <= 2) { return 0; } // 两个柱子无法接水
        int[] lMax = new int[n];
        int[] rMax = new int[n];
        
        lMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            lMax[i] = Math.max(lMax[i - 1], height[i]);
        }
        
        rMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rMax[i] = Math.max(rMax[i + 1], height[i]);
        }

        // System.out.println(Arrays.toString(lMax));
        // System.out.println(Arrays.toString(rMax));
        int ans = 0;
        for (int i = 1; i < n - 1; i++) {
            int val = Math.min(lMax[i - 1], rMax[i + 1]) - height[i];
            // 有可能是负的，说明此处水桶太高了；但实际上最多也就接不到水
            ans += Math.max(0, val);
            // System.out.printf("%s ", ans);
        }
        return ans;
    }

    // 方法二：单调栈（找上一个更大元素，在找的过程中填坑）
    // 此处相当于单调栈的反向遍历，因为找的是反遍历方向上的更大元素
    public int trap2(int[] height) {
        Deque<Integer> st = new ArrayDeque<>(); // 存储下标，此处是严格降序栈（对应下面while中取等号）
        int n = height.length, ans = 0;
        for (int i = 0; i < n; i++) {
            // 1. 找上一个更大元素，找的过程中填坑；目的并非为了找到，因此实际用来算答案的是“小于等于”height[i]的元素
            // 等于height[i]的情况也算进去，因为此时算出来的值必然是0，例如[10,5,5]，但这能减少栈中元素个数；
            // 不然的话，后续就会出现[5,5,10]这种，当然这种情况算出来也是0，并不影响结果，所以等号取不取都行；取等号，则为严格降序栈，否则不严格
            while (!st.isEmpty() && height[st.peek()] < height[i]) {
                // 如果能填坑，至少栈中得要有2个元素，先弹出来一个当作最低点
                int bottom = st.pop();
                // 栈中只有1个元素，无法形成坑；并且这个元素小于height[i]也没有利用价值
                // 想象一个高柱子的左侧全是比它低的，这些全部无法接水，例如1,2,3,4,10
                if (st.isEmpty()) {
                    break;
                }
                // 左侧第一个必然小于等于height[i]
                int dh = Math.min(height[i], height[st.peek()]) - height[bottom];
                ans += dh * (i - st.peek() - 1);
            }
            // 已经找到上一个更大元素，将自身下标添加到栈中，维持单调递减
            st.push(i);
        }
        return ans;
    }
}

84. 柱状图中最大的矩形

利用接雨水这个题的前后缀分解方法，实则使用前后单调栈即可。

单调队列

239. 滑动窗口最大值

使用单调队列存储下标，降本增笑的笑话：

  1. 如果新员工比老员工强（或者一样强），把老员工裁掉。（元素进入窗口）
  2. 如果老员工 35 岁了，也裁掉。（元素离开窗口）
  3. 裁员后，资历最老（最左边）的人就是最强的员工了。

选自：灵神题解

注意此处要使用双端队列，因为在头部和尾部都需要进行“获取插入移出”的操作；以及一开始会有若干次只维护双端队列但不寻找答案的操作。

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
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> que = new ArrayDeque<>(); // 单调队列，存的是下标
        int[] ans = new int[n - k + 1];
        for (int j = 0; j < n; j++) {
            while (!que.isEmpty() && nums[que.getLast()] <= nums[j]) {
                que.pollLast();
            }
            que.offerLast(j);
            int i = j - k + 1; // [j-k+1,j]的闭区间的元素个数为k
            
            // 一开始会经历若干次不找答案的操作
            if (i < 0) {
                continue;
            }
            if (que.getFirst() < i) {
                que.pollFirst();
            }
            ans[i] = nums[que.getFirst()];
        }
        
        return ans;
    }
}

树形DP

543. 二叉树的直径

此题算的是路径的长度，和节点的数字和无关。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    int ans = -1;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
    }
    // 返回值定义为，到叶子节点的最长路径，即边的数量
    int dfs(TreeNode node) {
        if (node == null) {
            // 在本dfs函数返回值的定义下，本状态是非法的，已经超出叶节点了，返回-1是为了保证dfs(叶子)=0
            // 返回-1的原因：只有叶节点可能调用此处，dfs(叶子)应当为0；而child和parent的dfs返回值的关系为+1
            return -1;
        }
        int v1 = dfs(node.left) + 1;
        int v2 = dfs(node.right) + 1;
        ans = Math.max(ans, v1 + v2);
        return Math.max(v1, v2);
    }
}

124. 二叉树中的最大路径和

此题算的是节点上的数字和，注意递归函数的返回值和最终答案之间的关系，是隔了一层运算的；因为递归函数只表示当前节点到叶子的最大路径和，并不是两个叶子的最大路径和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        getSubTreeVal(root);
        return ans;
    }

    int getSubTreeVal(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftVal = getSubTreeVal(node.left);
        int rightVal = getSubTreeVal(node.right);
        ans = Math.max(ans, Math.max(0, leftVal) + Math.max(0, rightVal) + node.val);
        return Math.max(Math.max(leftVal, rightVal), 0) + node.val;
    }
}

图论

拓扑排序

207. 课程表 和 210. 课程表 II

两种方法，分别是深搜和广搜。

深搜采用三色标记法，类似后序遍历的思想，当某个节点依赖的所有节点都被访问过后（即从这个节点出发的所有节点都被 dfs 过后），该节点才被添加到访问序列中；
广搜则不断将入度为零的节点添加到队列之中，并将所有“依赖于队列中节点”的节点的入度-1，直到出现新的入度为零的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution {
    int[] ans;
    int idx = 0;
    List<Integer>[] g, h;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        ans = new int[numCourses];
        g = new ArrayList[numCourses];
        h = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            g[i] = new ArrayList<>();
            h[i] = new ArrayList<>();
        }
        for (int[] pre : prerequisites) {
            // pre[0]依赖于pre[1]
            g[pre[0]].add(pre[1]); // g[i]表示i所依赖的，用于深度优先搜索
            h[pre[1]].add(pre[0]); // h[i]表示依赖于i的，用于广度优先搜索
        }
        
        // 方法一：深度优先搜索
        // return findOrderDfs(numCourses, prerequisites);

        // 方法二：广度优先搜索，也叫Kahn算法
        return findOrderBfs(numCourses, prerequisites);
    }

    // 方法一：深度优先搜索，三色法
    int[] findOrderDfs(int numCourses, int[][] prerequisites) {
        int[] colors = new int[numCourses];
        Arrays.fill(colors, 0);
        for (int i = 0; i < numCourses; i++) {
            if (dfs(i, g, colors)) {
                return new int[0];
            }
        }
        return ans;
    }

    // 返回是否存在环
    boolean dfs(int i, List<Integer>[] g, int[] colors) {
        if (colors[i] == 1) {
            return true;
        }
        if (colors[i] == 2) {
            return false;
        }

        colors[i] = 1;
        for (int j : g[i]) {
            if (dfs(j, g, colors)) {
                return true;
            }
        }
        ans[idx++] = i; // i不需要回溯，因为此时必然所有i依赖的都被遍历过了
        colors[i] = 2;
        return false;
    }

    int[] findOrderBfs(int numCourses, int[][] prerequisites) {
        Deque<Integer> deq = new ArrayDeque<>();
        // 找出入度为零的节点
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            inDegree[i] = g[i].size(); // 这里用g，表示i的入度
            if (inDegree[i] == 0) {
                deq.offer(i);
            }
        }


        while (!deq.isEmpty()) {
            int i = deq.poll();
            ans[idx++] = i;
            for (int j : h[i]) { // 这里用h，要让依赖于i的入度-1
                inDegree[j]--;
                if (inDegree[j] == 0) {
                    deq.offer(j);
                }
            }
        }
        
        return idx == numCourses ? ans : new int[0];
    }
}

Trie前缀树

208. 实现 Trie (前缀树)

用灵神的 26 叉树来写吧，直接 char - 'a' 作为下标，是否为 null 来判断；然后 startsWith 和 search 共用一个 find 函数，返回 0 表示找不到、 1 表示前缀匹配、 2 表示完全匹配

动态规划

动态规划的东西有点太多了，我会新开一个博客进行整理。