1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class ReverseLinkedList {
    public ListNode reverseList(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            // 暂存下一个节点
            ListNode next = head.next;
            // 讲head节点的next指向前一个节点
            head.next = newHead;
            // newHead更新为head
            newHead = head;
            // 遍历下一个节点
            head = next;
        }
        return newHead;
    }
}

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 class ReverseLinkedList2 {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null) {
            return null;
        }
        // 用cur（当前节点）和pre（前一个节点）两个进行循环反转
        ListNode cur = head, pre = null;
        // 先走到m反转起始位置，最后pre为m-1位置、cur为m位置节点
        for (int i = 1; i < m; i++) {
            pre = cur;
            cur = cur.next;
        }
        // 用first（m-1位置）记录反转起始位置节点，last记录反转结束位置，用于反转后连接
        ListNode first = pre, last = cur;
        // 反转指向需要一个额外中间节点tmp
        ListNode tmp = null;
        // 循环反转m到n位置节点指针
        for (int i = m; i <= n; i++) {
            // 记录当前节点下一个节点
            tmp = cur.next;
            // 当前节点下一个节点指向前一个节点
            cur.next = pre;
            // 前一个节点移动为当前节点
            pre = cur;
            // 当前节点移动到下一个节点
            cur = tmp;
        }
        // 反转起始位置节点（m-1位置）指向pre（pre为反转后头节点，反转前原始链表第n个节点）
        // 如果first为null，说明m为0，直接将pre作为head
        if (first != null) {
            first.next = pre;
        } else {
            head = pre;
        }
        // 反转结束位置节点指向节点cur（cur为原始链表第n+1个节点）
        last.next = cur;
        return head;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class IntersectionOfTwoLinkedLists {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 双指针法
        ListNode pA = headA;
        ListNode pB = headB;
        // 当 pA 到达链表的尾部时，将它重定位到链表 B 的头结点 (你没看错，就是链表 B);
        // 类似的，当 pB 到达链表的尾部时，将它重定位到链表 A 的头结点。
        // 当 pA 和 pB 相遇，则 pA或pB 即为相交结点。
        while (pA != pB) {
            pA = pA != null ? pA.next : headB;
            pB = pB != null ? pB.next : headA;
        }
        return pA;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LinkedListCycle {
    public boolean hasCycle(ListNode head) {
        // 注意判断链表为空和一个节点链表情况
        if (head == null || head.next == null) {
            return false;
        }
        // 快指针
        ListNode p1 = head.next;
        // 慢指针
        ListNode p2 = head;
        // 如果快慢指针相交则存在环
        while (p1 != p2) {
            // 为null说明已经到链表尾部，无环
            if (p1 == null || p1.next == null) {
                return false;
            }
            p1 = p1.next.next;
            p2 = p2.next;
        }
        return true;
    }
}

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 class LinkedListCycle2 {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        // 快指针
        ListNode p1 = head;
        // 慢指针
        ListNode p2 = head;
        // 如果快慢指针相交则存在环
        do {
            if (p1 == null || p1.next == null) {
                return null;
            }
            p1 = p1.next.next;
            p2 = p2.next;
        } while (p1 != p2);
        // 快指针从head开始
        p1 = head;
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}

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 class PartitionList {
    public ListNode partition(ListNode head, int x) {
        // 用两个链表分别保存小于x和大于等于x的节点；
        ListNode left = new ListNode(-1);
        ListNode right = new ListNode(-1);
        // 用两个节点移动更新
        ListNode pl = left;
        ListNode pr = right;
        while (head != null) {
            if (head.val < x) {
                pl.next = head;
                pl = pl.next;
            } else {
                pr.next = head;
                pr = pr.next;
            }
            head = head.next;
        }
        // 将右边最后一个节点的next设置为null，不然可能存在环
        pr.next = null;
        // 拼接左右两个链表
        pl.next = right.next;
        return left.next;
    }
}

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 class CopyListWithRandomPointer {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node tmp = head;
        // 复制每个节点， A->B->C 变为 A->A'->B->B'->C->C'
        while (tmp != null) {
            Node newNode = new Node(tmp.val);
            newNode.next = tmp.next;
            tmp.next = newNode;
            tmp = newNode.next;
        }
        // 再遍历一次，将随机指针复制到新节点
        tmp = head;
        while (tmp != null) {
            tmp.next.random = tmp.random != null ? tmp.random.next : null;
            tmp = tmp.next.next;
        }
        // 复制的新链表的头节点
        Node headNew = head.next;
        Node pOld = head;
        Node pNew = head.next;
        // 拆分，A->A'->B->B'->C->C' 变为两个链表 A->B->C and A'->B'->C'
        while (pOld != null) {
            pOld.next = pOld.next.next;
            pNew.next = pNew.next != null ? pNew.next.next : null;
            pOld = pOld.next;
            pNew = pNew.next;
        }
        return headNew;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class MergeTwoSortedLists {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(-1);
        ListNode prev = res;
        // 两个都不（&&）为空，比较大小添加较小节点到新链表尾部
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        // 拼接剩下部分
        prev.next = (l1 == null) ? l2 : l1;
        return res.next;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class MergeKSortedLists {
    public ListNode mergeKLists(ListNode[] lists) {
        // 优先队列
        Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        for (ListNode node : lists) {
            if (node != null) {
                pq.offer(node);
            }
        }
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        while (!pq.isEmpty()) {
            ListNode minNode = pq.poll();
            tail.next = minNode;
            tail = minNode;
            if (minNode.next != null) {
                pq.offer(minNode.next);
            }
        }
        return dummyHead.next;
    }
}

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 class ImplementStackUsingQueues {
    // 用一个队列
    private LinkedList<Integer> q1 = new LinkedList<>();

    public ImplementStackUsingQueues() {
    }

    public void push(int x) {
        q1.add(x);
        int sz = q1.size();
        // 每加入一个元素，把前面元素移动到新加入的后面
        while (sz > 1) {
            q1.add(q1.remove());
            sz--;
        }
    }

    public int pop() {
        return q1.remove();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}

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 class ImplementQueueUsingStacks {
    // 两个栈，新元素压入s1的栈顶，弹出时把s1元素压入s2，弹出s2的栈顶元素
    private Stack<Integer> s1 = new Stack<>();
    private Stack<Integer> s2 = new Stack<>();
    // s1中压入的第一个元素（队首，栈底）
    private int front;

    public ImplementQueueUsingStacks() {

    }

    public void push(int x) {
        if (s1.empty()) {
            front = x;
        }
        s1.push(x);
    }

    public int pop() {
        // s2为空，把s1所以元素压入s2，返回s2栈顶元素
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        // s2不为空，直接返回s2栈顶元素
        return s2.pop();
    }

    public int peek() {
        // s2不为空返回s2的栈顶元素
        if (!s2.isEmpty()) {
            return s2.peek();
        }
        // s2为空返回s1的栈底元素
        return front;
    }

    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

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 class MinStack {
    // 数据栈
    private Stack<Integer> data;
    // 辅助栈，记录对应最小值
    private Stack<Integer> helper;

    public MinStack() {
        data = new Stack<>();
        helper = new Stack<>();
    }

    public void push(int x) {
        data.add(x);
        // 如果辅助栈为空或者辅助栈栈顶元素大于x，压入x到栈顶
        if (helper.isEmpty() || helper.peek() >= x) {
            helper.add(x);
        } else {
            helper.add(helper.peek());
        }
    }

    public void pop() {
        // 数据栈和辅助栈同时pop
        data.pop();
        helper.pop();
    }

    public int top() {
        return data.peek();
    }

    public int getMin() {
        return helper.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
39
40
41
42
43
44
public class BasicCalculator {
    public int calculate(String s) {
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        int num = 0;
        // 判断正负
        int sign = 1;
        for (char c : s.toCharArray()) {
            if (c == ' ') {
                continue;
            }
            // 数字
            if (c >= '0' && c <= '9') {
                num = num * 10 + c - '0';
            }
            // 如果遇到操作符，进行运算
            else if (c == '+' || c == '-') {
                res = res + sign * num;
                sign = c == '+' ? 1 : -1;
                num = 0;
            }
            // 遇到’('，将结果和括号前的运算保存，然后将参数重置
            else if (c == '(') {
                stack.push(res);
                stack.push(sign);
                sign = 1;
                res = 0;
            }
            // 遇到')'，计算新的结果
            else if (c == ')') {
                // 将')'前的运算结束
                res = res + sign * num;
                // 将之前的结果和操作取出来和当前结果进行运算
                int signBefore = stack.pop();
                int resBefore = stack.pop();
                res = resBefore + signBefore * res;
                sign = 1;
                num = 0;
            }
        }
        res = res + sign * num;
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class KthLargestElementInAnArray {
    public int findKthLargest(int[] nums, int k) {
        // 创建一个小顶堆（优先队列模拟）
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        for (int n : nums) {
            // 堆中元素个数小于K时，新元素直接进入堆中
            if (heap.size() < k) {
                heap.add(n);
            }
            // 当堆顶小于新元素时，弹出堆顶，将新元素加入堆
            else if (heap.element() < n) {
                heap.poll();
                heap.add(n);
            }
        }
        return heap.poll();
    }
}

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 class FindMedianFromDataStream {
    private int count;
    private PriorityQueue<Integer> maxheap;
    private PriorityQueue<Integer> minheap;

    public FindMedianFromDataStream() {
        count = 0;
        maxheap = new PriorityQueue<>((x, y) -> y - x);
        minheap = new PriorityQueue<>((x, y) -> x - y);
    }

    public void addNum(int num) {
        count++;
        maxheap.offer(num);
        minheap.add(maxheap.poll());
        // 如果两个堆合起来的元素个数是奇数，小顶堆要拿出堆顶元素给大顶堆
        if ((count & 1) != 0) {
            maxheap.add(minheap.poll());
        }
    }

    public double findMedian() {
        // 如果两个堆合起来的元素个数是偶数，数据流的中位数就是各自堆顶元素的平均值
        if ((count & 1) == 0) {
            return (double) (maxheap.peek() + minheap.peek()) / 2;
        }
        // 如果两个堆合起来的元素个数是奇数，数据流的中位数大顶堆的堆顶元素
        else {
            return (double) maxheap.peek();
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class AssignCookies {
    public int findContentChildren(int[] g, int[] s) {
        int res = 0;
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0, j = 0;
        while (i < g.length && j < s.length) {
            if (s[j] >= g[i]) {
                res++;
                i++;
            }
            j++;
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class WiggleSubsequence {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        // 判断连续上升或者下降的波段个数
        int up = 1, down = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            } else if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }
}

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 class RemoveKDigits {
    public String removeKdigits(String num, int k) {
        LinkedList<Character> stack = new LinkedList<>();
        for (char digit : num.toCharArray()) {
            // 对于数字序列[d1,d2,d3,...,dn],如果d2小于d1，删除d1才能获得最小结果。
            while (k > 0 && stack.size() > 0 && stack.peekLast() > digit) {
                stack.removeLast();
                k -= 1;
            }
            stack.addLast(digit);
        }
        // 对于单调递增序列，只需要删除末尾的数字来获得最小结果。
        for (int i = 0; i < k; i++) {
            stack.removeLast();
        }
        StringBuilder res = new StringBuilder();
        // 去掉头部的0
        boolean headZero = true;
        for (char digit : stack) {
            if (headZero && digit == '0') {
                continue;
            }
            headZero = false;
            res.append(digit);
        }
        if (res.length() == 0) {
            return "0";
        }
        return res.toString();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class JumpGame {
    public boolean canJump(int[] nums) {
        // 最远可以到达的位置
        int maxIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            System.out.println("i:" + i + " maxIndex:" + maxIndex);
            if (i <= maxIndex) {
                // 更新最远可以到达的位置
                maxIndex = Math.max(maxIndex, i + nums[i]);
                // 如果最远可以到达的位置大于等于数组长度，则可以到达最后一个位置
                if (maxIndex >= nums.length - 1) {
                    return true;
                }
            } else {
                return false;
            }
        }
        return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class JumpGame2 {
    public int jump(int[] nums) {
        int res = 0;
        int maxPosition = 0;
        int end = 0;
        // 最后一个元素不需要访问
        for (int i = 0; i < nums.length - 1; i++) {
            // 遍历i到当前maxPosition之间下一步能到的最远距离
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                res++;
            }
        }
        return res;
    }
}

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
class MinimumNumberOfArrowsToBurstBalloons {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) {
            return 0;
        }
        // 先按x_end排序
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        int res = 1;
        int start, end;
        // 记录当前气球的end位置
        int maxPosition = points[0][1];
        for (int[] p : points) {
            // end位置在当前气球end位置（maxPosition）之前的所有气球都可以一次引爆
            start = p[0];
            end = p[1];
            if (maxPosition < start) {
                maxPosition = end;
                res++;
            }
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MinimumNumberOfRefuelingStops {
    /**
     * 动态规划，时间O(N^2)，空间O(N)
     */
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        // dp[i] 为加 i 次油能走的最远距离，需要满足 dp[i] >= target 的最小 i
        int[] dp = new int[stations.length + 1];
        dp[0] = startFuel;
        for (int i = 0; i < stations.length; i++) {
            for (int j = i; j >= 0; j--) {
                // 如果 dp[j] 能到达stations[i]，判断更新是否加j+1次油能到更远距离
                if (dp[j] >= stations[i][0]) {
                    dp[j + 1] = Math.max(dp[j + 1], dp[j] + stations[i][1]);
                }
            }
        }
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] >= target) {
                return i;
            }
        }
        return -1;
    }
}

1
2
3
4
5
6
7
8
9
 result = []
 def backtrack(路径, 选择列表):
     if 满足结束条件:
         result.add(路径)
         return
     for 选择 in 选择列表:
         做选择
         backtrack(路径, 选择列表)
         撤销选择

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
class Subsets {
    /**
     * 递归（遍历），时间：O(N * 2^N)，空间：O(N * 2^N)
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int num : nums) {
            List<List<Integer>> newSubsets = new ArrayList<>();
            for (List<Integer> r : res) {
                newSubsets.add(new ArrayList<Integer>(r) );
            }
            res.addAll(newSubsets);
        }
        return res;
    }

    /**
     * 回溯：时间：O(N * 2^N)，空间：O(N * 2^N)
     * 算法：幂集是所有长度从 0 到 n 所有子集的组合。
     */
    public void backtrack(List<List<Integer>> res, int first, ArrayList<Integer> curr, int[] nums) {
        res.add(new ArrayList<>(curr));
        for (int i = first; i < nums.length; i++) {
            curr.add(nums[i]);
            backtrack(res, i + 1, curr, nums);
            curr.remove(curr.size() - 1);
        }
    }

    public List<List<Integer>> subsets2(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(res, 0, new ArrayList<>(), nums);
        return res;
    }

    /**
     * 位操作，字典排序（二进制排序） 子集：时间：O(N * 2^N)，空间：O(N * 2^N)
     * 相当于遍历，只是用位掩码来表示所有遍历
     */
    public List<List<Integer>> subsets3(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        // 生成从 0..00 到 1..11 的所有 n 位掩码
        for (int i = (int) Math.pow(2, n); i < (int) Math.pow(2, n + 1); i++) {
            String bitmask = Integer.toBinaryString(i).substring(1);
            List<Integer> curr = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (bitmask.charAt(j) == '1') {
                    curr.add(nums[j]);
                }
            }
            res.add(curr);
        }
        return res;
    }
}

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
class Subsets2 {
    /**
     * 回溯
     */
    private void backtrack(List<List<Integer>> res, int first, ArrayList<Integer> curr, int[] nums) {
        res.add(new ArrayList<>(curr));
        for (int i = first; i < nums.length; i++) {
            // 跳过重复元素
            if (i > first && nums[i] == nums[i - 1]) {
                continue;
            }
            curr.add(nums[i]);
            backtrack(res, i + 1, curr, nums);
            curr.remove(curr.size() - 1);
        }
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        // 先排序
        Arrays.sort(nums);
        backtrack(res, 0, new ArrayList<>(), nums);
        return res;
    }

    /**
     * 遍历1
     * 在已有子集遍历添加当前元素时，跳过上次遍历重复元素已经添加过的子集，只添加新的部分
     */
    public List<List<Integer>> subsetsWithDup2(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        res.add(new ArrayList<>());
        // 新解开始位置
        int start = 1;
        for (int i = 0; i < nums.length; i++) {
            List<List<Integer>> newSubsets = new ArrayList<>();
            for (int j = 0; j < res.size(); j++) {
                List<Integer> list = res.get(j);
                // 跳过重复元素
                if (i > 0 && nums[i] == nums[i - 1] && j < start) {
                    continue;
                }
                int tmp = nums[i];
                newSubsets.add(new ArrayList<Integer>(list) );
            }
            // 更新新解开始位置
            start = res.size();
            res.addAll(newSubsets);
        }
        return res;
    }

    /**
     * 遍历2
     * 记录重复元素重复次数dupCount，在出现重复数字之前的所有解中，分别加1个重复数字, ..., dupCount个重复数字
     */
    public List<List<Integer>> subsetsWithDup3(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        res.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i++) {
            // 重复元素重复次数
            int dupCount = 0;
            while (((i + 1) < nums.length) && nums[i + 1] == nums[i]) {
                dupCount++;
                i++;
            }
            int tmpSize = res.size();
            for (int j = 0; j < tmpSize; j++) {
                List<Integer> tmpList = new ArrayList<>(res.get(j));
                // 每次在上次的结果中多加 1 个重复数字
                for (int k = 0; k <= dupCount; k++) {
                    // 加入当前重复的数字
                    tmpList.add(nums[i]);
                    res.add(new ArrayList<>(tmpList));
                }
            }
        }
        return res;
    }
}

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 CombinationSum2 {
    /**
     * 回溯
     * 同：90.子集2
     */
    public void backtrack(List<List<Integer>> res, int start, ArrayList<Integer> curr, int[] candidates, int target) {
        if (target == 0) {
            res.add(new ArrayList<>(curr));
        } else if (target < 0) {
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            // 跳过重复元素
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            curr.add(candidates[i]);
            backtrack(res, i + 1, curr, candidates, target - candidates[i]);
            curr.remove(curr.size() - 1);
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(res, 0, new ArrayList<>(), candidates, target);
        return res;
    }
}

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 GenerateParentheses {
    public void backtrack(List<String> res, StringBuilder cur, int left, int right, int n) {
        if (cur.length() == n * 2) {
            res.add(cur.toString());
            return;
        }
        if (left < n) {
            cur.append('(');
            backtrack(res, cur, left + 1, right, n);
            cur.deleteCharAt(cur.length() - 1);
        }
        // 右括号个数一定要小于左括号个数才能再加一个右括号
        if (right < left) {
            cur.append(')');
            backtrack(res, cur, left, right + 1, n);
            cur.deleteCharAt(cur.length() - 1);
        }
    }

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(res, new StringBuilder(), 0, 0, n);
        return res;
    }
}

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
class NQueens {
    /**
     * 构造每行结果String
     */
    private static List<String> charToString(char[][] array) {
        List<String> result = new LinkedList<>();
        for (char[] chars : array) {
            result.add(String.valueOf(chars));
        }
        return result;
    }

    /**
     * 判断是否符合要求
     */
    private boolean isValid(char[][] board, int row, int col) {
        // 检查列上是否已经有皇后
        for (char[] chars : board) {
            if (chars[col] == 'Q') {
                return false;
            }
        }
        // 检查左上角是否有皇后
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        // 检查右下角是否有皇后
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    /**
     * 回溯
     */
    public void backtrack(List<List<String>> res, char[][] board, int row) {
        if (row == board.length) {
            res.add(charToString(board));
            return;
        }
        for (int col = 0; col < board.length; col++) {
            if (!isValid(board, row, col)) {
                continue;
            }
            board[row][col] = 'Q';
            backtrack(res, board, row + 1);
            board[row][col] = '.';
        }
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        if (n <= 0) {
            return null;
        }
        char[][] board = new char[n][n];
        for (char[] chars : board) {
            Arrays.fill(chars, '.');
        }
        backtrack(res, board, 0);
        return res;
    }
}

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
class CountOfSmallerNumbersAfterSelf {
    private int[] temp;
    // 计数数组
    private int[] counter;
    // 索引数组
    private int[] indexes;

    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int len = nums.length;
        if (len == 0) {
            return res;
        }
        temp = new int[len];
        counter = new int[len];
        indexes = new int[len];
        for (int i = 0; i < len; i++) {
            indexes[i] = i;
        }
        divide(nums, 0, len - 1);
        for (int i = 0; i < len; i++) {
            res.add(counter[i]);
        }
        return res;
    }

    private void divide(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = l + (r - l) / 2;
        divide(nums, l, mid);
        divide(nums, mid + 1, r);
        // 归并排序的优化，如果索引数组有序，就没有必要再继续计算了
        if (nums[indexes[mid]] > nums[indexes[mid + 1]]) {
            merge(nums, l, mid, r);
        }
    }

    private void merge(int[] nums, int left, int mid, int right) {
        for (int i = left; i <= right; i++) {
            temp[i] = indexes[i];
        }
        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++) {
            if (i > mid) {
                indexes[k] = temp[j++];
            } else if (j > right) {
                indexes[k] = temp[i++];
                // 此时 j 用完了，之前的数就和后面的区间长度构成逆序
                counter[indexes[k]] += (right - mid);
            } else if (nums[temp[i]] <= nums[temp[j]]) {
                indexes[k] = temp[i++];
                counter[indexes[k]] += (j - mid - 1);
            } else {
                // nums[indexes[i]] > nums[indexes[j]] 构成逆序
                indexes[k] = temp[j++];
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class PathSum2 {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        // 用Deque双端队列比用LinkedList快十倍以上？
        dfs(root, sum, new ArrayDeque<>(), res);
        return res;
    }

    public void dfs(TreeNode root, int sum, Deque<Integer> tmp, List<List<Integer>> res) {
        if (root == null) {
            return;
        }
        tmp.addLast(root.val);
        if (root.val == sum && root.left == null && root.right == null) {
            res.add(new LinkedList<>(tmp));
        }

        dfs(root.left, sum - root.val, tmp, res);
        dfs(root.right, sum - root.val, tmp, res);
        tmp.removeLast();
    }
}

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 LowestCommonAncestorOfABinaryTree {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //  如果当前结点 root 等于 NULL，则直接返回 NULL
        if (root == null) {
            return null;
        }
        // 如果 root 等于 p 或者 q ，那返回 p 或者 q
        if (root == p || root == q) {
            return root;
        }
        // 递归左右子树，因为是递归，使用函数后可认为左右子树已经算出结果
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 此时若left为空，那最终结果只要看 right
        if (left == null) {
            return right;
        }
        // 若 right 为空，那最终结果只要看 left
        if (right == null) {
            return left;
        }
        // 如果 left 和 right 都非空，root 是他们的最近公共祖先
        return root;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class FlattenBinaryTreeToLinkedList {
    TreeNode tmp = null;

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.right);
        flatten(root.left);
        root.right = tmp;
        root.left = null;
        tmp = root;
    }
}

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 BinaryTreeRightSideView {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root != null) {
            // 当前层节点
            Deque<TreeNode> deque1 = new ArrayDeque<>();
            // 下一层节点
            Deque<TreeNode> deque2 = new ArrayDeque<>();
            deque1.addLast(root);
            bfs(deque1, deque2, res);
        }
        return res;
    }

    public void bfs(Deque<TreeNode> deque1, Deque<TreeNode> deque2, List<Integer> res) {
        if (deque1.isEmpty()) {
            return;
        }
        // 当前层的最后一个节点就是该层右视图节点
        res.add(deque1.getLast().val);
        // 遍历得到下一层节点
        while (!deque1.isEmpty()) {
            TreeNode tmp = deque1.removeFirst();
            if (tmp.left != null) {
                deque2.addLast(tmp.left);
            }
            if (tmp.right != null) {
                deque2.addLast(tmp.right);
            }
        }
        // 递归下下一层
        bfs(deque2, deque1, res);
    }
}

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 boolean canFinish(int numCourses, int[][] prerequisites) {
        // 邻接表，记录每门课程的依赖路径
        List<List<Integer>> adjacency = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjacency.add(new ArrayList<>());
        }
        for (int[] cp : prerequisites) {
            adjacency.get(cp[1]).add(cp[0]);
        }
        // 标记节点
        int[] flags = new int[numCourses];
        // 依次判断每门课程的依赖路径是否存在环
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(adjacency, flags, i)) {
                return false;
            }
        }
        return true;
    }

    public boolean dfs(List<List<Integer>> adjacency, int[] flags, int i) {
        if (flags[i] == 1) {
            return false;
        }
        if (flags[i] == -1) {
            return true;
        }
        // flag=1表示该节点（课程）已经在依赖路径上，如果后面有节点又指向该节点，说明存在环，返回false
        flags[i] = 1;
        // 深度遍历依赖课程
        for (Integer j : adjacency.get(i)) {
            if (!dfs(adjacency, flags, j)) {
                return false;
            }
        }
        flags[i] = -1;
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        // 防止 left 和 right 太大直接相加导致溢出
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class SearchInsertPosition {
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        int left = 0;
        // 因为有可能数组的最后一个元素的位置的下一个是我们要找的，故右边界是 len
        int right = len;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return 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
29
30
31
32
33
34
35
36
class FindFirstAndLastPositionOfElementInSortedArray {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                left = mid;
                right = mid;
                // 搜索左右边界
                while (left - 1 >= 0 && nums[left - 1] == target) {
                    left--;
                }
                while (right + 1 < nums.length && nums[right + 1] == target) {
                    right++;
                }
                break;
            }
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        int[] res;
        if (nums[left] != target) {
            res = new int[]{-1, -1};
        } else {

            res = new int[]{left, right};
        }
        return res;
    }
}

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 SearchInRotatedSortedArray {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[nums.length - 1]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -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
public class SerializeAndDeserializeBinaryTree {
    public void rserialize(TreeNode root, StringBuilder str) {
        if (root == null) {
            str.append("Null,");
        } else {
            str.append(root.val).append(",");
            rserialize(root.left, str);
            rserialize(root.right, str);
        }
    }

    public String serialize(TreeNode root) {
        StringBuilder strRes = new StringBuilder();
        rserialize(root, strRes);
        return strRes.toString();
    }

    public TreeNode rdeserialize(List<String> list) {
        if ("Null".equals(list.get(0))) {
            list.remove(0);
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(list.get(0)));
        list.remove(0);
        root.left = rdeserialize(list);
        root.right = rdeserialize(list);
        return root;
    }

    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        List<String> dataList = new LinkedList<>(Arrays.asList(dataArray));
        return rdeserialize(dataList);
    }
}

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
class LongestPalindromicSubstring {
    /**
     * 中心扩散
     */
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            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) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        // left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
        // right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }

    /**
     * 动态规划：
     * dp[i][j]表示字符串s[i...j]是否为回文串
     * 状态转移方程：dp[i][j] = (s[i]==s[j]) and dp[i+1][j-1]
     * 边界条件：j-1 - (i+1) + 1 < 2，整理得：j-i < 3
     * 初始化，单个字符是回文串：dp[i][i] = true
     */
    public String longestPalindrome1(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        int maxLen = 1;
        int begin = 0;
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                }
                // 边界条件
                else if (j - i < 3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
                // 如果是回文串并且更长，更新长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class WordPattern {
    public boolean wordPattern(String pattern, String str) {
        Map<Character, String> hashMap = new HashMap<>();
        String[] array = str.split(" ");
        if (pattern.length() != array.length) {
            return false;
        }
        for (int i = 0; i < pattern.length(); i++) {
            char patternI = pattern.charAt(i);
            if (hashMap.containsKey(patternI)) {
                if (!hashMap.get(patternI).equals(array[i])) {
                    return false;
                }
            } else {
                if (hashMap.containsValue(array[i])) {
                    return false;
                }
                hashMap.put(patternI, array[i]);
            }
        }
        return true;
    }
}

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
class GroupAnagrams {
    /**
     * 统计每个字符的次数作为key
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> hashMap = new HashMap<>();
        for (String str : strs) {
            // 统计26个字母次数作为key
            int[] num = new int[26];
            for (int j = 0; j < str.length(); j++) {
                num[str.charAt(j) - 'a']++;
            }
            StringBuilder sKey = new StringBuilder();
            for (int i : num) {
                sKey.append(i);
            }
            String key = sKey.toString();
            if (hashMap.containsKey(key)) {
                hashMap.get(key).add(str);
            } else {
                hashMap.put(key, new LinkedList<>(Collections.singleton(str)));
            }
        }
        return new ArrayList<>(hashMap.values());
    }

    /**
     * 把每个字符串都映射到一个正数上。
     * 算术基本定理，又称为正整数的唯一分解定理，即：
     * 每个大于1的自然数，要么本身就是质数，要么可以写为2个以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。
     */
    public List<List<String>> groupAnagrams2(String[] strs) {
        HashMap<Integer, List<String>> hashMap = new HashMap<>();
        // 每个字母对应一个质数
        int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
        for (String str : strs) {
            int key = 1;
            // 累乘得到 key
            for (int j = 0; j < str.length(); j++) {
                key *= prime[str.charAt(j) - 'a'];
            }
            if (hashMap.containsKey(key)) {
                hashMap.get(key).add(str);
            } else {
                hashMap.put(key, new LinkedList<>(Collections.singleton(str)));
            }
        }
        return new ArrayList<>(hashMap.values());
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class LongestSubstringWithoutRepeatingCharacters {
    public int lengthOfLongestSubstring(String s) {
        int start = 0, maxLen = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            Character key = s.charAt(i);
            if (map.containsKey(key)) {
                start = Math.max(map.get(key) + 1, start);
            }
            map.put(key, i);
            maxLen = Math.max(maxLen, i - start + 1);
        }
        return maxLen;
    }
}

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
class RepeatedDnaSequences {
    /**
     * HashSet
     */
    public List<String> findRepeatedDnaSequences(String s) {
        HashSet<String> hashSet = new HashSet<>();
        HashSet<String> res = new HashSet<>();
        for (int i = 0; i <= s.length() - 10; i++) {
            String key = s.substring(i, i + 10);
            if (hashSet.contains(key)) {
                res.add(key);
            } else {
                hashSet.add(key);
            }
        }
        return new ArrayList<>(res);
    }

    /**
     * 位运算
     * 二进制映射map：A -> 00, C -> 01, G -> 10, T -> 11
     * 用int存储，一般情况下是32位的，只有10个字母，每个字母对应两位，所以只需要 20 位，
     * 把key和 11111111111111111111(0xfffff) 进行按位与，只保留低 20 位，
     * 所以更新 key 的话需要三个步骤，左移两位 -> 加上当前的字母 -> 按位与操作。
     * <p>
     * 更新策略：
     * 不用map，字母本质上就是一个数字，至于对应关系就是 ASCII 码值。
     * A -> 65 1000001
     * C -> 65 1000011
     * G -> 65 1000111
     * T -> 65 1010100
     * 只用低三位就可以区分这四个字母了。
     * 每次移3位，因为每个字母对应三位，10个字母总共需要30位，所以把key和(0x3fffffff)也就是30个1进行按位与。
     */
    public List<String> findRepeatedDnaSequences2(String s) {
        if (s.length() < 10) {
            return new ArrayList<>();
        }
        Set<String> res = new HashSet<>();
        Set<Integer> set = new HashSet<>();
        int key = 0;
        char[] array = s.toCharArray();
        for (int i = 0; i < 10; i++) {
            key <<= 3;
            key |= (array[i] & 7);
        }
        set.add(key);
        for (int i = 10; i < s.length(); i++) {
            key <<= 3;
            key |= (array[i] & 7);
            key &= 0x3fffffff;
            if (set.contains(key)) {
                res.add(s.substring(i - 9, i + 1));
            } else {
                set.add(key);
            }
        }
        return new ArrayList<>(res);
    }
}