LeetCode Hot 100

发表于 更新于 分类于

LeetCode Hot 100 · Java 题解

按你给的《面试百题》分类风格整理,并补全为 Hot 100 的 100 题 Java 版本。
默认都选主流面试里最稳、时间复杂度最优或综合最优的写法。
参考你的原始分类结构与题目风格:

哈希

1. 两数之和

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (map.containsKey(need)) return new int[]{map.get(need), i};
            map.put(nums[i], i);
        }
        return new int[0];
    }
}

2. 字母异位词分组

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] arr = s.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

3. 最长连续序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        int ans = 0;
        for (int x : set) {
            if (set.contains(x - 1)) continue;
            int cur = x, len = 1;
            while (set.contains(cur + 1)) {
                cur++;
                len++;
            }
            ans = Math.max(ans, len);
        }
        return ans;
    }
}

双指针

4. 移动零

1
2
3
4
5
6
7
class Solution {
    public void moveZeroes(int[] nums) {
        int k = 0;
        for (int x : nums) if (x != 0) nums[k++] = x;
        while (k < nums.length) nums[k++] = 0;
    }
}

5. 盛最多水的容器

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1, ans = 0;
        while (l < r) {
            ans = Math.max(ans, (r - l) * Math.min(height[l], height[r]));
            if (height[l] < height[r]) l++;
            else r--;
        }
        return ans;
    }
}

6. 三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum < 0) l++;
                else if (sum > 0) r--;
                else {
                    ans.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                }
            }
        }
        return ans;
    }
}

7. 接雨水

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1;
        int lMax = 0, rMax = 0, ans = 0;
        while (l < r) {
            lMax = Math.max(lMax, height[l]);
            rMax = Math.max(rMax, height[r]);
            if (lMax < rMax) ans += lMax - height[l++];
            else ans += rMax - height[r--];
        }
        return ans;
    }
}

滑动窗口 / 子串

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

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] cnt = new int[128];
        int l = 0, ans = 0;
        for (int r = 0; r < s.length(); r++) {
            cnt[s.charAt(r)]++;
            while (cnt[s.charAt(r)] > 1) cnt[s.charAt(l++)]--;
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        if (s.length() < p.length()) return ans;
        int[] need = new int[26], win = new int[26];
        for (char c : p.toCharArray()) need[c - 'a']++;
        int m = p.length();
        for (int i = 0; i < s.length(); i++) {
            win[s.charAt(i) - 'a']++;
            if (i >= m) win[s.charAt(i - m) - 'a']--;
            if (i >= m - 1 && Arrays.equals(need, win)) ans.add(i - m + 1);
        }
        return ans;
    }
}

10. 和为 K 的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0, ans = 0;
        for (int x : nums) {
            sum += x;
            ans += map.getOrDefault(sum - k, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return ans;
    }
}

11. 滑动窗口最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new ArrayDeque<>();
        int[] ans = new int[nums.length - k + 1];
        int idx = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
            dq.offerLast(i);
            if (i >= k - 1) ans[idx++] = nums[dq.peekFirst()];
        }
        return ans;
    }
}

12. 最小覆盖子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";
        int[] cnt = new int[128];
        for (char c : t.toCharArray()) cnt[c]--;
        int debt = t.length(), l = 0, start = 0, minLen = Integer.MAX_VALUE;
        for (int r = 0; r < s.length(); r++) {
            if (++cnt[s.charAt(r)] <= 0) debt--;
            while (debt == 0) {
                if (r - l + 1 < minLen) {
                    minLen = r - l + 1;
                    start = l;
                }
                if (--cnt[s.charAt(l++)] < 0) debt++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

普通数组

13. 最大子数组和

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxSubArray(int[] nums) {
        int cur = nums[0], ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]);
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}

14. 合并区间

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> res = new ArrayList<>();
        for (int[] cur : intervals) {
            if (res.isEmpty() || res.get(res.size() - 1)[1] < cur[0]) res.add(cur);
            else res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], cur[1]);
        }
        return res.toArray(new int[0][]);
    }
}

