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

遍历+哈希表

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

前缀和

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

核心是“任意子数组的和，都可以表示为两个前缀和的差”，前缀和数组得开辟n+1长度，并且定义pres[i]为[0,i-1]范围内的元素和，并令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]

  1. 560. 和为 K 的子数组
    见前缀和

  2. 437. 路径总和 III
    见前缀和

滑动窗口

定长滑动窗口

  1. 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. 左端点离开窗口
}

变长滑动窗口

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

  1. 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;
    }
}
  1. 713. 乘积小于 K 的子数组

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

链表

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

  1. 反转链表

这个题要注意，链表长度为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;
}
  1. 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;
}
  1. 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;
}
  1. 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;
    }
}
  1. 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;
}
  1. 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
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;
    }
}
  1. 23. 合并 K 个升序链表

这个题可以用最小堆来完成，写法比较简单，注意所用语言是如何定义最小堆的；代码就不贴了

  1. 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;
    }
}
  1. 1206. 设计跳表

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

二分查找

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

  1. 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
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;
        } else {
            j = mid;
        }
    }
    return j;
}
  1. 153. 寻找旋转排序数组中的最小值

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

树和二叉树

递归和回溯

子集型回溯

划分型回溯

  1. 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;
    }
}

组合型回溯

  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);
        }
    }
}
  1. 216. 组合总和 III

排列型回溯

  1. 46. 全排列

有重复元素的回溯

  1. 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. 排序数组

快速排序

  1. 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; }
        //     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;
    }
}
  1. 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种做法。而且我个人暂时无法对单调栈理解得非常到位，时常不知道如何判断该出栈还是入栈。

  1. 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. 商品折扣后的最终价格

  1. 496. 下一个更大元素 I

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

  1. 503. 下一个更大元素 II

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

单调队列

  1. 239. 滑动窗口最大值

树形DP

  1. 543. 二叉树的直径
    此题算的是路径的长度，和节点的数字和无关。

  2. 124. 二叉树中的最大路径和
    此题算的是节点上的数字和

动态规划

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