15. 轮转数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
    private void reverse(int[] a, int l, int r) {
        while (l < r) {
            int t = a[l];
            a[l++] = a[r];
            a[r--] = t;
        }
    }
}

16. 除自身以外数组的乘积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        ans[0] = 1;
        for (int i = 1; i < n; i++) ans[i] = ans[i - 1] * nums[i - 1];
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] *= suffix;
            suffix *= nums[i];
        }
        return ans;
    }
}

17. 缺失的第一个正数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                int idx = nums[i] - 1;
                int t = nums[i];
                nums[i] = nums[idx];
                nums[idx] = t;
            }
        }
        for (int i = 0; i < n; i++) if (nums[i] != i + 1) return i + 1;
        return n + 1;
    }
}

矩阵

18. 矩阵置零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean row0 = false, col0 = false;
        for (int j = 0; j < n; j++) if (matrix[0][j] == 0) row0 = true;
        for (int i = 0; i < m; i++) if (matrix[i][0] == 0) col0 = true;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }
        if (row0) Arrays.fill(matrix[0], 0);
        if (col0) for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
}

19. 螺旋矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) ans.add(matrix[top][j]);
            top++;
            for (int i = top; i <= bottom; i++) ans.add(matrix[i][right]);
            right--;
            if (top <= bottom) for (int j = right; j >= left; j--) ans.add(matrix[bottom][j]);
            bottom--;
            if (left <= right) for (int i = bottom; i >= top; i--) ans.add(matrix[i][left]);
            left++;
        }
        return ans;
    }
}

20. 旋转图像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int t = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = t;
            }
        }
        for (int[] row : matrix) {
            int l = 0, r = n - 1;
            while (l < r) {
                int t = row[l];
                row[l++] = row[r];
                row[r--] = t;
            }
        }
    }
}

21. 搜索二维矩阵 II

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0, j = matrix[0].length - 1;
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] == target) return true;
            if (matrix[i][j] > target) j--;
            else i++;
        }
        return false;
    }
}

链表

22. 相交链表

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        while (a != b) {
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }
        return a;
    }
}

23. 反转链表

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

24. 回文链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode prev = null;
        while (slow != null) {
            ListNode next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        }
        while (prev != null) {
            if (prev.val != head.val) return false;
            prev = prev.next;
            head = head.next;
        }
        return true;
    }
}

25. 环形链表

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

26. 合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0), cur = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 != null ? list1 : list2;
        return dummy.next;
    }
}

27. 两数相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), cur = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int sum = carry;
            if (l1 != null) { sum += l1.val; l1 = l1.next; }
            if (l2 != null) { sum += l2.val; l2 = l2.next; }
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            carry = sum / 10;
        }
        return dummy.next;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy, slow = dummy;
        for (int i = 0; i < n; i++) fast = fast.next;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

29. 两两交换链表中的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head), cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            ListNode a = cur.next, b = a.next;
            a.next = b.next;
            b.next = a;
            cur.next = b;
            cur = a;
        }
        return dummy.next;
    }
}

30. 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
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head), pre = dummy;
        while (true) {
            ListNode tail = pre;
            for (int i = 0; i < k && tail != null; i++) tail = tail.next;
            if (tail == null) break;
            ListNode next = tail.next;
            ListNode[] pair = reverse(pre.next, tail);
            pre.next = pair[0];
            pair[1].next = next;
            pre = pair[1];
        }
        return dummy.next;
    }
    private ListNode[] reverse(ListNode head, ListNode tail) {
        ListNode prev = tail.next, cur = head;
        while (prev != tail) {
            ListNode nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        return new ListNode[]{tail, head};
    }
}

31. 随机链表的复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        for (Node cur = head; cur != null; cur = cur.next.next) {
            Node copy = new Node(cur.val);
            copy.next = cur.next;
	            cur.next = copy;
        }
        for (Node cur = head; cur != null; cur = cur.next.next) {
            if (cur.random != null) cur.next.random = cur.random.next;
        }
        Node dummy = new Node(0), tail = dummy;
        for (Node cur = head; cur != null; ) {
            Node copy = cur.next;
            cur.next = copy.next;
            tail.next = copy;
            tail = copy;
            cur = cur.next;
        }
        return dummy.next;
    }
}

32. 排序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        slow.next = null;
        return merge(sortList(head), sortList(mid));
    }
    private ListNode merge(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0), cur = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { cur.next = a; a = a.next; }
            else { cur.next = b; b = b.next; }
            cur = cur.next;
        }
        cur.next = a != null ? a : b;
        return dummy.next;
    }
}

二叉树

33. 二叉树的中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Deque<TreeNode> st = new ArrayDeque<>();
        while (root != null || !st.isEmpty()) {
            while (root != null) {
                st.push(root);
                root = root.left;
            }
            root = st.pop();
            ans.add(root.val);
            root = root.right;
        }
        return ans;
    }
}

34. 二叉树的最大深度

1
2
3
4
5
6
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

35. 翻转二叉树

1
2
3
4
5
6
7
8
9
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode tmp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(tmp);
        return root;
    }
}

36. 对称二叉树

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null || check(root.left, root.right);
    }
    private boolean check(TreeNode a, TreeNode b) {
        if (a == null || b == null) return a == b;
        return a.val == b.val && check(a.left, b.right) && check(a.right, b.left);
    }
}

37. 二叉树的直径

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    int ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return ans;
    }
    private int depth(TreeNode node) {
        if (node == null) return 0;
        int l = depth(node.left), r = depth(node.right);
        ans = Math.max(ans, l + r);
        return 1 + Math.max(l, r);
    }
}

38. 二叉树的层序遍历

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }
    private TreeNode build(int[] nums, int l, int r) {
        if (l > r) return null;
        int m = l + (r - l) / 2;
        TreeNode root = new TreeNode(nums[m]);
        root.left = build(nums, l, m - 1);
        root.right = build(nums, m + 1, r);
        return root;
    }
}

40. 验证二叉搜索树

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean isValidBST(TreeNode root) {
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean dfs(TreeNode node, long low, long high) {
        if (node == null) return true;
        if (node.val <= low || node.val >= high) return false;
        return dfs(node.left, low, node.val) && dfs(node.right, node.val, high);
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> st = new ArrayDeque<>();
        while (true) {
            while (root != null) {
                st.push(root);
                root = root.left;
            }
            root = st.pop();
            if (--k == 0) return root.val;
            root = root.right;
        }
    }
}

42. 二叉树的右视图

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

43. 二叉树展开为链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public void flatten(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode pre = cur.left;
                while (pre.right != null) pre = pre.right;
                pre.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    private Map<Integer, Integer> idx = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++)  idx.put(inorder[i], i);
        return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }
    
    private TreeNode build(int[] pre, int pl, int pr, int il, int ir) {
        if (pl > pr) return null;
        int rootVal = pre[pl], k = idx.get(rootVal), leftSize = k - il;
        TreeNode root = new TreeNode(rootVal);
        root.left = build(pre, pl + 1, pl + leftSize, il, k - 1);
        root.right = build(pre, pl + leftSize + 1, pr, k + 1, ir);
        return root;
    }
}

45. 路径总和 III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> map = new HashMap<>();
        map.put(0L, 1);
        return dfs(root, 0L, targetSum, map);
    }
    private int dfs(TreeNode node, long sum, int target, Map<Long, Integer> map) {
        if (node == null) return 0;
        sum += node.val;
        int ans = map.getOrDefault(sum - target, 0);
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        ans += dfs(node.left, sum, target, map);
        ans += dfs(node.right, sum, target, map);
        map.put(sum, map.get(sum) - 1);
        return ans;
    }
}

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

1
2
3
4
5
6
7
8
9
10
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) return right;
        if (right == null) return left;
        return root;
    }
}

图论

47. 岛屿数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length, ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    ans++;
                    dfs(grid, i, j);
                }
            }
        }
        return ans;
    }
    private void dfs(char[][] g, int i, int j) {
        if (i < 0 || j < 0 || i >= g.length || j >= g[0].length || g[i][j] != '1') return;
        g[i][j] = '0';
        dfs(g, i + 1, j);
        dfs(g, i - 1, j);
        dfs(g, i, j + 1);
        dfs(g, i, j - 1);
    }
}

48. 腐烂的橘子

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 orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length, fresh = 0, minutes = 0;
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) q.offer(new int[]{i, j});
                else if (grid[i][j] == 1) fresh++;
            }
        }
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (fresh > 0 && !q.isEmpty()) {
            int size = q.size();
            minutes++;
            for (int k = 0; k < size; k++) {
                int[] cur = q.poll();
                for (int[] d : dirs) {
                    int x = cur[0] + d[0], y = cur[1] + d[1];
                    if (x >= 0 && y >= 0 && x < m && y < n && grid[x][y] == 1) {
                        grid[x][y] = 2;
                        fresh--;
                        q.offer(new int[]{x, y});
                    }
                }
            }
        }
        return fresh == 0 ? minutes : -1;
    }
}

49. 课程表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] g = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++) g[i] = new ArrayList<>();
        int[] indeg = new int[numCourses];
        for (int[] e : prerequisites) {
            g[e[1]].add(e[0]);
            indeg[e[0]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);
        int cnt = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            cnt++;
            for (int v : g[u]) if (--indeg[v] == 0) q.offer(v);
        }
        return cnt == numCourses;
    }
}

50. 实现 Trie

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
class Trie {
    class Node {
        Node[] next = new Node[26];
        boolean end;
    }
    private final Node root = new Node();
    public void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (cur.next[idx] == null) cur.next[idx] = new Node();
            cur = cur.next[idx];
        }
        cur.end = true;
    }
    public boolean search(String word) {
        Node node = find(word);
        return node != null && node.end;
    }
    public boolean startsWith(String prefix) {
        return find(prefix) != null;
    }
    private Node find(String s) {
        Node cur = root;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (cur.next[idx] == null) return null;
            cur = cur.next[idx];
        }
        return cur;
    }
}

51. 单词拆分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

52. 除法求值

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 Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, List<Pair>> g = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            String a = equations.get(i).get(0), b = equations.get(i).get(1);
            g.computeIfAbsent(a, k -> new ArrayList<>()).add(new Pair(b, values[i]));
            g.computeIfAbsent(b, k -> new ArrayList<>()).add(new Pair(a, 1.0 / values[i]));
        }
        double[] ans = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String s = queries.get(i).get(0), t = queries.get(i).get(1);
            if (!g.containsKey(s) || !g.containsKey(t)) ans[i] = -1.0;
            else if (s.equals(t)) ans[i] = 1.0;
            else ans[i] = bfs(g, s, t);
        }
        return ans;
    }
    private double bfs(Map<String, List<Pair>> g, String s, String t) {
        Queue<Pair2> q = new LinkedList<>();
        Set<String> vis = new HashSet<>();
        q.offer(new Pair2(s, 1.0));
        vis.add(s);
        while (!q.isEmpty()) {
            Pair2 cur = q.poll();
            if (cur.node.equals(t)) return cur.val;
            for (Pair nxt : g.get(cur.node)) {
                if (vis.add(nxt.to)) q.offer(new Pair2(nxt.to, cur.val * nxt.w));
            }
        }
        return -1.0;
    }
    class Pair { String to; double w; Pair(String t, double w) { this.to = t; this.w = w; } }
    class Pair2 { String node; double val; Pair2(String n, double v) { node = n; val = v; } }
}

53. 岛屿的最大面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) ans = Math.max(ans, dfs(grid, i, j));
            }
        }
        return ans;
    }
    private int dfs(int[][] g, int i, int j) {
        if (i < 0 || j < 0 || i >= g.length || j >= g[0].length || g[i][j] == 0) return 0;
        g[i][j] = 0;
        return 1 + dfs(g, i + 1, j) + dfs(g, i - 1, j) + dfs(g, i, j + 1) + dfs(g, i, j - 1);
    }
}

54. 省份数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length, ans = 0;
        boolean[] vis = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                ans++;
                dfs(isConnected, vis, i);
            }
        }
        return ans;
    }
    private void dfs(int[][] g, boolean[] vis, int u) {
        vis[u] = true;
        for (int v = 0; v < g.length; v++) {
            if (g[u][v] == 1 && !vis[v]) dfs(g, vis, v);
        }
    }
}

回溯

55. 全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        dfs(nums, used, new ArrayList<>(), ans);
        return ans;
    }
    private void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.add(nums[i]);
            dfs(nums, used, path, ans);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

56. 子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(nums, 0, new ArrayList<>(), ans);
        return ans;
    }
    private void dfs(int[] nums, int idx, List<Integer> path, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(path));
        for (int i = idx; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums, i + 1, path, ans);
            path.remove(path.size() - 1);
        }
    }
}

57. 电话号码的字母组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    private static final String[] MAP = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits.length() == 0) return ans;
        dfs(digits, 0, new StringBuilder(), ans);
        return ans;
    }
    private void dfs(String digits, int idx, StringBuilder path, List<String> ans) {
        if (idx == digits.length()) {
            ans.add(path.toString());
            return;
        }
        String s = MAP[digits.charAt(idx) - '0'];
        for (char c : s.toCharArray()) {
            path.append(c);
            dfs(digits, idx + 1, path, ans);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

58. 组合总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(candidates, target, 0, new ArrayList<>(), ans);
        return ans;
    }
    private void dfs(int[] c, int target, int idx, List<Integer> path, List<List<Integer>> ans) {
        if (target == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = idx; i < c.length; i++) {
            if (c[i] > target) continue;
            path.add(c[i]);
            dfs(c, target - c[i], i, path, ans);
            path.remove(path.size() - 1);
        }
    }
}

59. 括号生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        dfs(n, 0, 0, new StringBuilder(), ans);
        return ans;
    }
    private void dfs(int n, int open, int close, StringBuilder path, List<String> ans) {
        if (path.length() == 2 * n) {
            ans.add(path.toString());
            return;
        }
        if (open < n) {
            path.append('(');
            dfs(n, open + 1, close, path, ans);
            path.deleteCharAt(path.length() - 1);
        }
        if (close < open) {
            path.append(')');
            dfs(n, open, close + 1, path, ans);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

60. 单词搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }
    private boolean dfs(char[][] b, String w, int i, int j, int k) {
        if (k == w.length()) return true;
        if (i < 0 || j < 0 || i >= b.length || j >= b[0].length || b[i][j] != w.charAt(k)) return false;
        char tmp = b[i][j];
        b[i][j] = '#';
        boolean ok = dfs(b, w, i + 1, j, k + 1) || dfs(b, w, i - 1, j, k + 1)
                || dfs(b, w, i, j + 1, k + 1) || dfs(b, w, i, j - 1, k + 1);
        b[i][j] = tmp;
        return ok;
    }
}

61. 分割回文串

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 Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<>();
        dfs(s, 0, new ArrayList<>(), ans);
        return ans;
    }
    private void dfs(String s, int start, List<String> path, List<List<String>> ans) {
        if (start == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (isPal(s, start, end)) {
                path.add(s.substring(start, end + 1));
                dfs(s, end + 1, path, ans);
                path.remove(path.size() - 1);
            }
        }
    }
    private boolean isPal(String s, int l, int r) {
        while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
        return true;
    }
}

62. 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
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    int cols;
    List<List<String>> ans = new ArrayList<>();
    
    public List<List<String>> solveNQueens(int n) {
        cols=n;
        boolean col[] = new boolean[n];
        boolean l[] = new boolean[2*n-1]; //r-c+n-1
        boolean r[] = new boolean[2*n-1]; //r+c
        int[] qpos=new int[n]; //用来存每行的q在哪一列
        dfs(0,col,l,r,qpos);
        return ans;
    }

  

    public void dfs(int currow,boolean col[], boolean l[],boolean r[],int qpos[]){
        if(currow==cols){
            List<String>one = new ArrayList<>(cols); //有n行
            for(int c : qpos){
                char[] row = new char[cols];
                Arrays.fill(row,'.');
                row[c]='Q';
                one.add(new String(row));
            }
            ans.add(one);
        }

  

        //在当前行遍历每一列, 看看是否有违规的

        for(int i=0;i<cols;i++){
            int rval=currow+i;
            int lval=currow-i+cols-1;
            if(!col[i]&&!l[lval]&&!r[rval]){
                qpos[currow]=i;
                col[i]=true;
                l[lval]=true;
                r[rval]=true;
                dfs(currow+1,col,l,r,qpos);
                
                col[i]=false;
                l[lval]=false;
                r[rval]=false;
            }
        }
    }
}

二分查找

63. 搜索插入位置

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] < target) l = m + 1;
            else r = m;
        }
        return l;
    }
}

64. 搜索二维矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int l = 0, r = m * n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int x = matrix[mid / n][mid % n];
            if (x == target) return true;
            if (x < target) l = mid + 1;
            else r = mid - 1;
        }
        return false;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = lower(nums, target);
        int right = lower(nums, target + 1) - 1;
        if (left == nums.length || nums[left] != target) return new int[]{-1, -1};
        return new int[]{left, right};
    }
    private int lower(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] < target) l = m + 1;
            else r = m;
        }
        return l;
    }
}

66. 搜索旋转排序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] == target) return m;

            if (nums[l] <= nums[m]) {  //左边是有序的
                if (nums[l] <= target && target < nums[m]) r = m - 1; //如果在左边, 则收紧有边界
                else l = m + 1; //否则跳过此处
            } else { //右边是有序的
                if (nums[m] < target && target <= nums[r]) l = m + 1; //如果在右边, 则收紧右边界
                else r = m - 1;
            }
        }
        return -1;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] > nums[r]) l = m + 1;
            else r = m;
        }
        return nums[l];
    }
}

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

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

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int len1=nums1.length, len2=nums2.length;

        if(nums1.length>nums2.length) return findMedianSortedArrays(nums2,nums1);

  

        int l=0,r=nums1.length;

        int totalleft=(len1+len2+1)/2;

        while(l<=r){

            int i = l+(r-l)/2;

            int j = totalleft-i;

  

            int l1= (i==0)?Integer.MIN_VALUE:nums1[i-1];

            int r1= (i==len1)?Integer.MAX_VALUE:nums1[i];

  

            int l2= (j==0)?Integer.MIN_VALUE:nums2[j-1];

            int r2= (j==len2)?Integer.MAX_VALUE:nums2[j];

  

            /* 1  3   8   9   15

               7  11  18  19  21  25

            */

            if(l1<=r2&&l2<=r1){

                if((len1+len2)%2==1){

                    return Math.max(l1,l2);

                }else {

                    //想想他们是紧靠在一起的, 那么中位数肯定为左最大右最小啊!

                    return (Math.max(l1,l2)+Math.min(r1,r2))/2.0;

                }

            }else if(l1>r2){

                r=i-1;

            }else l=i+1;

        }

        return 0.0;

    }

}

69. 寻找峰值

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] > nums[m + 1]) r = m;
            else l = m + 1;
        }
        return l;
    }
}

栈

70. 有效的括号

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean isValid(String s) {
        Deque<Character> st = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(') st.push(')');
            else if (c == '[') st.push(']');
            else if (c == '{') st.push('}');
            else if (st.isEmpty() || st.pop() != c) return false;
        }
        return st.isEmpty();
    }
}

71. 最小栈

1
2
3
4
5
6
7
8
9
10
11
12
13
class MinStack {
    Deque<Integer> st = new ArrayDeque<>();
    Deque<Integer> minSt = new ArrayDeque<>();
    public void push(int val) {
        st.push(val);
        if (minSt.isEmpty() || val <= minSt.peek()) minSt.push(val);
    }
    public void pop() {
        if (st.pop().equals(minSt.peek())) minSt.pop();
    }
    public int top() { return st.peek(); }
    public int getMin() { return minSt.peek(); }
}

72. 字符串解码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String decodeString(String s) {
        Deque<Integer> numSt = new ArrayDeque<>();
        Deque<StringBuilder> strSt = new ArrayDeque<>();
        StringBuilder cur = new StringBuilder();
        int num = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) num = num * 10 + c - '0';
            else if (c == '[') {
                numSt.push(num);
                strSt.push(cur);
                num = 0;
                cur = new StringBuilder();
            } else if (c == ']') {
                int k = numSt.pop();
                StringBuilder prev = strSt.pop();
                while (k-- > 0) prev.append(cur);
                cur = prev;
            } else cur.append(c);
        }
        return cur.toString();
    }
}

73. 每日温度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && temperatures[i] > temperatures[st.peek()]) {
                int idx = st.pop();
                ans[idx] = i - idx;
            }
            st.push(i);
        }
        return ans;
    }
}

74. 柱状图中最大的矩形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length, ans = 0;
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i <= n; i++) {
            int h = i == n ? 0 : heights[i];
            while (!st.isEmpty() && heights[st.peek()] > h) {
                int cur = heights[st.pop()];
                int left = st.isEmpty() ? -1 : st.peek();
                ans = Math.max(ans, cur * (i - left - 1));
            }
            st.push(i);
        }
        return ans;
    }
}

堆 / 优先队列

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

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : nums) {
            pq.offer(x);
            if (pq.size() > k) pq.poll();
        }
        return pq.peek();
    }
}

76. 前 K 个高频元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums) map.put(x, map.getOrDefault(x, 0) + 1);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        for (var e : map.entrySet()) {
            pq.offer(new int[]{e.getKey(), e.getValue()});
            if (pq.size() > k) pq.poll();
        }
        int[] ans = new int[k];
        for (int i = k - 1; i >= 0; i--) ans[i] = pq.poll()[0];
        return ans;
    }
}

77. 数据流的中位数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class MedianFinder {
    PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> b - a);
    PriorityQueue<Integer> right = new PriorityQueue<>();
    public void addNum(int num) {
        if (left.isEmpty() || num <= left.peek()) left.offer(num);
        else right.offer(num);
        if (left.size() > right.size() + 1) right.offer(left.poll());
        if (right.size() > left.size()) left.offer(right.poll());
    }
    public double findMedian() {
        if (left.size() > right.size()) return left.peek();
        return (left.peek() + right.peek()) / 2.0;
    }
}

贪心

78. 买卖股票的最佳时机

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE, ans = 0;
        for (int p : prices) {
            min = Math.min(min, p);
            ans = Math.max(ans, p - min);
        }
        return ans;
    }
}

79. 跳跃游戏

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean canJump(int[] nums) {
        int far = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > far) return false;
            far = Math.max(far, i + nums[i]);
        }
        return true;
    }
}

80. 跳跃游戏 II

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int jump(int[] nums) {
        int end = 0, far = 0, steps = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            far = Math.max(far, i + nums[i]);
            if (i == end) {
                steps++;
                end = far;
            }
        }
        return steps;
    }
}

81. 划分字母区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
        List<Integer> ans = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) {
                ans.add(end - start + 1);
                start = i + 1;
            }
        }
        return ans;
    }
}

82. 杨辉三角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) row.add(1);
                else row.add(ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j));
            }
            ans.add(row);
        }
        return ans;
    }
}

技巧 / 位运算 / 数组结论题

83. 只出现一次的数字

1
2
3
4
5
6
7
class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int x : nums) ans ^= x;
        return ans;
    }
}

84. 多数元素

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0, cnt = 0;
        for (int x : nums) {
            if (cnt == 0) candidate = x;
            cnt += (x == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

85. 颜色分类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0, i = 0, p2 = nums.length - 1;
        while (i <= p2) {
            if (nums[i] == 0) {
                int t = nums[i]; nums[i] = nums[p0]; nums[p0] = t;
                i++; p0++;
            } else if (nums[i] == 2) {
                int t = nums[i]; nums[i] = nums[p2]; nums[p2] = t;
                p2--;
            } else i++;
        }
    }
}

86. 下一个排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[j] <= nums[i]) j--;
            swap(nums, i, j);
        }
        reverse(nums, i + 1, nums.length - 1);
    }
    private void swap(int[] nums, int i, int j) {
        int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
    }
    private void reverse(int[] nums, int l, int r) {
        while (l < r) swap(nums, l++, r--);
    }
}

87. 寻找重复数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0], fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

动态规划

88. 爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}

89. 打家劫舍

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int rob(int[] nums) {
        int prev2 = 0, prev1 = 0;
        for (int x : nums) {
            int cur = Math.max(prev1, prev2 + x);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

90. 完全平方数

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
        return dp[n];
    }
}

91. 零钱兑换

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int c : coins) if (i >= c) dp[i] = Math.min(dp[i], dp[i - c] + 1);
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

92. 最长递增子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tail = new int[nums.length];
        int size = 0;
        for (int x : nums) {
            int l = 0, r = size;
            while (l < r) {
                int m = l + (r - l) / 2;
                if (tail[m] < x) l = m + 1;
                else r = m;
            }
            tail[l] = x;
            if (l == size) size++;
        }
        return size;
    }
}

93. 乘积最大子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0], min = nums[0], ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            if (x < 0) {
                int t = max;
                max = min;
                min = t;
            }
            max = Math.max(x, max * x);
            min = Math.min(x, min * x);
            ans = Math.max(ans, max);
        }
        return ans;
    }
}

94. 分割等和子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums) sum += x;
        if ((sum & 1) == 1) return false;
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int x : nums) {
            for (int j = target; j >= x; j--) dp[j] = dp[j] || dp[j - x];
        }
        return dp[target];
    }
}

95. 最长有效括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];
        int ans = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                else {
                    int pre = i - dp[i - 1] - 1;
                    if (pre >= 0 && s.charAt(pre) == '(') {
                        dp[i] = dp[i - 1] + 2 + (pre >= 1 ? dp[pre - 1] : 0);
                    }
                }
                ans = Math.max(ans, dp[i]);
            }
        }
        return ans;
    }
}

96. 不同路径

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) dp[j] += dp[j - 1];
        }
        return dp[n - 1];
    }
}

97. 最小路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];
        dp[0] = grid[0][0];
        for (int j = 1; j < n; j++) dp[j] = dp[j - 1] + grid[0][j];
        for (int i = 1; i < m; i++) {
            dp[0] += grid[i][0];
            for (int j = 1; j < n; j++) dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
        }
        return dp[n - 1];
    }
}

98. 最长回文子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String longestPalindrome(String s) {
        if (s.length() < 2) return s;
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expand(s, i, i);
            int len2 = expand(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start + 1) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    private int expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return r - l - 1;
    }
}

99. 最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }
}

100. 编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        }
        return dp[m][n];
    }
}

使用建议

  1. 这份更适合你拿去二刷、三刷,先按分类建立题感。
  2. 每题自己再补一行:时间复杂度 / 空间复杂度。
  3. 真正面试前,重点盯这几类:链表、二叉树、回溯、DP、图、二分。
  4. 如果你后面要,我可以继续给你做:
    • 带复杂度版
    • 带思路注释版
    • 适合 Obsidian 直接导入版
    • 按“一周刷题计划”拆分版