LeetCode 高频200题 - Java题解

, , , , , ,

按面试出现频率从高到低排序，每道题包含题目描述、解题思路分析和Java实现。适合架构师面试前快速复习算法基本功。

难度标记

  • 🟢 Easy
  • 🟡 Medium
  • 🔴 Hard

1. 🟡 两数之和（Two Sum）- LeetCode 1

题目：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数的下标。

分析：暴力解法O(n²)，用HashMap存储已遍历的值和下标，一次遍历O(n)解决。面试最高频题，考察哈希表的基本应用。

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

时间复杂度：O(n)，空间复杂度：O(n)

2. 🟡 两数相加（Add Two Numbers）- LeetCode 2

题目：两个非空链表表示两个非负整数（逆序存储），返回它们的和，同样用链表表示。

分析：模拟竖式加法，逐位相加并处理进位。注意最后可能还有进位需要新增节点。链表操作基本功。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = 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; }
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
    }
    return dummy.next;
}

时间复杂度：O(max(m,n))，空间复杂度：O(max(m,n))

3. 🟡 无重复字符的最长子串（Longest Substring Without Repeating Characters）- LeetCode 3

题目：给定一个字符串，找出不含重复字符的最长子串的长度。

分析：经典滑动窗口题。用HashSet或数组记录窗口内的字符，右指针扩展窗口，遇到重复字符时左指针收缩。

1
2
3
4
5
6
7
8
9
10
public int lengthOfLongestSubstring(String s) {
    int[] index = new int[128]; // 记录字符最后出现的位置+1
    int maxLen = 0, left = 0;
    for (int right = 0; right < s.length(); right++) {
        left = Math.max(left, index[s.charAt(right)]);
        maxLen = Math.max(maxLen, right - left + 1);
        index[s.charAt(right)] = right + 1;
    }
    return maxLen;
}

时间复杂度：O(n)，空间复杂度：O(1)（固定128大小数组）

4. 🔴 寻找两个正序数组的中位数（Median of Two Sorted Arrays）- LeetCode 4

题目：给定两个正序数组，找出这两个数组的中位数，要求时间复杂度O(log(m+n))。

分析：二分查找。在较短的数组上二分，找到一个分割点使得左半部分的最大值≤右半部分的最小值。面试Hard题经典代表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
    int m = nums1.length, n = nums2.length;
    int lo = 0, hi = m;
    while (lo <= hi) {
        int i = (lo + hi) / 2;
        int j = (m + n + 1) / 2 - i;
        int maxLeft1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
        int minRight1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
        int maxLeft2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
        int minRight2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            if ((m + n) % 2 == 0)
                return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
            else
                return Math.max(maxLeft1, maxLeft2);
        } else if (maxLeft1 > minRight2) {
            hi = i - 1;
        } else {
            lo = i + 1;
        }
    }
    return 0;
}

时间复杂度：O(log(min(m,n)))，空间复杂度：O(1)

5. 🟡 最长回文子串（Longest Palindromic Substring）- LeetCode 5

题目：给定一个字符串，找到最长的回文子串。

分析：中心扩展法最直观。每个字符（和每两个相邻字符之间）作为中心向两边扩展。也可以用动态规划或Manacher算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public String longestPalindrome(String s) {
    int start = 0, maxLen = 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 > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;
        }
    }
    return s.substring(start, start + maxLen);
}

private int expand(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--; right++;
    }
    return right - left - 1;
}

时间复杂度：O(n²)，空间复杂度：O(1)

6. 🟡 盛最多水的容器（Container With Most Water）- LeetCode 11

题目：给定n个非负整数表示n条垂线，找出两条线与x轴构成的容器能容纳最多的水。

分析：双指针从两端向中间收缩。每次移动较短的那条线，因为移动较长的线不可能得到更大的面积。贪心思想。

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

时间复杂度：O(n)，空间复杂度：O(1)

7. 🟡 三数之和（3Sum）- LeetCode 15

题目：找出数组中所有和为0的三元组，不能包含重复的三元组。

分析：排序+双指针。固定一个数，对剩余部分用双指针找两数之和。关键是去重逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++) {
        if (nums[i] > 0) break;
        if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++; right--;
            } else if (sum < 0) left++;
            else right--;
        }
    }
    return res;
}

时间复杂度：O(n²)，空间复杂度：O(1)（不计输出）

8. 🟡 电话号码的字母组合（Letter Combinations of a Phone Number）- LeetCode 17

题目：给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。

分析：经典回溯题。每个数字对应几个字母，逐位选择，递归生成所有组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<String> letterCombinations(String digits) {
    List<String> res = new ArrayList<>();
    if (digits.isEmpty()) return res;
    String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    backtrack(res, new StringBuilder(), digits, map, 0);
    return res;
}

private void backtrack(List<String> res, StringBuilder sb, String digits, String[] map, int idx) {
    if (idx == digits.length()) { res.add(sb.toString()); return; }
    for (char c : map[digits.charAt(idx) - '0'].toCharArray()) {
        sb.append(c);
        backtrack(res, sb, digits, map, idx + 1);
        sb.deleteCharAt(sb.length() - 1);
    }
}

时间复杂度：O(4^n)，空间复杂度：O(n)

9. 🟡 删除链表的倒数第N个节点（Remove Nth Node From End of List）- LeetCode 19

题目：删除链表的倒数第n个节点，返回链表头节点。要求一趟扫描。

分析：快慢指针。快指针先走n步，然后快慢指针同时走，快指针到末尾时慢指针指向待删除节点的前一个。

1
2
3
4
5
6
7
8
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 != null) { fast = fast.next; slow = slow.next; }
    slow.next = slow.next.next;
    return dummy.next;
}

时间复杂度：O(L)，空间复杂度：O(1)

10. 🟢 有效的括号（Valid Parentheses）- LeetCode 20

题目：给定一个只包含括号的字符串，判断是否有效（正确闭合）。

分析：栈的经典应用。遇到左括号入栈，遇到右括号检查栈顶是否匹配。

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

时间复杂度：O(n)，空间复杂度：O(n)

11. 🟢 合并两个有序链表（Merge Two Sorted Lists）- LeetCode 21

题目：将两个升序链表合并为一个新的升序链表。

分析：双指针逐一比较，也可以递归实现。基础链表操作。

1
2
3
4
5
6
7
8
9
10
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
        else { curr.next = l2; l2 = l2.next; }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

时间复杂度：O(m+n)，空间复杂度：O(1)

12. 🟡 括号生成（Generate Parentheses）- LeetCode 22

题目：生成所有由n对括号组成的有效组合。

分析：回溯法。维护左括号和右括号的剩余数量，左括号可以随时放，右括号只有在剩余数量大于左括号时才能放。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    backtrack(res, new StringBuilder(), 0, 0, n);
    return res;
}

private void backtrack(List<String> res, StringBuilder sb, int open, int close, int n) {
    if (sb.length() == 2 * n) { res.add(sb.toString()); return; }
    if (open < n) {
        sb.append('('); backtrack(res, sb, open + 1, close, n); sb.deleteCharAt(sb.length() - 1);
    }
    if (close < open) {
        sb.append(')'); backtrack(res, sb, open, close + 1, n); sb.deleteCharAt(sb.length() - 1);
    }
}

时间复杂度：O(4^n/√n)（卡特兰数），空间复杂度：O(n)

13. 🔴 合并K个升序链表（Merge k Sorted Lists）- LeetCode 23

题目：合并k个升序链表，返回合并后的升序链表。

分析：优先队列（最小堆）。将每个链表的头节点入堆，每次取最小的节点，再将其next入堆。也可以分治合并。

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode node : lists) if (node != null) pq.offer(node);
    ListNode dummy = new ListNode(0), curr = dummy;
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        curr.next = node;
        curr = curr.next;
        if (node.next != null) pq.offer(node.next);
    }
    return dummy.next;
}

时间复杂度：O(N·log k)，空间复杂度：O(k)

14. 🟡 下一个排列（Next Permutation）- LeetCode 31

题目：找出数组的下一个字典序排列。如果已经是最大排列，则重排为最小排列。

分析：从右往左找第一个下降的位置i，再从右往左找第一个大于nums[i]的位置j，交换后反转i+1到末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
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--); }

时间复杂度：O(n)，空间复杂度：O(1)

15. 🔴 最长有效括号（Longest Valid Parentheses）- LeetCode 32

题目：给定一个只包含’(‘和’)’的字符串，找出最长有效括号子串的长度。

分析：用栈存储下标。栈底保持最后一个未匹配的右括号下标作为分隔符。也可以用DP或双向扫描。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int longestValidParentheses(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1);
    int max = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.isEmpty()) stack.push(i);
            else max = Math.max(max, i - stack.peek());
        }
    }
    return max;
}

时间复杂度：O(n)，空间复杂度：O(n)

16. 🟡 搜索旋转排序数组（Search in Rotated Sorted Array）- LeetCode 33

题目：在旋转排序数组中搜索目标值，要求O(log n)。

分析：二分查找变体。每次判断哪半边是有序的，再判断target是否在有序的那半边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[lo] <= nums[mid]) { // 左半有序
            if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else { // 右半有序
            if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

时间复杂度：O(log n)，空间复杂度：O(1)

17. 🟡 在排序数组中查找元素的第一个和最后一个位置（Find First and Last Position）- LeetCode 34

题目：在排序数组中找到目标值的起始和结束位置，要求O(log n)。

分析：两次二分查找，分别找左边界和右边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] searchRange(int[] nums, int target) {
    return new int[]{findBound(nums, target, true), findBound(nums, target, false)};
}

private int findBound(int[] nums, int target, boolean isLeft) {
    int lo = 0, hi = nums.length - 1, result = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) {
            result = mid;
            if (isLeft) hi = mid - 1; else lo = mid + 1;
        } else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return result;
}

时间复杂度：O(log n)，空间复杂度：O(1)

18. 🟡 组合总和（Combination Sum）- LeetCode 39

题目：给定无重复元素的数组和目标值，找出所有和为目标值的组合，数字可以重复使用。

分析：回溯法。每次可以选择当前数字（不前进）或跳过当前数字（前进到下一个）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(candidates);
    backtrack(res, new ArrayList<>(), candidates, target, 0);
    return res;
}

private void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums, int remain, int start) {
    if (remain == 0) { res.add(new ArrayList<>(path)); return; }
    for (int i = start; i < nums.length && nums[i] <= remain; i++) {
        path.add(nums[i]);
        backtrack(res, path, nums, remain - nums[i], i); // i不变，可重复使用
        path.remove(path.size() - 1);
    }
}

时间复杂度：O(n^(T/M))，T为target，M为最小候选数，空间复杂度：O(T/M)

19. 🔴 接雨水（Trapping Rain Water）- LeetCode 42

题目：给定n个非负整数表示柱子高度，计算能接多少雨水。

分析：双指针法。每个位置能接的水=min(左边最高, 右边最高) - 当前高度。双指针从两端向中间移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            leftMax = Math.max(leftMax, height[left]);
            water += leftMax - height[left];
            left++;
        } else {
            rightMax = Math.max(rightMax, height[right]);
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

时间复杂度：O(n)，空间复杂度：O(1)

20. 🟡 全排列（Permutations）- LeetCode 46

题目：给定一个不含重复数字的数组，返回其所有可能的全排列。

分析：回溯法经典题。用visited数组标记已使用的数字，递归生成排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(res, new ArrayList<>(), nums, new boolean[nums.length]);
    return res;
}

private void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums, boolean[] used) {
    if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        path.add(nums[i]);
        backtrack(res, path, nums, used);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

时间复杂度：O(n·n!)，空间复杂度：O(n)

21. 🟡 旋转图像（Rotate Image）- LeetCode 48

题目：将n×n矩阵顺时针旋转90度，要求原地旋转。

分析：先沿主对角线转置，再每行左右翻转。两步操作等价于顺时针旋转90度。

1
2
3
4
5
6
7
8
9
10
11
12
13
public void rotate(int[][] matrix) {
    int n = matrix.length;
    // 转置
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            int tmp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = tmp;
        }
    // 每行翻转
    for (int i = 0; i < n; i++)
        for (int l = 0, r = n - 1; l < r; l++, r--) {
            int tmp = matrix[i][l]; matrix[i][l] = matrix[i][r]; matrix[i][r] = tmp;
        }
}

时间复杂度：O(n²)，空间复杂度：O(1)

22. 🟡 字母异位词分组（Group Anagrams）- LeetCode 49

题目：给定一个字符串数组，将字母异位词组合在一起。

分析：将每个字符串排序后作为key，相同key的字符串是异位词。也可以用字符计数数组作为key。

1
2
3
4
5
6
7
8
9
10
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());
}

时间复杂度：O(n·k·log k)，k为字符串最大长度，空间复杂度：O(n·k)

23. 🟡 最大子数组和（Maximum Subarray）- LeetCode 53

题目：找到一个具有最大和的连续子数组，返回其最大和。

分析：Kadane算法。维护当前子数组和，如果和变负则重新开始。动态规划思想：dp[i] = max(nums[i], dp[i-1]+nums[i])。

1
2
3
4
5
6
7
8
public int maxSubArray(int[] nums) {
    int maxSum = nums[0], curSum = nums[0];
    for (int i = 1; i < nums.length; i++) {
        curSum = Math.max(nums[i], curSum + nums[i]);
        maxSum = Math.max(maxSum, curSum);
    }
    return maxSum;
}

时间复杂度：O(n)，空间复杂度：O(1)

24. 🟡 跳跃游戏（Jump Game）- LeetCode 55

题目：给定非负整数数组，每个元素代表在该位置可以跳跃的最大长度，判断是否能到达最后一个位置。

分析：贪心。维护能到达的最远位置，遍历过程中如果当前位置超过最远位置则不可达。

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

时间复杂度：O(n)，空间复杂度：O(1)

25. 🟡 合并区间（Merge Intervals）- LeetCode 56

题目：合并所有重叠的区间。

分析：按起始位置排序，然后逐个合并。如果当前区间的起始≤上一个区间的结束，则合并。

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

时间复杂度：O(n·log n)，空间复杂度：O(n)

26. 🟡 不同路径（Unique Paths）- LeetCode 62

题目：m×n网格，从左上角到右下角，每次只能向下或向右移动一步，有多少条不同路径。

分析：动态规划。dp[i][j] = dp[i-1][j] + dp[i][j-1]。可以优化为一维数组。

1
2
3
4
5
6
7
8
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];
}

时间复杂度：O(m·n)，空间复杂度：O(n)

27. 🟡 最小路径和（Minimum Path Sum）- LeetCode 64

题目：m×n网格中每个格子有非负整数，找到从左上角到右下角的路径使得路径上数字总和最小。

分析：动态规划。dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。可以原地修改grid节省空间。

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

时间复杂度：O(m·n)，空间复杂度：O(1)

28. 🟢 爬楼梯（Climbing Stairs）- LeetCode 70

题目：每次可以爬1或2个台阶，有多少种不同的方法爬到n阶。

分析：斐波那契数列。dp[i] = dp[i-1] + dp[i-2]。只需要两个变量。

1
2
3
4
5
6
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;
}

时间复杂度：O(n)，空间复杂度：O(1)

29. 🔴 最小覆盖子串（Minimum Window Substring）- LeetCode 76

题目：给定字符串s和t，找出s中包含t所有字符的最小子串。

分析：滑动窗口。右指针扩展直到包含t的所有字符，然后左指针收缩找最小窗口。用数组计数比HashMap快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public String minWindow(String s, String t) {
    int[] need = new int[128], window = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    int left = 0, count = 0, minLen = Integer.MAX_VALUE, start = 0;
    int required = 0;
    for (int c : need) if (c > 0) required++;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        window[c]++;
        if (window[c] == need[c]) count++;
        while (count == required) {
            if (right - left + 1 < minLen) { minLen = right - left + 1; start = left; }
            char lc = s.charAt(left);
            if (window[lc] == need[lc]) count--;
            window[lc]--;
            left++;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

时间复杂度：O(m+n)，空间复杂度：O(1)

30. 🟡 子集（Subsets）- LeetCode 78

题目：给定一组不含重复元素的整数数组，返回所有可能的子集。

分析：回溯法。每个元素选或不选，也可以用位运算枚举。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(res, new ArrayList<>(), nums, 0);
    return res;
}

private void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums, int start) {
    res.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(res, path, nums, i + 1);
        path.remove(path.size() - 1);
    }
}

时间复杂度：O(n·2^n)，空间复杂度：O(n)

31. 🟡 单词搜索（Word Search）- LeetCode 79

题目：给定m×n网格和一个单词，判断单词是否存在于网格中（相邻单元格水平或垂直连接）。

分析：DFS回溯。从每个格子出发尝试匹配，用原地修改标记已访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean exist(char[][] board, String word) {
    for (int i = 0; i < board.length; i++)
        for (int j = 0; j < board[0].length; j++)
            if (dfs(board, word, i, j, 0)) return true;
    return false;
}

private boolean dfs(char[][] board, String word, int i, int j, int k) {
    if (k == word.length()) return true;
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(k))
        return false;
    char tmp = board[i][j];
    board[i][j] = '#';
    boolean found = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1)
                 || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k + 1);
    board[i][j] = tmp;
    return found;
}

时间复杂度：O(m·n·3^L)，L为单词长度，空间复杂度：O(L)

32. 🔴 柱状图中最大的矩形（Largest Rectangle in Histogram）- LeetCode 84

题目：给定n个非负整数表示柱状图中各柱子的高度，找出能勾勒出的最大矩形面积。

分析：单调栈。维护一个递增栈，遇到更矮的柱子时弹出计算面积。

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

时间复杂度：O(n)，空间复杂度：O(n)

33. 🟡 二叉树的中序遍历（Binary Tree Inorder Traversal）- LeetCode 94

题目：给定二叉树的根节点，返回中序遍历结果。

分析：递归简单，迭代用栈模拟。Morris遍历可以O(1)空间。

1
2
3
4
5
6
7
8
9
10
11
12
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) { stack.push(curr); curr = curr.left; }
        curr = stack.pop();
        res.add(curr.val);
        curr = curr.right;
    }
    return res;
}

时间复杂度：O(n)，空间复杂度：O(n)

34. 🟡 不同的二叉搜索树（Unique Binary Search Trees）- LeetCode 96

题目：给定n，求1到n为节点组成的二叉搜索树有多少种。

分析：卡特兰数。dp[n] = Σ dp[i-1]*dp[n-i]，i从1到n。以i为根，左子树i-1个节点，右子树n-i个节点。

1
2
3
4
5
6
7
8
public int numTrees(int n) {
    int[] dp = new int[n + 1];
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= i; j++)
            dp[i] += dp[j - 1] * dp[i - j];
    return dp[n];
}

时间复杂度：O(n²)，空间复杂度：O(n)

35. 🟡 验证二叉搜索树（Validate Binary Search Tree）- LeetCode 98

题目：判断给定二叉树是否是有效的二叉搜索树。

分析：中序遍历应该是严格递增的。也可以递归传递上下界。

1
2
3
4
5
6
7
8
9
public boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return validate(node.left, min, node.val) && validate(node.right, node.val, max);
}

时间复杂度：O(n)，空间复杂度：O(h)，h为树高

36. 🟢 对称二叉树（Symmetric Tree）- LeetCode 101

题目：判断二叉树是否是镜像对称的。

分析：递归比较左子树和右子树。左子树的左孩子=右子树的右孩子，左子树的右孩子=右子树的左孩子。

1
2
3
4
5
6
7
8
9
public boolean isSymmetric(TreeNode root) {
    return root == null || isMirror(root.left, root.right);
}

private boolean isMirror(TreeNode l, TreeNode r) {
    if (l == null && r == null) return true;
    if (l == null || r == null) return false;
    return l.val == r.val && isMirror(l.left, r.right) && isMirror(l.right, r.left);
}

时间复杂度：O(n)，空间复杂度：O(h)

37. 🟡 二叉树的层序遍历（Binary Tree Level Order Traversal）- LeetCode 102

题目：返回二叉树的层序遍历结果（逐层从左到右）。

分析：BFS用队列。每层处理队列中当前所有节点。

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

时间复杂度：O(n)，空间复杂度：O(n)

38. 🟢 二叉树的最大深度（Maximum Depth of Binary Tree）- LeetCode 104

题目：给定二叉树，找出其最大深度。

分析：递归。当前节点的深度 = 1 + max(左子树深度, 右子树深度)。

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

时间复杂度：O(n)，空间复杂度：O(h)

39. 🟡 从前序与中序遍历序列构造二叉树（Construct Binary Tree）- LeetCode 105

题目：根据前序遍历和中序遍历构造二叉树。

分析：前序第一个元素是根，在中序中找到根的位置，左边是左子树，右边是右子树，递归构建。用HashMap加速查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) map.put(inorder[i], i);
    return build(preorder, 0, preorder.length - 1, 0, map);
}

private TreeNode build(int[] preorder, int preStart, int preEnd, int inStart, Map<Integer, Integer> map) {
    if (preStart > preEnd) return null;
    TreeNode root = new TreeNode(preorder[preStart]);
    int inRoot = map.get(root.val);
    int leftSize = inRoot - inStart;
    root.left = build(preorder, preStart + 1, preStart + leftSize, inStart, map);
    root.right = build(preorder, preStart + leftSize + 1, preEnd, inRoot + 1, map);
    return root;
}

时间复杂度：O(n)，空间复杂度：O(n)

40. 🟡 二叉树展开为链表（Flatten Binary Tree to Linked List）- LeetCode 114

题目：将二叉树展开为单链表（按前序遍历顺序，用right指针连接）。

分析：对每个节点，将左子树插入到当前节点和右子树之间。找到左子树的最右节点连接原右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
public void flatten(TreeNode root) {
    TreeNode curr = root;
    while (curr != null) {
        if (curr.left != null) {
            TreeNode rightmost = curr.left;
            while (rightmost.right != null) rightmost = rightmost.right;
            rightmost.right = curr.right;
            curr.right = curr.left;
            curr.left = null;
        }
        curr = curr.right;
    }
}

时间复杂度：O(n)，空间复杂度：O(1)

41. 🔴 买卖股票的最佳时机 III（Best Time to Buy and Sell Stock III）- LeetCode 123

题目：最多可以完成两笔交易，求最大利润。

分析：维护四个状态：第一次买入、第一次卖出、第二次买入、第二次卖出的最大利润。

1
2
3
4
5
6
7
8
9
10
11
public int maxProfit(int[] prices) {
    int buy1 = Integer.MIN_VALUE, sell1 = 0;
    int buy2 = Integer.MIN_VALUE, sell2 = 0;
    for (int p : prices) {
        buy1 = Math.max(buy1, -p);
        sell1 = Math.max(sell1, buy1 + p);
        buy2 = Math.max(buy2, sell1 - p);
        sell2 = Math.max(sell2, buy2 + p);
    }
    return sell2;
}

时间复杂度：O(n)，空间复杂度：O(1)

42. 🟢 买卖股票的最佳时机（Best Time to Buy and Sell Stock）- LeetCode 121

题目：只能买卖一次，求最大利润。

分析：遍历时维护最低价格，每天计算当天卖出的利润。

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

时间复杂度：O(n)，空间复杂度：O(1)

43. 🔴 二叉树中的最大路径和（Binary Tree Maximum Path Sum）- LeetCode 124

题目：给定二叉树，找出路径和最大的路径（路径可以从任意节点到任意节点）。

分析：后序遍历。每个节点计算经过它的最大路径和（左+右+自身），同时向上返回单边最大贡献值。

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

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

private int dfs(TreeNode node) {
    if (node == null) return 0;
    int left = Math.max(0, dfs(node.left));
    int right = Math.max(0, dfs(node.right));
    maxSum = Math.max(maxSum, left + right + node.val);
    return node.val + Math.max(left, right);
}

时间复杂度：O(n)，空间复杂度：O(h)

44. 🟡 最长连续序列（Longest Consecutive Sequence）- LeetCode 128

题目：给定未排序的整数数组，找出最长连续序列的长度，要求O(n)。

分析：HashSet存所有数。对每个数，如果num-1不存在（说明是序列起点），则向后计数。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) set.add(n);
    int max = 0;
    for (int n : set) {
        if (!set.contains(n - 1)) { // 只从序列起点开始
            int len = 1;
            while (set.contains(n + len)) len++;
            max = Math.max(max, len);
        }
    }
    return max;
}

时间复杂度：O(n)，空间复杂度：O(n)

45. 🟡 单词拆分（Word Break）- LeetCode 139

题目：给定字符串s和字典wordDict，判断s是否可以被拆分为字典中的单词。

分析：动态规划。dp[i]表示s的前i个字符是否可以被拆分。

1
2
3
4
5
6
7
8
9
public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = 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] && dict.contains(s.substring(j, i))) { dp[i] = true; break; }
    return dp[s.length()];
}

时间复杂度：O(n²·k)，k为子串比较时间，空间复杂度：O(n)

46. 🟡 环形链表 II（Linked List Cycle II）- LeetCode 142

题目：给定链表，返回环的入口节点。如果没有环返回null。

分析：快慢指针。快指针每次走2步，慢指针每次走1步。相遇后，一个指针从头开始，两个指针每次走1步，再次相遇点就是环入口。

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            ListNode p = head;
            while (p != slow) { p = p.next; slow = slow.next; }
            return p;
        }
    }
    return null;
}

时间复杂度：O(n)，空间复杂度：O(1)

47. 🟡 LRU缓存（LRU Cache）- LeetCode 146

题目：设计LRU缓存，支持get和put操作，均为O(1)时间复杂度。

分析：HashMap + 双向链表。HashMap存key到链表节点的映射，双向链表维护访问顺序。面试超高频设计题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class LRUCache {
    private Map<Integer, Node> map = new HashMap<>();
    private Node head = new Node(), tail = new Node();
    private int capacity;

    class Node {
        int key, val;
        Node prev, next;
        Node() {}
        Node(int k, int v) { key = k; val = v; }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail; tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) { node.val = value; moveToHead(node); return; }
        node = new Node(key, value);
        map.put(key, node);
        addToHead(node);
        if (map.size() > capacity) { Node tail = removeTail(); map.remove(tail.key); }
    }

    private void addToHead(Node n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }
    private void remove(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
    private void moveToHead(Node n) { remove(n); addToHead(n); }
    private Node removeTail() { Node n = tail.prev; remove(n); return n; }
}

时间复杂度：get/put均O(1)，空间复杂度：O(capacity)

48. 🟡 排序链表（Sort List）- LeetCode 148

题目：对链表进行排序，要求O(n log n)时间和O(1)空间。

分析：归并排序。快慢指针找中点，递归分割，合并两个有序链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 mergeTwoLists(sortList(head), sortList(mid));
}

private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
        else { curr.next = l2; l2 = l2.next; }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

时间复杂度：O(n·log n)，空间复杂度：O(log n)递归栈

49. 🟡 乘积最大子数组（Maximum Product Subarray）- LeetCode 152

题目：找出数组中乘积最大的连续子数组。

分析：维护当前最大值和最小值（负数乘负数可能变最大）。遇到负数时交换最大最小值。

1
2
3
4
5
6
7
8
9
10
public int maxProduct(int[] nums) {
    int max = nums[0], min = nums[0], result = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < 0) { int tmp = max; max = min; min = tmp; }
        max = Math.max(nums[i], max * nums[i]);
        min = Math.min(nums[i], min * nums[i]);
        result = Math.max(result, max);
    }
    return result;
}

时间复杂度：O(n)，空间复杂度：O(1)

50. 🟡 最小栈（Min Stack）- LeetCode 155

题目：设计一个支持push、pop、top和getMin操作的栈，getMin要求O(1)。

分析：用辅助栈同步记录每个状态下的最小值。也可以用一个栈存差值。

1
2
3
4
5
6
7
8
9
10
11
12
13
class MinStack {
    private Deque<Integer> stack = new ArrayDeque<>();
    private Deque<Integer> minStack = new ArrayDeque<>();

    public void push(int val) {
        stack.push(val);
        minStack.push(minStack.isEmpty() ? val : Math.min(val, minStack.peek()));
    }

    public void pop() { stack.pop(); minStack.pop(); }
    public int top() { return stack.peek(); }
    public int getMin() { return minStack.peek(); }
}

时间复杂度：所有操作O(1)，空间复杂度：O(n)

51. 🟡 相交链表（Intersection of Two Linked Lists）- LeetCode 160

题目：找到两个单链表相交的起始节点。

分析：双指针。A走完走B，B走完走A，两者走的总长度相同，会在交点相遇。

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

时间复杂度：O(m+n)，空间复杂度：O(1)

52. 🟡 多数元素（Majority Element）- LeetCode 169

题目：找出数组中出现次数超过n/2的元素。

分析：Boyer-Moore投票算法。维护候选人和计数，遇到相同+1，不同-1，计数为0时换候选人。

1
2
3
4
5
6
7
8
public int majorityElement(int[] nums) {
    int candidate = 0, count = 0;
    for (int n : nums) {
        if (count == 0) candidate = n;
        count += (n == candidate) ? 1 : -1;
    }
    return candidate;
}

时间复杂度：O(n)，空间复杂度：O(1)

53. 🟡 打家劫舍（House Robber）- LeetCode 198

题目：不能偷相邻的房屋，求能偷到的最大金额。

分析：动态规划。dp[i] = max(dp[i-1], dp[i-2]+nums[i])。只需两个变量。

1
2
3
4
5
public int rob(int[] nums) {
    int prev = 0, curr = 0;
    for (int n : nums) { int tmp = curr; curr = Math.max(curr, prev + n); prev = tmp; }
    return curr;
}

时间复杂度：O(n)，空间复杂度：O(1)

54. 🟡 岛屿数量（Number of Islands）- LeetCode 200

题目：给定m×n的二维网格（’1’是陆地，’0’是水），计算岛屿数量。

分析：DFS/BFS。遍历网格，遇到’1’就DFS将整个岛标记为已访问，计数+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int numIslands(char[][] grid) {
    int count = 0;
    for (int i = 0; i < grid.length; i++)
        for (int j = 0; j < grid[0].length; j++)
            if (grid[i][j] == '1') { dfs(grid, i, j); count++; }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') return;
    grid[i][j] = '0';
    dfs(grid, i + 1, j); dfs(grid, i - 1, j); dfs(grid, i, j + 1); dfs(grid, i, j - 1);
}

时间复杂度：O(m·n)，空间复杂度：O(m·n)

55. 🟡 反转链表（Reverse Linked List）- LeetCode 206

题目：反转单链表。

分析：迭代法用三个指针。也可以递归。

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

时间复杂度：O(n)，空间复杂度：O(1)

56. 🟡 课程表（Course Schedule）- LeetCode 207

题目：n门课程有先修关系，判断是否可能完成所有课程（检测有向图是否有环）。

分析：拓扑排序（BFS/Kahn算法）。计算入度，入度为0的入队，逐步删除边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] indegree = new int[numCourses];
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
    for (int[] p : prerequisites) { graph.get(p[1]).add(p[0]); indegree[p[0]]++; }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) queue.offer(i);
    int count = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll(); count++;
        for (int next : graph.get(course))
            if (--indegree[next] == 0) queue.offer(next);
    }
    return count == numCourses;
}

时间复杂度：O(V+E)，空间复杂度：O(V+E)

57. 🟡 实现Trie（前缀树）（Implement Trie）- LeetCode 208

题目：实现Trie，支持insert、search和startsWith操作。

分析：每个节点包含26个子节点指针和一个结束标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Trie {
    private Trie[] children = new Trie[26];
    private boolean isEnd;

    public void insert(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) node.children[idx] = new Trie();
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) { return searchPrefix(prefix) != null; }

    private Trie searchPrefix(String s) {
        Trie node = this;
        for (char c : s.toCharArray()) {
            node = node.children[c - 'a'];
            if (node == null) return null;
        }
        return node;
    }
}

时间复杂度：insert/search/startsWith均O(m)，m为字符串长度

58. 🟡 数组中的第K个最大元素（Kth Largest Element）- LeetCode 215

题目：找出数组中第k个最大的元素。

分析：快速选择算法（QuickSelect），平均O(n)。也可以用最小堆O(n·log k)。

1
2
3
4
5
6
7
8
public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(); // 最小堆
    for (int n : nums) {
        pq.offer(n);
        if (pq.size() > k) pq.poll();
    }
    return pq.peek();
}

时间复杂度：O(n·log k)，空间复杂度：O(k)

59. 🟡 最大正方形（Maximal Square）- LeetCode 221

题目：在由’0’和’1’组成的二维矩阵中，找到只包含’1’的最大正方形，返回其面积。

分析：动态规划。dp[i][j]表示以(i,j)为右下角的最大正方形边长。dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

1
2
3
4
5
6
7
8
9
10
11
public int maximalSquare(char[][] matrix) {
    int m = matrix.length, n = matrix[0].length, max = 0;
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (matrix[i - 1][j - 1] == '1') {
                dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                max = Math.max(max, dp[i][j]);
            }
    return max * max;
}

时间复杂度：O(m·n)，空间复杂度：O(m·n)

60. 🟢 翻转二叉树（Invert Binary Tree）- LeetCode 226

题目：翻转一棵二叉树。

分析：递归交换每个节点的左右子树。

1
2
3
4
5
6
7
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;
}

时间复杂度：O(n)，空间复杂度：O(h)

61. 🟡 回文链表（Palindrome Linked List）- LeetCode 234

题目：判断链表是否是回文链表，要求O(1)空间。

分析：快慢指针找中点，反转后半部分，逐一比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isPalindrome(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode rev = reverse(slow);
    while (rev != null) {
        if (head.val != rev.val) return false;
        head = head.next; rev = rev.next;
    }
    return true;
}

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

时间复杂度：O(n)，空间复杂度：O(1)

62. 🟡 二叉树的最近公共祖先（Lowest Common Ancestor）- LeetCode 236

题目：给定二叉树和两个节点，找到它们的最近公共祖先。

分析：递归。如果当前节点是p或q则返回当前节点。左右子树分别递归，如果左右都非空则当前节点是LCA。

1
2
3
4
5
6
7
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 && right != null) return root;
    return left != null ? left : right;
}

时间复杂度：O(n)，空间复杂度：O(h)

63. 🟡 除自身以外数组的乘积（Product of Array Except Self）- LeetCode 238

题目：给定数组，返回每个位置除自身外所有元素的乘积，不能用除法。

分析：两次遍历。第一次从左到右计算左侧乘积，第二次从右到左乘以右侧乘积。

1
2
3
4
5
6
7
8
9
public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    res[0] = 1;
    for (int i = 1; i < n; i++) res[i] = res[i - 1] * nums[i - 1];
    int right = 1;
    for (int i = n - 1; i >= 0; i--) { res[i] *= right; right *= nums[i]; }
    return res;
}

时间复杂度：O(n)，空间复杂度：O(1)（输出数组不算）

64. 🟡 滑动窗口最大值（Sliding Window Maximum）- LeetCode 239

题目：给定数组和窗口大小k，返回每个窗口中的最大值。

分析：单调递减双端队列。队列存下标，保持队列中的值递减。

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

时间复杂度：O(n)，空间复杂度：O(k)

65. 🟡 搜索二维矩阵 II（Search a 2D Matrix II）- LeetCode 240

题目：m×n矩阵，每行从左到右递增，每列从上到下递增，搜索目标值。

分析：从右上角开始。当前值大于target则左移，小于target则下移。

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

时间复杂度：O(m+n)，空间复杂度：O(1)

66. 🟡 完全平方数（Perfect Squares）- LeetCode 279

题目：给定正整数n，找到若干个完全平方数使得它们的和等于n，返回最少的数量。

分析：动态规划。dp[i] = min(dp[i - j*j] + 1)，j从1到√i。也可以用BFS。

1
2
3
4
5
6
7
8
9
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];
}

时间复杂度：O(n·√n)，空间复杂度：O(n)

67. 🟡 移动零（Move Zeroes）- LeetCode 283

题目：将数组中所有0移动到末尾，保持非零元素的相对顺序。

分析：双指针。一个指针记录非零元素应该放的位置，另一个遍历数组。

1
2
3
4
5
public void moveZeroes(int[] nums) {
    int j = 0;
    for (int i = 0; i < nums.length; i++)
        if (nums[i] != 0) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; j++; }
}

时间复杂度：O(n)，空间复杂度：O(1)

68. 🟡 寻找重复数（Find the Duplicate Number）- LeetCode 287

题目：n+1个整数在[1,n]范围内，只有一个重复数，找出它。不能修改数组，O(1)空间。

分析：Floyd判圈算法（快慢指针）。将数组看作链表（值是next指针），重复数就是环的入口。

1
2
3
4
5
6
7
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;
}

时间复杂度：O(n)，空间复杂度：O(1)

69. 🔴 最长递增子序列（Longest Increasing Subsequence）- LeetCode 300

题目：给定整数数组，找到最长严格递增子序列的长度。

分析：DP是O(n²)，贪心+二分可以O(n·log n)。维护一个tails数组，tails[i]是长度为i+1的递增子序列的最小末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int n : nums) {
        int lo = 0, hi = size;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (tails[mid] < n) lo = mid + 1; else hi = mid;
        }
        tails[lo] = n;
        if (lo == size) size++;
    }
    return size;
}

时间复杂度：O(n·log n)，空间复杂度：O(n)

70. 🟡 零钱兑换（Coin Change）- LeetCode 322

题目：给定不同面额的硬币和总金额，计算凑成总金额所需的最少硬币数。

分析：完全背包问题。dp[i]表示凑成金额i的最少硬币数。

1
2
3
4
5
6
7
8
9
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 (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

时间复杂度：O(amount·n)，空间复杂度：O(amount)

71. 🟡 打家劫舍 III（House Robber III）- LeetCode 337

题目：二叉树形的房屋，不能偷直接相连的两个节点，求最大金额。

分析：树形DP。每个节点返回两个值：偷/不偷当前节点的最大金额。

1
2
3
4
5
6
7
8
9
10
11
12
public int rob(TreeNode root) {
    int[] res = dfs(root);
    return Math.max(res[0], res[1]);
}

private int[] dfs(TreeNode node) {
    if (node == null) return new int[]{0, 0};
    int[] left = dfs(node.left), right = dfs(node.right);
    int rob = node.val + left[1] + right[1]; // 偷当前，不偷子节点
    int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); // 不偷当前
    return new int[]{rob, notRob};
}

时间复杂度：O(n)，空间复杂度：O(h)

72. 🟡 比特位计数（Counting Bits）- LeetCode 338

题目：给定整数n，返回0到n每个数的二进制中1的个数。

分析：动态规划。dp[i] = dp[i >> 1] + (i & 1)，即右移一位的结果加上最低位。

1
2
3
4
5
public int[] countBits(int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) dp[i] = dp[i >> 1] + (i & 1);
    return dp;
}

时间复杂度：O(n)，空间复杂度：O(n)

73. 🟡 前K个高频元素（Top K Frequent Elements）- LeetCode 347

题目：给定整数数组和整数k，返回出现频率前k高的元素。

分析：HashMap统计频率，然后用最小堆取前k个。也可以用桶排序O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> freq.get(a) - freq.get(b));
    for (int key : freq.keySet()) {
        pq.offer(key);
        if (pq.size() > k) pq.poll();
    }
    int[] res = new int[k];
    for (int i = 0; i < k; i++) res[i] = pq.poll();
    return res;
}

时间复杂度：O(n·log k)，空间复杂度：O(n)

74. 🟡 字符串解码（Decode String）- LeetCode 394

题目：给定编码字符串如”3[a2[c]]”，返回解码后的字符串”accaccacc”。

分析：用栈。遇到’[‘时将当前字符串和数字入栈，遇到’]’时弹出拼接。

1
2
3
4
5
6
7
8
9
10
11
12
13
public String decodeString(String s) {
    Deque<StringBuilder> strStack = new ArrayDeque<>();
    Deque<Integer> numStack = new ArrayDeque<>();
    StringBuilder curr = new StringBuilder();
    int num = 0;
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) { num = num * 10 + (c - '0'); }
        else if (c == '[') { strStack.push(curr); numStack.push(num); curr = new StringBuilder(); num = 0; }
        else if (c == ']') { StringBuilder prev = strStack.pop(); int k = numStack.pop(); for (int i = 0; i < k; i++) prev.append(curr); curr = prev; }
        else curr.append(c);
    }
    return curr.toString();
}

时间复杂度：O(n·k)，k为最大重复次数，空间复杂度：O(n)

75. 🟡 每日温度（Daily Temperatures）- LeetCode 739

题目：给定每日温度数组，返回每天需要等几天才能遇到更高温度。

分析：单调递减栈。栈中存下标，遇到更高温度时弹出并计算天数差。

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

时间复杂度：O(n)，空间复杂度：O(n)

76. 🟡 和为K的子数组（Subarray Sum Equals K）- LeetCode 560

题目：给定整数数组和整数k，找到和为k的连续子数组的个数。

分析：前缀和+HashMap。prefixSum[j] - prefixSum[i] = k，即找之前出现过的前缀和为prefixSum[j]-k的次数。

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

时间复杂度：O(n)，空间复杂度：O(n)

77. 🟡 任务调度器（Task Scheduler）- LeetCode 621

题目：给定任务数组和冷却时间n，计算完成所有任务的最短时间。

分析：贪心。最高频任务决定框架，(maxFreq-1)*(n+1)+countOfMax。与总任务数取较大值。

1
2
3
4
5
6
7
8
public int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    for (char t : tasks) freq[t - 'A']++;
    int maxFreq = 0, countMax = 0;
    for (int f : freq) maxFreq = Math.max(maxFreq, f);
    for (int f : freq) if (f == maxFreq) countMax++;
    return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + countMax);
}

时间复杂度：O(n)，空间复杂度：O(1)

78. 🟡 回文子串（Palindromic Substrings）- LeetCode 647

题目：给定字符串，计算有多少个回文子串。

分析：中心扩展法。每个位置作为中心（奇数和偶数长度），向两边扩展计数。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int countSubstrings(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        count += expand(s, i, i) + expand(s, i, i + 1);
    }
    return count;
}

private int expand(String s, int l, int r) {
    int count = 0;
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { count++; l--; r++; }
    return count;
}

时间复杂度：O(n²)，空间复杂度：O(1)

79. 🟡 目标和（Target Sum）- LeetCode 494

题目：给定数组和目标值，每个数字前可以加+或-，求有多少种方式使得总和等于目标值。

分析：转化为0-1背包。设正数和为P，则P-(S-P)=target，P=(S+target)/2。

1
2
3
4
5
6
7
8
9
10
11
12
public int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int n : nums) sum += n;
    if ((sum + target) % 2 != 0 || sum + target < 0) return 0;
    int bag = (sum + target) / 2;
    int[] dp = new int[bag + 1];
    dp[0] = 1;
    for (int n : nums)
        for (int j = bag; j >= n; j--)
            dp[j] += dp[j - n];
    return dp[bag];
}

时间复杂度：O(n·bag)，空间复杂度：O(bag)

80. 🟡 把二叉搜索树转换为累加树（Convert BST to Greater Tree）- LeetCode 538

题目：将BST转换为累加树，每个节点的值改为原树中大于等于该节点值的所有节点值之和。

分析：反向中序遍历（右-根-左），维护累加和。

1
2
3
4
5
6
7
8
9
10
11
private int sum = 0;

public TreeNode convertBST(TreeNode root) {
    if (root != null) {
        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
    }
    return root;
}

时间复杂度：O(n)，空间复杂度：O(h)

81. 🟡 二叉树的直径（Diameter of Binary Tree）- LeetCode 543

题目：给定二叉树，计算任意两个节点之间的最长路径长度。

分析：后序遍历。每个节点的直径=左子树深度+右子树深度，取全局最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
private int diameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
    depth(root);
    return diameter;
}

private int depth(TreeNode node) {
    if (node == null) return 0;
    int left = depth(node.left), right = depth(node.right);
    diameter = Math.max(diameter, left + right);
    return 1 + Math.max(left, right);
}

时间复杂度：O(n)，空间复杂度：O(h)

82. 🟡 合并二叉树（Merge Two Binary Trees）- LeetCode 617

题目：合并两棵二叉树，重叠节点值相加，不重叠的保留。

分析：递归同时遍历两棵树。

1
2
3
4
5
6
7
8
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if (t1 == null) return t2;
    if (t2 == null) return t1;
    t1.val += t2.val;
    t1.left = mergeTrees(t1.left, t2.left);
    t1.right = mergeTrees(t1.right, t2.right);
    return t1;
}

时间复杂度：O(min(m,n))，空间复杂度：O(min(h1,h2))

83. 🟡 最短无序连续子数组（Shortest Unsorted Continuous Subarray）- LeetCode 581

题目：找到最短的连续子数组，排序该子数组后整个数组变为升序。

分析：从左找右边界（最后一个小于左侧最大值的位置），从右找左边界（最后一个大于右侧最小值的位置）。

1
2
3
4
5
6
7
8
9
public int findUnsortedSubarray(int[] nums) {
    int n = nums.length, left = -1, right = -1;
    int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        if (nums[i] < max) right = i; else max = nums[i];
        if (nums[n - 1 - i] > min) left = n - 1 - i; else min = nums[n - 1 - i];
    }
    return right == -1 ? 0 : right - left + 1;
}

时间复杂度：O(n)，空间复杂度：O(1)

84. 🟢 汉明距离（Hamming Distance）- LeetCode 461

题目：计算两个整数之间的汉明距离（对应位不同的位数）。

分析：异或后统计1的个数。

1
2
3
public int hammingDistance(int x, int y) {
    return Integer.bitCount(x ^ y);
}

时间复杂度：O(1)，空间复杂度：O(1)

85. 🟡 找到所有数组中消失的数字（Find All Numbers Disappeared）- LeetCode 448

题目：n个整数在[1,n]范围内，找出所有未出现的数字，不用额外空间。

分析：原地标记。将nums[abs(nums[i])-1]取负，最后正数对应的下标+1就是缺失的数。

1
2
3
4
5
6
public List<Integer> findDisappearedNumbers(int[] nums) {
    for (int n : nums) { int idx = Math.abs(n) - 1; if (nums[idx] > 0) nums[idx] = -nums[idx]; }
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) if (nums[i] > 0) res.add(i + 1);
    return res;
}

时间复杂度：O(n)，空间复杂度：O(1)

86. 🟡 分割等和子集（Partition Equal Subset Sum）- LeetCode 416

题目：判断数组是否可以分割为两个子集，使得两个子集的元素和相等。

分析：0-1背包。目标和为sum/2，dp[j]表示是否能凑出和为j。

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

时间复杂度：O(n·target)，空间复杂度：O(target)

87. 🟡 路径总和 III（Path Sum III）- LeetCode 437

题目：二叉树中找出路径和等于目标值的路径数量（路径不需要从根开始或到叶子结束）。

分析：前缀和+HashMap。类似子数组和为K的思路，在树上用DFS+回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int pathSum(TreeNode root, int targetSum) {
    Map<Long, Integer> prefix = new HashMap<>();
    prefix.put(0L, 1);
    return dfs(root, 0, targetSum, prefix);
}

private int dfs(TreeNode node, long currSum, int target, Map<Long, Integer> prefix) {
    if (node == null) return 0;
    currSum += node.val;
    int count = prefix.getOrDefault(currSum - target, 0);
    prefix.merge(currSum, 1, Integer::sum);
    count += dfs(node.left, currSum, target, prefix) + dfs(node.right, currSum, target, prefix);
    prefix.merge(currSum, -1, Integer::sum);
    return count;
}

时间复杂度：O(n)，空间复杂度：O(h)

88. 🟡 找到字符串中所有字母异位词（Find All Anagrams）- LeetCode 438

题目：给定字符串s和p，找到s中所有p的字母异位词的起始索引。

分析：固定长度滑动窗口+字符计数数组比较。

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

时间复杂度：O(n)，空间复杂度：O(1)

89. 🟡 二叉树的右视图（Binary Tree Right Side View）- LeetCode 199

题目：给定二叉树，返回从右侧看到的节点值。

分析：BFS层序遍历，每层取最后一个节点。或DFS先访问右子树。

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

时间复杂度：O(n)，空间复杂度：O(n)

90. 🟡 螺旋矩阵（Spiral Matrix）- LeetCode 54

题目：给定m×n矩阵，按螺旋顺序返回所有元素。

分析：模拟。维护上下左右四个边界，按右→下→左→上的顺序遍历，每次遍历完收缩边界。

1
2
3
4
5
6
7
8
9
10
11
public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res = 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++) res.add(matrix[top][j]); top++;
        for (int i = top; i <= bottom; i++) res.add(matrix[i][right]); right--;
        if (top <= bottom) { for (int j = right; j >= left; j--) res.add(matrix[bottom][j]); bottom--; }
        if (left <= right) { for (int i = bottom; i >= top; i--) res.add(matrix[i][left]); left++; }
    }
    return res;
}

时间复杂度：O(m·n)，空间复杂度：O(1)

91. 🟡 螺旋矩阵 II（Spiral Matrix II）- LeetCode 59

题目：生成n×n矩阵，按螺旋顺序填入1到n²。

分析：与螺旋矩阵类似，按方向填充。

1
2
3
4
5
6
7
8
9
10
11
public int[][] generateMatrix(int n) {
    int[][] matrix = new int[n][n];
    int top = 0, bottom = n - 1, left = 0, right = n - 1, num = 1;
    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; j++) matrix[top][j] = num++; top++;
        for (int i = top; i <= bottom; i++) matrix[i][right] = num++; right--;
        for (int j = right; j >= left; j--) matrix[bottom][j] = num++; bottom--;
        for (int i = bottom; i >= top; i--) matrix[i][left] = num++; left++;
    }
    return matrix;
}

时间复杂度：O(n²)，空间复杂度：O(1)

92. 🟡 颜色分类（Sort Colors）- LeetCode 75

题目：给定包含0、1、2的数组，原地排序（荷兰国旗问题）。

分析：三指针。p0指向0的右边界，p2指向2的左边界，curr遍历。

1
2
3
4
5
6
7
8
9
10
public void sortColors(int[] nums) {
    int p0 = 0, curr = 0, p2 = nums.length - 1;
    while (curr <= p2) {
        if (nums[curr] == 0) { swap(nums, p0++, curr++); }
        else if (nums[curr] == 2) { swap(nums, curr, p2--); }
        else curr++;
    }
}

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

时间复杂度：O(n)，空间复杂度：O(1)

93. 🟡 编辑距离（Edit Distance）- LeetCode 72

题目：给定两个单词，计算将word1转换为word2所需的最少操作数（插入、删除、替换）。

分析：经典二维DP。dp[i][j]表示word1前i个字符转换为word2前j个字符的最少操作数。

1
2
3
4
5
6
7
8
9
10
11
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] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
    return dp[m][n];
}

时间复杂度：O(m·n)，空间复杂度：O(m·n)

94. 🟡 最长公共子序列（Longest Common Subsequence）- LeetCode 1143

题目：给定两个字符串，返回最长公共子序列的长度。

分析：二维DP。dp[i][j]表示text1前i个和text2前j个字符的LCS长度。

1
2
3
4
5
6
7
8
9
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++)
            dp[i][j] = (text1.charAt(i - 1) == text2.charAt(j - 1))
                ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);
    return dp[m][n];
}

时间复杂度：O(m·n)，空间复杂度：O(m·n)

95. 🟡 旋转链表（Rotate List）- LeetCode 61

题目：给定链表和k，将链表向右旋转k个位置。

分析：先连成环，然后在正确位置断开。

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null || k == 0) return head;
    int len = 1;
    ListNode tail = head;
    while (tail.next != null) { tail = tail.next; len++; }
    k %= len;
    if (k == 0) return head;
    tail.next = head; // 成环
    for (int i = 0; i < len - k; i++) tail = tail.next;
    head = tail.next;
    tail.next = null;
    return head;
}

时间复杂度：O(n)，空间复杂度：O(1)

96. 🟡 矩阵置零（Set Matrix Zeroes）- LeetCode 73

题目：如果矩阵中某个元素为0，则将其所在行和列全部置为0，要求原地。

分析：用第一行和第一列作为标记。先记录第一行和第一列是否有0，然后用它们标记其他行列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean firstRow = false, firstCol = false;
    for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRow = true;
    for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstCol = 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 (firstRow) for (int j = 0; j < n; j++) matrix[0][j] = 0;
    if (firstCol) for (int i = 0; i < m; i++) matrix[i][0] = 0;
}

时间复杂度：O(m·n)，空间复杂度：O(1)

97. 🟡 不同的二叉搜索树 II（Unique BSTs II）- LeetCode 95

题目：给定n，生成所有由1到n为节点组成的不同BST。

分析：递归。以每个数为根，左边的数构成左子树，右边的数构成右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<TreeNode> generateTrees(int n) {
    return build(1, n);
}

private List<TreeNode> build(int lo, int hi) {
    List<TreeNode> res = new ArrayList<>();
    if (lo > hi) { res.add(null); return res; }
    for (int i = lo; i <= hi; i++) {
        for (TreeNode left : build(lo, i - 1))
            for (TreeNode right : build(i + 1, hi)) {
                TreeNode root = new TreeNode(i);
                root.left = left; root.right = right;
                res.add(root);
            }
    }
    return res;
}

时间复杂度：O(4^n/√n)（卡特兰数），空间复杂度：O(4^n/√n)

98. 🟡 二叉树的锯齿形层序遍历（Zigzag Level Order Traversal）- LeetCode 103

题目：返回二叉树的锯齿形层序遍历（先左到右，再右到左，交替进行）。

分析：BFS层序遍历，奇数层反转结果。或用双端队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean leftToRight = true;
    while (!queue.isEmpty()) {
        int size = queue.size();
        LinkedList<Integer> level = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (leftToRight) level.addLast(node.val); else level.addFirst(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(level);
        leftToRight = !leftToRight;
    }
    return res;
}

时间复杂度：O(n)，空间复杂度：O(n)

99. 🟡 从中序与后序遍历序列构造二叉树（Construct Binary Tree II）- LeetCode 106

题目：根据中序遍历和后序遍历构造二叉树。

分析：后序最后一个元素是根，在中序中找到根的位置，递归构建。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public TreeNode buildTree(int[] inorder, int[] postorder) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) map.put(inorder[i], i);
    return build(postorder, 0, postorder.length - 1, 0, map);
}

private TreeNode build(int[] postorder, int postStart, int postEnd, int inStart, Map<Integer, Integer> map) {
    if (postStart > postEnd) return null;
    TreeNode root = new TreeNode(postorder[postEnd]);
    int inRoot = map.get(root.val);
    int leftSize = inRoot - inStart;
    root.left = build(postorder, postStart, postStart + leftSize - 1, inStart, map);
    root.right = build(postorder, postStart + leftSize, postEnd - 1, inRoot + 1, map);
    return root;
}

时间复杂度：O(n)，空间复杂度：O(n)

100. 🟡 二叉树的序列化与反序列化（Serialize and Deserialize Binary Tree）- LeetCode 297

题目：设计算法实现二叉树的序列化与反序列化。

分析：BFS层序遍历序列化，null用”#”表示。反序列化时用队列重建。

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 Codec {
    public String serialize(TreeNode root) {
        if (root == null) return "#";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) { sb.append("#,"); continue; }
            sb.append(node.val).append(",");
            queue.offer(node.left);
            queue.offer(node.right);
        }
        return sb.toString();
    }

    public TreeNode deserialize(String data) {
        if (data.equals("#")) return null;
        String[] vals = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (!vals[i].equals("#")) { node.left = new TreeNode(Integer.parseInt(vals[i])); queue.offer(node.left); }
            i++;
            if (!vals[i].equals("#")) { node.right = new TreeNode(Integer.parseInt(vals[i])); queue.offer(node.right); }
            i++;
        }
        return root;
    }
}

时间复杂度：O(n)，空间复杂度：O(n)

101. 🟡 最长重复子数组（Maximum Length of Repeated Subarray）- LeetCode 718

题目：给定两个整数数组，返回两个数组中公共的、长度最长的子数组的长度。

分析：二维DP。dp[i][j]表示以nums1[i-1]和nums2[j-1]结尾的最长公共子数组长度。

1
2
3
4
5
6
7
8
public int findLength(int[] nums1, int[] nums2) {
    int m = nums1.length, n = nums2.length, max = 0;
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (nums1[i - 1] == nums2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; max = Math.max(max, dp[i][j]); }
    return max;
}

时间复杂度：O(m·n)，空间复杂度：O(m·n)

102. 🟡 在排序数组中查找元素（Binary Search）- LeetCode 704

题目：标准二分查找。

分析：基础二分，注意边界条件。

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

时间复杂度：O(log n)，空间复杂度：O(1)

103. 🟡 腐烂的橘子（Rotting Oranges）- LeetCode 994

题目：网格中1是新鲜橘子，2是腐烂橘子，每分钟腐烂橘子会感染相邻的新鲜橘子。求所有橘子腐烂的最短时间。

分析：多源BFS。所有腐烂橘子同时入队，逐层扩散。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length, fresh = 0, time = 0;
    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) queue.offer(new int[]{i, j});
            else if (grid[i][j] == 1) fresh++;
        }
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!queue.isEmpty() && fresh > 0) {
        int size = queue.size(); time++;
        for (int k = 0; k < size; k++) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int ni = cell[0] + d[0], nj = cell[1] + d[1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) {
                    grid[ni][nj] = 2; fresh--; queue.offer(new int[]{ni, nj});
                }
            }
        }
    }
    return fresh == 0 ? time : -1;
}

时间复杂度：O(m·n)，空间复杂度：O(m·n)

104. 🟡 K个一组翻转链表（Reverse Nodes in k-Group）- LeetCode 25

题目：每k个节点一组进行翻转，不足k个的保持原样。

分析：先计算链表长度，然后每k个一组翻转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0, head);
    ListNode prevGroup = dummy;
    int len = 0;
    for (ListNode n = head; n != null; n = n.next) len++;
    while (len >= k) {
        ListNode curr = prevGroup.next, prev = null;
        for (int i = 0; i < k; i++) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; }
        ListNode tail = prevGroup.next;
        tail.next = curr;
        prevGroup.next = prev;
        prevGroup = tail;
        len -= k;
    }
    return dummy.next;
}

时间复杂度：O(n)，空间复杂度：O(1)

105. 🟡 最长回文子序列（Longest Palindromic Subsequence）- LeetCode 516

题目：给定字符串，找出最长回文子序列的长度。

分析：区间DP。dp[i][j]表示s[i..j]中最长回文子序列长度。

1
2
3
4
5
6
7
8
9
10
public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++)
            dp[i][j] = (s.charAt(i) == s.charAt(j)) ? dp[i + 1][j - 1] + 2 : Math.max(dp[i + 1][j], dp[i][j - 1]);
    }
    return dp[0][n - 1];
}

时间复杂度：O(n²)，空间复杂度：O(n²)

106. 🟡 复原IP地址（Restore IP Addresses）- LeetCode 93

题目：给定只包含数字的字符串，返回所有可能的有效IP地址。

分析：回溯法。每段1-3位数字，值在0-255之间，不能有前导零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<String> restoreIpAddresses(String s) {
    List<String> res = new ArrayList<>();
    backtrack(res, new ArrayList<>(), s, 0);
    return res;
}

private void backtrack(List<String> res, List<String> parts, String s, int start) {
    if (parts.size() == 4) { if (start == s.length()) res.add(String.join(".", parts)); return; }
    for (int len = 1; len <= 3 && start + len <= s.length(); len++) {
        String seg = s.substring(start, start + len);
        if ((seg.length() > 1 && seg.startsWith("0")) || Integer.parseInt(seg) > 255) continue;
        parts.add(seg);
        backtrack(res, parts, s, start + len);
        parts.remove(parts.size() - 1);
    }
}

时间复杂度：O(3^4)=O(1)，空间复杂度：O(1)

107. 🟡 单词搜索 II（Word Search II）- LeetCode 212

题目：给定m×n网格和单词列表，找出所有同时在网格和列表中出现的单词。

分析：Trie+DFS。将所有单词构建Trie，然后在网格上DFS匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<String> findWords(char[][] board, String[] words) {
    TrieNode root = new TrieNode();
    for (String w : words) { TrieNode node = root; for (char c : w.toCharArray()) { if (node.children[c-'a']==null) node.children[c-'a']=new TrieNode(); node=node.children[c-'a']; } node.word=w; }
    List<String> res = new ArrayList<>();
    for (int i = 0; i < board.length; i++)
        for (int j = 0; j < board[0].length; j++) dfs(board, i, j, root, res);
    return res;
}

private void dfs(char[][] board, int i, int j, TrieNode node, List<String> res) {
    if (i<0||i>=board.length||j<0||j>=board[0].length||board[i][j]=='#') return;
    char c = board[i][j];
    if (node.children[c-'a']==null) return;
    node = node.children[c-'a'];
    if (node.word!=null) { res.add(node.word); node.word=null; }
    board[i][j]='#';
    dfs(board,i+1,j,node,res); dfs(board,i-1,j,node,res);
    dfs(board,i,j+1,node,res); dfs(board,i,j-1,node,res);
    board[i][j]=c;
}

class TrieNode { TrieNode[] children=new TrieNode[26]; String word; }

时间复杂度：O(m·n·4^L)，空间复杂度：O(总字符数)

108. 🟡 数据流的中位数（Find Median from Data Stream）- LeetCode 295

题目：设计数据结构支持从数据流中添加数字和查找中位数。

分析：大顶堆存较小的一半，小顶堆存较大的一半。保持两个堆大小差不超过1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class MedianFinder {
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());
        if (minHeap.size() > maxHeap.size()) maxHeap.offer(minHeap.poll());
    }

    public double findMedian() {
        return maxHeap.size() > minHeap.size() ? maxHeap.peek() : (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

时间复杂度：addNum O(log n)，findMedian O(1)

109. 🟡 课程表 II（Course Schedule II）- LeetCode 210

题目：返回完成所有课程的学习顺序（拓扑排序结果）。

分析：与课程表I类似，BFS拓扑排序，记录出队顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] findOrder(int numCourses, int[][] prerequisites) {
    int[] indegree = new int[numCourses];
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
    for (int[] p : prerequisites) { graph.get(p[1]).add(p[0]); indegree[p[0]]++; }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) queue.offer(i);
    int[] order = new int[numCourses];
    int idx = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        order[idx++] = course;
        for (int next : graph.get(course)) if (--indegree[next] == 0) queue.offer(next);
    }
    return idx == numCourses ? order : new int[0];
}

时间复杂度：O(V+E)，空间复杂度：O(V+E)

110. 🟡 戳气球（Burst Balloons）- LeetCode 312

题目：n个气球，戳破第i个气球获得nums[i-1]*nums[i]*nums[i+1]硬币，求最大硬币数。

分析：区间DP。dp[i][j]表示戳破(i,j)开区间内所有气球的最大硬币数。枚举最后一个被戳破的气球k。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] val = new int[n + 2];
    val[0] = val[n + 1] = 1;
    for (int i = 0; i < n; i++) val[i + 1] = nums[i];
    int[][] dp = new int[n + 2][n + 2];
    for (int len = 1; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for (int k = i; k <= j; k++)
                dp[i][j] = Math.max(dp[i][j], dp[i][k - 1] + val[i - 1] * val[k] * val[j + 1] + dp[k + 1][j]);
        }
    return dp[1][n];
}

时间复杂度：O(n³)，空间复杂度：O(n²)

111. 🟡 除法求值（Evaluate Division）- LeetCode 399

题目：给定变量对之间的除法关系，回答查询。

分析：构建有向加权图，BFS/DFS查找路径，路径上的权重相乘。

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 double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
    Map<String, Map<String, Double>> graph = new HashMap<>();
    for (int i = 0; i < equations.size(); i++) {
        String a = equations.get(i).get(0), b = equations.get(i).get(1);
        graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, values[i]);
        graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / values[i]);
    }
    double[] res = new double[queries.size()];
    for (int i = 0; i < queries.size(); i++) {
        String src = queries.get(i).get(0), dst = queries.get(i).get(1);
        if (!graph.containsKey(src) || !graph.containsKey(dst)) { res[i] = -1.0; continue; }
        res[i] = bfs(graph, src, dst);
    }
    return res;
}

private double bfs(Map<String, Map<String, Double>> graph, String src, String dst) {
    if (src.equals(dst)) return 1.0;
    Queue<String[]> queue = new LinkedList<>(); // [node, product]
    Set<String> visited = new HashSet<>();
    Queue<Double> products = new LinkedList<>();
    queue.offer(new String[]{src}); products.offer(1.0); visited.add(src);
    while (!queue.isEmpty()) {
        String node = queue.poll()[0]; double product = products.poll();
        for (var entry : graph.get(node).entrySet()) {
            if (entry.getKey().equals(dst)) return product * entry.getValue();
            if (visited.add(entry.getKey())) { queue.offer(new String[]{entry.getKey()}); products.offer(product * entry.getValue()); }
        }
    }
    return -1.0;
}

时间复杂度：O(Q·(V+E))，空间复杂度：O(V+E)

112. 🟡 根据身高重建队列（Queue Reconstruction by Height）- LeetCode 406

题目：每个人有(h,k)，h是身高，k是前面身高≥h的人数。重建队列。

分析：贪心。按身高降序、k升序排序，然后按k值插入到对应位置。

1
2
3
4
5
6
public int[][] reconstructQueue(int[][] people) {
    Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
    List<int[]> res = new ArrayList<>();
    for (int[] p : people) res.add(p[1], p);
    return res.toArray(new int[0][]);
}

时间复杂度：O(n²)（插入操作），空间复杂度：O(n)

113. 🟡 正则表达式匹配（Regular Expression Matching）- LeetCode 10

题目：实现支持’.’和’*’的正则表达式匹配。

分析：动态规划。dp[i][j]表示s的前i个字符和p的前j个字符是否匹配。’*’可以匹配0个或多个前面的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;
    for (int j = 2; j <= n; j++) if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            char pc = p.charAt(j - 1);
            if (pc == '*') {
                dp[i][j] = dp[i][j - 2]; // 匹配0次
                if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1))
                    dp[i][j] |= dp[i - 1][j]; // 匹配1次或多次
            } else {
                dp[i][j] = dp[i - 1][j - 1] && (pc == '.' || pc == s.charAt(i - 1));
            }
        }
    return dp[m][n];
}

时间复杂度：O(m·n)，空间复杂度：O(m·n)

114. 🟡 通配符匹配（Wildcard Matching）- LeetCode 44

题目：实现支持’?’和’‘的通配符匹配。’‘匹配任意字符序列（包括空）。

分析：动态规划。与正则匹配类似但’*’语义不同。

1
2
3
4
5
6
7
8
9
10
11
12
public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;
    for (int j = 1; j <= n; j++) if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            else dp[i][j] = dp[i - 1][j - 1] && (p.charAt(j - 1) == '?' || p.charAt(j - 1) == s.charAt(i - 1));
        }
    return dp[m][n];
}

时间复杂度：O(m·n)，空间复杂度：O(m·n)

115. 🟡 最大矩形（Maximal Rectangle）- LeetCode 85

题目：给定只包含0和1的二维矩阵，找出只包含1的最大矩形面积。

分析：将每行看作柱状图的底，转化为柱状图最大矩形问题（LeetCode 84）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) return 0;
    int n = matrix[0].length, max = 0;
    int[] heights = new int[n];
    for (char[] row : matrix) {
        for (int j = 0; j < n; j++) heights[j] = row[j] == '1' ? heights[j] + 1 : 0;
        max = Math.max(max, largestRectangleArea(heights));
    }
    return max;
}

private int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    int max = 0;
    for (int i = 0; i <= heights.length; i++) {
        int h = (i == heights.length) ? 0 : heights[i];
        while (!stack.isEmpty() && h < heights[stack.peek()]) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            max = Math.max(max, height * width);
        }
        stack.push(i);
    }
    return max;
}

时间复杂度：O(m·n)，空间复杂度：O(n)

116. 🟡 跳跃游戏 II（Jump Game II）- LeetCode 45

题目：给定非负整数数组，每个元素代表最大跳跃长度，求到达最后位置的最少跳跃次数。

分析：贪心BFS。每次跳跃选择能到达最远的位置。

1
2
3
4
5
6
7
8
public int jump(int[] nums) {
    int jumps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == curEnd) { jumps++; curEnd = farthest; }
    }
    return jumps;
}

时间复杂度：O(n)，空间复杂度：O(1)

117. 🟡 最小栈的进阶 - 用队列实现栈（Implement Stack using Queues）- LeetCode 225

题目：使用队列实现栈的push、pop、top和empty操作。

分析：一个队列即可。push时将新元素入队后，把前面的元素依次出队再入队。

1
2
3
4
5
6
7
8
9
10
11
12
class MyStack {
    private Queue<Integer> queue = new LinkedList<>();

    public void push(int x) {
        queue.offer(x);
        for (int i = 0; i < queue.size() - 1; i++) queue.offer(queue.poll());
    }

    public int pop() { return queue.poll(); }
    public int top() { return queue.peek(); }
    public boolean empty() { return queue.isEmpty(); }
}

时间复杂度：push O(n)，其他O(1)

118. 🟡 用栈实现队列（Implement Queue using Stacks）- LeetCode 232

题目：使用栈实现队列的push、pop、peek和empty操作。

分析：两个栈。输入栈和输出栈。输出栈为空时将输入栈全部倒入输出栈。

1
2
3
4
5
6
7
8
class MyQueue {
    private Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();

    public void push(int x) { in.push(x); }
    public int pop() { peek(); return out.pop(); }
    public int peek() { if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop()); return out.peek(); }
    public boolean empty() { return in.isEmpty() && out.isEmpty(); }
}

时间复杂度：均摊O(1)

119. 🟡 有序矩阵中第K小的元素（Kth Smallest Element in a Sorted Matrix）- LeetCode 378

题目：n×n矩阵，每行每列升序排列，找第k小的元素。

分析：二分查找。对值域二分，统计矩阵中≤mid的元素个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int kthSmallest(int[][] matrix, int k) {
    int n = matrix.length, lo = matrix[0][0], hi = matrix[n - 1][n - 1];
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int count = 0, j = n - 1;
        for (int i = 0; i < n; i++) {
            while (j >= 0 && matrix[i][j] > mid) j--;
            count += j + 1;
        }
        if (count < k) lo = mid + 1; else hi = mid;
    }
    return lo;
}

时间复杂度：O(n·log(max-min))，空间复杂度：O(1)

120. 🟡 打乱数组（Shuffle an Array）- LeetCode 384

题目：设计算法打乱数组（Fisher-Yates洗牌算法）。

分析：从后往前遍历，每个位置随机与前面（含自身）的某个位置交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    private int[] original;
    private Random rand = new Random();

    public Solution(int[] nums) { original = nums.clone(); }

    public int[] reset() { return original.clone(); }

    public int[] shuffle() {
        int[] arr = original.clone();
        for (int i = arr.length - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
        return arr;
    }
}

时间复杂度：O(n)，空间复杂度：O(n)

121. 🟡 至少有K个重复字符的最长子串（Longest Substring with At Least K Repeating）- LeetCode 395

题目：找到字符串中每个字符出现次数都不少于k的最长子串。

分析：分治法。统计字符频率，以频率<k的字符为分割点递归处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int longestSubstring(String s, int k) {
    if (s.length() < k) return 0;
    int[] freq = new int[26];
    for (char c : s.toCharArray()) freq[c - 'a']++;
    for (int i = 0; i < s.length(); i++) {
        if (freq[s.charAt(i) - 'a'] < k) {
            int max = 0;
            for (String part : s.split(String.valueOf(s.charAt(i))))
                max = Math.max(max, longestSubstring(part, k));
            return max;
        }
    }
    return s.length();
}

时间复杂度：O(26·n)=O(n)，空间复杂度：O(n)

122. 🟡 找出数组中重复的数字（Find All Duplicates）- LeetCode 442

题目：n个整数在[1,n]范围内，某些元素出现两次，找出所有重复的数。

分析：原地标记。将nums[abs(nums[i])-1]取负，如果已经是负数说明重复。

1
2
3
4
5
6
7
8
9
public List<Integer> findDuplicates(int[] nums) {
    List<Integer> res = new ArrayList<>();
    for (int n : nums) {
        int idx = Math.abs(n) - 1;
        if (nums[idx] < 0) res.add(idx + 1);
        else nums[idx] = -nums[idx];
    }
    return res;
}

时间复杂度：O(n)，空间复杂度：O(1)

123. 🟡 无重叠区间（Non-overlapping Intervals）- LeetCode 435

题目：给定区间集合，找到需要移除的最小区间数量，使剩余区间互不重叠。

分析：贪心。按结束时间排序，尽量保留结束早的区间。

1
2
3
4
5
6
7
8
9
public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
    int count = 0, end = Integer.MIN_VALUE;
    for (int[] i : intervals) {
        if (i[0] >= end) end = i[1];
        else count++;
    }
    return count;
}

时间复杂度：O(n·log n)，空间复杂度：O(1)

124. 🟡 用最少数量的箭引爆气球（Minimum Number of Arrows）- LeetCode 452

题目：二维平面上有气球（区间表示），一支箭可以引爆所有经过的气球，求最少箭数。

分析：贪心。按结束位置排序，尽量让一支箭穿过更多气球。

1
2
3
4
5
6
7
8
9
public int findMinArrowShots(int[][] points) {
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
    int arrows = 1;
    long end = points[0][1];
    for (int i = 1; i < points.length; i++) {
        if (points[i][0] > end) { arrows++; end = points[i][1]; }
    }
    return arrows;
}

时间复杂度：O(n·log n)，空间复杂度：O(1)

125. 🟡 N叉树的层序遍历（N-ary Tree Level Order Traversal）- LeetCode 429

题目：给定N叉树，返回其层序遍历结果。

分析：BFS，与二叉树层序遍历类似，遍历所有children。

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

时间复杂度：O(n)，空间复杂度：O(n)

126. 🟡 最长递增路径（Longest Increasing Path in a Matrix）- LeetCode 329

题目：给定m×n矩阵，找出最长递增路径的长度。

分析：DFS+记忆化。每个格子的最长路径只需计算一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

public int longestIncreasingPath(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length, max = 0;
    int[][] memo = new int[m][n];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            max = Math.max(max, dfs(matrix, memo, i, j));
    return max;
}

private int dfs(int[][] matrix, int[][] memo, int i, int j) {
    if (memo[i][j] != 0) return memo[i][j];
    int max = 1;
    for (int[] d : dirs) {
        int ni = i + d[0], nj = j + d[1];
        if (ni >= 0 && ni < matrix.length && nj >= 0 && nj < matrix[0].length && matrix[ni][nj] > matrix[i][j])
            max = Math.max(max, 1 + dfs(matrix, memo, ni, nj));
    }
    return memo[i][j] = max;
}

时间复杂度：O(m·n)，空间复杂度：O(m·n)

127. 🟡 最佳买卖股票时机含冷冻期（Best Time with Cooldown）- LeetCode 309

题目：可以多次买卖股票，但卖出后有一天冷冻期。

分析：状态机DP。三个状态：持有、不持有（冷冻期）、不持有（非冷冻期）。

1
2
3
4
5
6
7
8
9
10
public int maxProfit(int[] prices) {
    int hold = Integer.MIN_VALUE, sold = 0, rest = 0;
    for (int p : prices) {
        int prevSold = sold;
        sold = hold + p;
        hold = Math.max(hold, rest - p);
        rest = Math.max(rest, prevSold);
    }
    return Math.max(sold, rest);
}

时间复杂度：O(n)，空间复杂度：O(1)

128. 🟡 最佳买卖股票时机含手续费（Best Time with Transaction Fee）- LeetCode 714

题目：可以多次买卖股票，每次交易需要手续费。

分析：两个状态：持有和不持有。

1
2
3
4
5
6
7
8
public int maxProfit(int[] prices, int fee) {
    int hold = -prices[0], cash = 0;
    for (int i = 1; i < prices.length; i++) {
        cash = Math.max(cash, hold + prices[i] - fee);
        hold = Math.max(hold, cash - prices[i]);
    }
    return cash;
}

时间复杂度：O(n)，空间复杂度：O(1)

129. 🟡 有效的数独（Valid Sudoku）- LeetCode 36

题目：判断9×9数独是否有效（已填入的数字是否合法）。

分析：用三个数组分别记录行、列、3×3宫格中数字是否出现过。

1
2
3
4
5
6
7
8
9
10
11
public boolean isValidSudoku(char[][] board) {
    boolean[][] rows = new boolean[9][9], cols = new boolean[9][9], boxes = new boolean[9][9];
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') continue;
            int num = board[i][j] - '1', box = (i / 3) * 3 + j / 3;
            if (rows[i][num] || cols[j][num] || boxes[box][num]) return false;
            rows[i][num] = cols[j][num] = boxes[box][num] = true;
        }
    return true;
}

时间复杂度：O(1)（固定81格），空间复杂度：O(1)

130. 🔴 解数独（Sudoku Solver）- LeetCode 37

题目：填充数独使每行、每列、每个3×3宫格都包含1-9。

分析：回溯法。逐格尝试1-9，用行/列/宫格的布尔数组快速判断合法性。

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 void solveSudoku(char[][] board) {
    boolean[][] rows = new boolean[9][9], cols = new boolean[9][9], boxes = new boolean[9][9];
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            if (board[i][j] != '.') {
                int num = board[i][j] - '1', box = (i / 3) * 3 + j / 3;
                rows[i][num] = cols[j][num] = boxes[box][num] = true;
            }
    solve(board, rows, cols, boxes, 0);
}

private boolean solve(char[][] board, boolean[][] rows, boolean[][] cols, boolean[][] boxes, int pos) {
    if (pos == 81) return true;
    int i = pos / 9, j = pos % 9;
    if (board[i][j] != '.') return solve(board, rows, cols, boxes, pos + 1);
    int box = (i / 3) * 3 + j / 3;
    for (int num = 0; num < 9; num++) {
        if (rows[i][num] || cols[j][num] || boxes[box][num]) continue;
        board[i][j] = (char) ('1' + num);
        rows[i][num] = cols[j][num] = boxes[box][num] = true;
        if (solve(board, rows, cols, boxes, pos + 1)) return true;
        board[i][j] = '.';
        rows[i][num] = cols[j][num] = boxes[box][num] = false;
    }
    return false;
}

时间复杂度：O(9^空格数)，空间复杂度：O(1)

131. 🟡 N皇后（N-Queens）- LeetCode 51

题目：在n×n棋盘上放置n个皇后，使它们互不攻击。

分析：回溯法。逐行放置，用三个集合记录列、主对角线、副对角线是否被占用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');
    backtrack(res, board, 0, new boolean[n], new boolean[2 * n], new boolean[2 * n]);
    return res;
}

private void backtrack(List<List<String>> res, char[][] board, int row, boolean[] cols, boolean[] diag1, boolean[] diag2) {
    int n = board.length;
    if (row == n) { List<String> list = new ArrayList<>(); for (char[] r : board) list.add(new String(r)); res.add(list); return; }
    for (int col = 0; col < n; col++) {
        if (cols[col] || diag1[row - col + n] || diag2[row + col]) continue;
        board[row][col] = 'Q'; cols[col] = diag1[row - col + n] = diag2[row + col] = true;
        backtrack(res, board, row + 1, cols, diag1, diag2);
        board[row][col] = '.'; cols[col] = diag1[row - col + n] = diag2[row + col] = false;
    }
}

时间复杂度：O(n!)，空间复杂度：O(n²)

132. 🟡 被围绕的区域（Surrounded Regions）- LeetCode 130

题目：将被’X’围绕的’O’翻转为’X’，边界上的’O’及其连通的’O’不翻转。

分析：从边界的’O’开始DFS标记为安全，然后将未标记的’O’翻转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void solve(char[][] board) {
    int m = board.length, n = board[0].length;
    for (int i = 0; i < m; i++) { dfs(board, i, 0); dfs(board, i, n - 1); }
    for (int j = 0; j < n; j++) { dfs(board, 0, j); dfs(board, m - 1, j); }
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            else if (board[i][j] == '#') board[i][j] = 'O';
        }
}

private void dfs(char[][] board, int i, int j) {
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O') return;
    board[i][j] = '#';
    dfs(board, i + 1, j); dfs(board, i - 1, j); dfs(board, i, j + 1); dfs(board, i, j - 1);
}

时间复杂度：O(m·n)，空间复杂度：O(m·n)

133. 🟡 克隆图（Clone Graph）- LeetCode 133

题目：给定无向连通图中一个节点的引用，返回该图的深拷贝。

分析：DFS/BFS + HashMap记录已克隆的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
public Node cloneGraph(Node node) {
    if (node == null) return null;
    Map<Node, Node> map = new HashMap<>();
    return dfs(node, map);
}

private Node dfs(Node node, Map<Node, Node> map) {
    if (map.containsKey(node)) return map.get(node);
    Node clone = new Node(node.val);
    map.put(node, clone);
    for (Node neighbor : node.neighbors) clone.neighbors.add(dfs(neighbor, map));
    return clone;
}

时间复杂度：O(V+E)，空间复杂度：O(V)

134. 🟡 单词接龙（Word Ladder）- LeetCode 127

题目：给定起始单词和结束单词以及字典，每次只能改变一个字母，求最短转换序列长度。

分析：BFS。每个单词是图中的节点，相差一个字母的单词之间有边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> dict = new HashSet<>(wordList);
    if (!dict.contains(endWord)) return 0;
    Queue<String> queue = new LinkedList<>();
    queue.offer(beginWord);
    int level = 1;
    while (!queue.isEmpty()) {
        int size = queue.size(); level++;
        for (int i = 0; i < size; i++) {
            char[] word = queue.poll().toCharArray();
            for (int j = 0; j < word.length; j++) {
                char orig = word[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == orig) continue;
                    word[j] = c;
                    String next = new String(word);
                    if (next.equals(endWord)) return level;
                    if (dict.remove(next)) queue.offer(next);
                }
                word[j] = orig;
            }
        }
    }
    return 0;
}

时间复杂度：O(n·m·26)，n为字典大小，m为单词长度

135. 🟡 最小路径和变体 - 三角形最小路径和（Triangle）- LeetCode 120

题目：给定三角形，找出从顶到底的最小路径和。

分析：自底向上DP。dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]。

1
2
3
4
5
6
7
8
public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();
    int[] dp = new int[n + 1];
    for (int i = n - 1; i >= 0; i--)
        for (int j = 0; j <= i; j++)
            dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
    return dp[0];
}

时间复杂度：O(n²)，空间复杂度：O(n)

136. 🟡 分割回文串（Palindrome Partitioning）- LeetCode 131

题目：将字符串分割成若干子串，使每个子串都是回文串，返回所有可能的分割方案。

分析：回溯+预处理回文判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<List<String>> partition(String s) {
    int n = s.length();
    boolean[][] isPalin = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--)
        for (int j = i; j < n; j++)
            isPalin[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || isPalin[i + 1][j - 1]);
    List<List<String>> res = new ArrayList<>();
    backtrack(res, new ArrayList<>(), s, isPalin, 0);
    return res;
}

private void backtrack(List<List<String>> res, List<String> path, String s, boolean[][] isPalin, int start) {
    if (start == s.length()) { res.add(new ArrayList<>(path)); return; }
    for (int end = start; end < s.length(); end++) {
        if (isPalin[start][end]) {
            path.add(s.substring(start, end + 1));
            backtrack(res, path, s, isPalin, end + 1);
            path.remove(path.size() - 1);
        }
    }
}

时间复杂度：O(n·2^n)，空间复杂度：O(n²)

137. 🟡 复制带随机指针的链表（Copy List with Random Pointer）- LeetCode 138

题目：深拷贝带有random指针的链表。

分析：三步法：1.在每个节点后插入拷贝节点 2.设置拷贝节点的random 3.拆分链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public Node copyRandomList(Node head) {
    if (head == null) return null;
    // 插入拷贝节点
    for (Node curr = head; curr != null; ) {
        Node copy = new Node(curr.val);
        copy.next = curr.next; curr.next = copy; curr = copy.next;
    }
    // 设置random
    for (Node curr = head; curr != null; curr = curr.next.next)
        if (curr.random != null) curr.next.random = curr.random.next;
    // 拆分
    Node newHead = head.next;
    for (Node curr = head; curr != null; ) {
        Node copy = curr.next; curr.next = copy.next;
        copy.next = (curr.next != null) ? curr.next.next : null;
        curr = curr.next;
    }
    return newHead;
}

时间复杂度：O(n)，空间复杂度：O(1)

138. 🟡 两两交换链表中的节点（Swap Nodes in Pairs）- LeetCode 24

题目：两两交换链表中相邻的节点。

分析：迭代法，用dummy节点简化边界处理。

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

时间复杂度：O(n)，空间复杂度：O(1)

139. 🟡 整数转罗马数字（Integer to Roman）- LeetCode 12

题目：将整数转换为罗马数字。

分析：贪心。从大到小匹配所有可能的罗马数字组合。

1
2
3
4
5
6
7
8
public String intToRoman(int num) {
    int[] vals = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
    String[] syms = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < vals.length; i++)
        while (num >= vals[i]) { sb.append(syms[i]); num -= vals[i]; }
    return sb.toString();
}

时间复杂度：O(1)，空间复杂度：O(1)

140. 🟡 字符串转换整数（String to Integer / atoi）- LeetCode 8

题目：实现atoi函数，将字符串转换为整数。

分析：处理前导空格、正负号、数字字符、溢出。状态机或直接模拟。

1
2
3
4
5
6
7
8
9
10
11
12
public int myAtoi(String s) {
    int i = 0, n = s.length(), sign = 1;
    long result = 0;
    while (i < n && s.charAt(i) == ' ') i++;
    if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) sign = s.charAt(i++) == '-' ? -1 : 1;
    while (i < n && Character.isDigit(s.charAt(i))) {
        result = result * 10 + (s.charAt(i++) - '0');
        if (result * sign > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        if (result * sign < Integer.MIN_VALUE) return Integer.MIN_VALUE;
    }
    return (int) (result * sign);
}

时间复杂度：O(n)，空间复杂度：O(1)

141. 🟡 Z字形变换（Zigzag Conversion）- LeetCode 6

题目：将字符串按Z字形排列后逐行读取。

分析：模拟。用numRows个StringBuilder，按方向交替填充。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public String convert(String s, int numRows) {
    if (numRows == 1) return s;
    StringBuilder[] rows = new StringBuilder[numRows];
    for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
    int row = 0, dir = -1;
    for (char c : s.toCharArray()) {
        rows[row].append(c);
        if (row == 0 || row == numRows - 1) dir = -dir;
        row += dir;
    }
    StringBuilder res = new StringBuilder();
    for (StringBuilder r : rows) res.append(r);
    return res.toString();
}

时间复杂度：O(n)，空间复杂度：O(n)

142. 🟡 四数之和（4Sum）- LeetCode 18

题目：找出数组中所有和为target的四元组。

分析：排序+双层循环+双指针。外两层固定两个数，内层双指针找另外两个。

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

时间复杂度：O(n³)，空间复杂度：O(1)

143. 🟡 最接近的三数之和（3Sum Closest）- LeetCode 16

题目：找出数组中三个数的和最接近target的值。

分析：排序+双指针。与三数之和类似，维护最接近的差值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int closest = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < nums.length - 2; i++) {
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (Math.abs(sum - target) < Math.abs(closest - target)) closest = sum;
            if (sum < target) left++;
            else if (sum > target) right--;
            else return target;
        }
    }
    return closest;
}

时间复杂度：O(n²)，空间复杂度：O(1)

144. 🟡 删除排序链表中的重复元素 II（Remove Duplicates II）- LeetCode 82

题目：删除排序链表中所有重复的元素，只保留原始链表中没有重复出现的元素。

分析：用dummy节点，prev指向上一个确认不重复的节点。

1
2
3
4
5
6
7
8
9
10
11
public ListNode deleteDuplicates(ListNode head) {
    ListNode dummy = new ListNode(0, head), prev = dummy;
    while (prev.next != null) {
        ListNode curr = prev.next;
        if (curr.next != null && curr.val == curr.next.val) {
            while (curr.next != null && curr.val == curr.next.val) curr = curr.next;
            prev.next = curr.next;
        } else prev = prev.next;
    }
    return dummy.next;
}

时间复杂度：O(n)，空间复杂度：O(1)

145. 🟡 反转链表 II（Reverse Linked List II）- LeetCode 92

题目：反转链表从位置left到right的部分。

分析：找到left前一个节点，然后用头插法逐个反转。

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy = new ListNode(0, head), prev = dummy;
    for (int i = 1; i < left; i++) prev = prev.next;
    ListNode curr = prev.next;
    for (int i = 0; i < right - left; i++) {
        ListNode next = curr.next;
        curr.next = next.next;
        next.next = prev.next;
        prev.next = next;
    }
    return dummy.next;
}

时间复杂度：O(n)，空间复杂度：O(1)

146. 🟡 子集 II（Subsets II）- LeetCode 90

题目：给定可能包含重复元素的整数数组，返回所有可能的子集（不含重复子集）。

分析：排序+回溯，同层跳过重复元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(res, new ArrayList<>(), nums, 0);
    return res;
}

private void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums, int start) {
    res.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue;
        path.add(nums[i]);
        backtrack(res, path, nums, i + 1);
        path.remove(path.size() - 1);
    }
}

时间复杂度：O(n·2^n)，空间复杂度：O(n)

147. 🟡 组合总和 II（Combination Sum II）- LeetCode 40

题目：给定有重复元素的数组和目标值，找出所有和为目标值的组合，每个数字只能用一次。

分析：排序+回溯+同层去重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(candidates);
    backtrack(res, new ArrayList<>(), candidates, target, 0);
    return res;
}

private void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums, int remain, int start) {
    if (remain == 0) { res.add(new ArrayList<>(path)); return; }
    for (int i = start; i < nums.length && nums[i] <= remain; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue;
        path.add(nums[i]);
        backtrack(res, path, nums, remain - nums[i], i + 1);
        path.remove(path.size() - 1);
    }
}

时间复杂度：O(2^n)，空间复杂度：O(n)

148. 🟡 全排列 II（Permutations II）- LeetCode 47

题目：给定可包含重复数字的序列，返回所有不重复的全排列。

分析：排序+回溯+剪枝。同层中相同的数字只选第一个（前一个相同数字未使用时跳过）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(res, new ArrayList<>(), nums, new boolean[nums.length]);
    return res;
}

private void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums, boolean[] used) {
    if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
    for (int i = 0; i < nums.length; i++) {
        if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
        used[i] = true; path.add(nums[i]);
        backtrack(res, path, nums, used);
        path.remove(path.size() - 1); used[i] = false;
    }
}

时间复杂度：O(n·n!)，空间复杂度：O(n)

149. 🟡 Pow(x, n)（快速幂）- LeetCode 50

题目：实现pow(x, n)。

分析：快速幂。n为偶数时x^n = (x²)^(n/2)，n为奇数时多乘一个x。注意n为负数和Integer.MIN_VALUE。

1
2
3
4
5
6
7
8
9
10
11
public double myPow(double x, int n) {
    long N = n;
    if (N < 0) { x = 1 / x; N = -N; }
    double result = 1;
    while (N > 0) {
        if ((N & 1) == 1) result *= x;
        x *= x;
        N >>= 1;
    }
    return result;
}

时间复杂度：O(log n)，空间复杂度：O(1)

150. 🟡 寻找峰值（Find Peak Element）- LeetCode 162

题目：数组中相邻元素不相等，找到一个峰值元素（大于左右邻居），要求O(log n)。

分析：二分查找。如果mid < mid+1，峰值在右半边；否则在左半边。

1
2
3
4
5
6
7
8
9
public int findPeakElement(int[] nums) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < nums[mid + 1]) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

时间复杂度：O(log n)，空间复杂度：O(1)

151. 🟡 两数相除（Divide Two Integers）- LeetCode 29

题目：不使用乘法、除法和取余运算符，实现两个整数的除法。

分析：用位运算模拟。每次将除数左移（翻倍），找到最大的倍数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int divide(int dividend, int divisor) {
    if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
    int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;
    long a = Math.abs((long) dividend), b = Math.abs((long) divisor);
    int result = 0;
    while (a >= b) {
        long temp = b;
        int multiple = 1;
        while (a >= (temp << 1)) { temp <<= 1; multiple <<= 1; }
        a -= temp;
        result += multiple;
    }
    return sign * result;
}

时间复杂度：O(log²n)，空间复杂度：O(1)

152. 🟡 排列序列（Permutation Sequence）- LeetCode 60

题目：给定n和k，返回第k个排列。

分析：数学法。利用阶乘确定每一位的数字，避免生成所有排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public String getPermutation(int n, int k) {
    int[] factorial = new int[n + 1];
    factorial[0] = 1;
    for (int i = 1; i <= n; i++) factorial[i] = factorial[i - 1] * i;
    List<Integer> nums = new ArrayList<>();
    for (int i = 1; i <= n; i++) nums.add(i);
    StringBuilder sb = new StringBuilder();
    k--;
    for (int i = n - 1; i >= 0; i--) {
        int idx = k / factorial[i];
        sb.append(nums.remove(idx));
        k %= factorial[i];
    }
    return sb.toString();
}

时间复杂度：O(n²)，空间复杂度：O(n)

153. 🟡 搜索旋转排序数组 II（Search in Rotated Sorted Array II）- LeetCode 81

题目：旋转排序数组中可能有重复元素，搜索目标值。

分析：与33题类似，但有重复时无法判断哪半边有序，需要缩小边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return true;
        if (nums[lo] == nums[mid]) { lo++; continue; } // 无法判断，缩小边界
        if (nums[lo] <= nums[mid]) {
            if (target >= nums[lo] && target < nums[mid]) hi = mid - 1; else lo = mid + 1;
        } else {
            if (target > nums[mid] && target <= nums[hi]) lo = mid + 1; else hi = mid - 1;
        }
    }
    return false;
}

时间复杂度：平均O(log n)，最坏O(n)，空间复杂度：O(1)

154. 🟡 寻找旋转排序数组中的最小值（Find Minimum in Rotated Sorted Array）- LeetCode 153

题目：在旋转排序数组中找到最小值。

分析：二分查找。比较mid和right，mid>right说明最小值在右半边。

1
2
3
4
5
6
7
8
9
public int findMin(int[] nums) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) lo = mid + 1;
        else hi = mid;
    }
    return nums[lo];
}

时间复杂度：O(log n)，空间复杂度：O(1)

155. 🟡 最大数（Largest Number）- LeetCode 179

题目：给定一组非负整数，重新排列使之组成最大的整数。

分析：自定义排序。比较a+b和b+a的字典序。

1
2
3
4
5
6
7
8
9
public String largestNumber(int[] nums) {
    String[] strs = new String[nums.length];
    for (int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]);
    Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));
    if (strs[0].equals("0")) return "0";
    StringBuilder sb = new StringBuilder();
    for (String s : strs) sb.append(s);
    return sb.toString();
}

时间复杂度：O(n·log n·k)，k为数字平均位数，空间复杂度：O(n)

156. 🟡 位1的个数（Number of 1 Bits）- LeetCode 191

题目：返回无符号整数的二进制中1的个数。

分析：n & (n-1)消除最低位的1，计数直到n为0。

1
2
3
4
5
public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) { n &= (n - 1); count++; }
    return count;
}

时间复杂度：O(k)，k为1的个数，空间复杂度：O(1)

157. 🟡 旋转数组（Rotate Array）- LeetCode 189

题目：将数组向右旋转k个位置。

分析：三次翻转。先整体翻转，再翻转前k个，再翻转后n-k个。

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

private void reverse(int[] nums, int l, int r) {
    while (l < r) { int t = nums[l]; nums[l++] = nums[r]; nums[r--] = t; }
}

时间复杂度：O(n)，空间复杂度：O(1)

158. 🟡 只出现一次的数字（Single Number）- LeetCode 136

题目：数组中除了一个元素只出现一次外，其余都出现两次，找出那个只出现一次的。

分析：异或。a^a=0，0^a=a，所有数异或的结果就是只出现一次的数。

1
2
3
4
5
public int singleNumber(int[] nums) {
    int result = 0;
    for (int n : nums) result ^= n;
    return result;
}

时间复杂度：O(n)，空间复杂度：O(1)

159. 🟡 只出现一次的数字 III（Single Number III）- LeetCode 260

题目：数组中恰好有两个元素只出现一次，其余都出现两次，找出这两个元素。

分析：全部异或得到两个数的异或值，找到任意一个为1的位，按该位分组分别异或。

1
2
3
4
5
6
7
8
9
10
public int[] singleNumber(int[] nums) {
    int xor = 0;
    for (int n : nums) xor ^= n;
    int bit = xor & (-xor); // 最低位的1
    int a = 0, b = 0;
    for (int n : nums) {
        if ((n & bit) == 0) a ^= n; else b ^= n;
    }
    return new int[]{a, b};
}

时间复杂度：O(n)，空间复杂度：O(1)

160. 🟡 二叉搜索树中第K小的元素（Kth Smallest Element in a BST）- LeetCode 230

题目：给定BST的根节点和整数k，返回第k小的元素。

分析：中序遍历BST得到升序序列，第k个就是答案。

1
2
3
4
5
6
7
8
9
10
11
public int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) { stack.push(curr); curr = curr.left; }
        curr = stack.pop();
        if (--k == 0) return curr.val;
        curr = curr.right;
    }
    return -1;
}

时间复杂度：O(H+k)，空间复杂度：O(H)

161. 🟡 二叉搜索树迭代器（BST Iterator）- LeetCode 173

题目：实现BST的迭代器，支持next()和hasNext()，均为O(1)均摊时间。

分析：用栈模拟中序遍历，先将所有左节点入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class BSTIterator {
    private Deque<TreeNode> stack = new ArrayDeque<>();

    public BSTIterator(TreeNode root) { pushLeft(root); }

    public int next() {
        TreeNode node = stack.pop();
        pushLeft(node.right);
        return node.val;
    }

    public boolean hasNext() { return !stack.isEmpty(); }

    private void pushLeft(TreeNode node) { while (node != null) { stack.push(node); node = node.left; } }
}

时间复杂度：next()均摊O(1)，空间复杂度：O(h)

162. 🟡 最小基因变化（Minimum Genetic Mutation）- LeetCode 433

题目：基因序列由ACGT组成，每次变化一个字符，求从start到end的最少变化次数。

分析：BFS，与单词接龙类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int minMutation(String startGene, String endGene, String[] bank) {
    Set<String> dict = new HashSet<>(Arrays.asList(bank));
    if (!dict.contains(endGene)) return -1;
    Queue<String> queue = new LinkedList<>();
    queue.offer(startGene);
    char[] genes = {'A', 'C', 'G', 'T'};
    int steps = 0;
    while (!queue.isEmpty()) {
        int size = queue.size(); steps++;
        for (int i = 0; i < size; i++) {
            char[] curr = queue.poll().toCharArray();
            for (int j = 0; j < 8; j++) {
                char orig = curr[j];
                for (char g : genes) {
                    if (g == orig) continue;
                    curr[j] = g;
                    String next = new String(curr);
                    if (next.equals(endGene)) return steps;
                    if (dict.remove(next)) queue.offer(next);
                }
                curr[j] = orig;
            }
        }
    }
    return -1;
}

时间复杂度：O(n·8·4)，空间复杂度：O(n)

163. 🟡 打家劫舍 II（House Robber II）- LeetCode 213

题目：房屋排成环形，不能偷相邻的，求最大金额。

分析：环形问题拆成两个线性问题：偷[0,n-2]和偷[1,n-1]，取较大值。

1
2
3
4
5
6
7
8
9
10
public int rob(int[] nums) {
    if (nums.length == 1) return nums[0];
    return Math.max(robRange(nums, 0, nums.length - 2), robRange(nums, 1, nums.length - 1));
}

private int robRange(int[] nums, int start, int end) {
    int prev = 0, curr = 0;
    for (int i = start; i <= end; i++) { int tmp = curr; curr = Math.max(curr, prev + nums[i]); prev = tmp; }
    return curr;
}

时间复杂度：O(n)，空间复杂度：O(1)

164. 🟡 丑数 II（Ugly Number II）- LeetCode 264

题目：找出第n个丑数（只包含质因子2、3、5的正整数）。

分析：三指针法。维护三个指针分别乘以2、3、5，每次取最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int nthUglyNumber(int n) {
    int[] dp = new int[n];
    dp[0] = 1;
    int p2 = 0, p3 = 0, p5 = 0;
    for (int i = 1; i < n; i++) {
        int v2 = dp[p2] * 2, v3 = dp[p3] * 3, v5 = dp[p5] * 5;
        dp[i] = Math.min(v2, Math.min(v3, v5));
        if (dp[i] == v2) p2++;
        if (dp[i] == v3) p3++;
        if (dp[i] == v5) p5++;
    }
    return dp[n - 1];
}

时间复杂度：O(n)，空间复杂度：O(n)

165. 🟡 两个整数相加（Sum of Two Integers）- LeetCode 371

题目：不使用+和-运算符，计算两个整数之和。

分析：位运算。异或得到不进位的和，与运算左移一位得到进位，循环直到进位为0。

1
2
3
4
5
6
7
8
public int getSum(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

时间复杂度：O(1)，空间复杂度：O(1)

166. 🟡 重排链表（Reorder List）- LeetCode 143

题目：将链表L0→L1→…→Ln重排为L0→Ln→L1→Ln-1→…

分析：三步：1.快慢指针找中点 2.反转后半部分 3.交替合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void reorderList(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode second = reverse(slow.next);
    slow.next = null;
    ListNode first = head;
    while (second != null) {
        ListNode tmp1 = first.next, tmp2 = second.next;
        first.next = second; second.next = tmp1;
        first = tmp1; second = tmp2;
    }
}

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

时间复杂度：O(n)，空间复杂度：O(1)

167. 🟡 奇偶链表（Odd Even Linked List）- LeetCode 328

题目：将链表中奇数位置节点排在前面，偶数位置节点排在后面。

分析：双指针分别串联奇数位和偶数位节点，最后连接。

1
2
3
4
5
6
7
8
9
10
public ListNode oddEvenList(ListNode head) {
    if (head == null) return null;
    ListNode odd = head, even = head.next, evenHead = even;
    while (even != null && even.next != null) {
        odd.next = even.next; odd = odd.next;
        even.next = odd.next; even = even.next;
    }
    odd.next = evenHead;
    return head;
}

时间复杂度：O(n)，空间复杂度：O(1)

168. 🟡 加油站（Gas Station）- LeetCode 134

题目：环形路线上有n个加油站，判断能否绕一圈，返回起始加油站编号。

分析：贪心。如果总油量≥总消耗，一定有解。从净油量累计最低点的下一个站出发。

1
2
3
4
5
6
7
8
9
10
public int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, curr = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        total += diff;
        curr += diff;
        if (curr < 0) { start = i + 1; curr = 0; }
    }
    return total >= 0 ? start : -1;
}

时间复杂度：O(n)，空间复杂度：O(1)

169. 🟡 分发糖果（Candy）- LeetCode 135

题目：n个孩子站成一排，每个孩子有评分，分发糖果使得评分高的孩子比相邻的孩子获得更多糖果，求最少糖果数。

分析：两次遍历。从左到右保证右边比左边高的多一个，从右到左保证左边比右边高的多一个。

1
2
3
4
5
6
7
8
9
10
11
12
public int candy(int[] ratings) {
    int n = ratings.length;
    int[] candies = new int[n];
    Arrays.fill(candies, 1);
    for (int i = 1; i < n; i++)
        if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
    for (int i = n - 2; i >= 0; i--)
        if (ratings[i] > ratings[i + 1]) candies[i] = Math.max(candies[i], candies[i + 1] + 1);
    int sum = 0;
    for (int c : candies) sum += c;
    return sum;
}

时间复杂度：O(n)，空间复杂度：O(n)

170. 🟡 基本计算器 II（Basic Calculator II）- LeetCode 227

题目：实现一个基本的计算器，支持+、-、*、/和空格。

分析：用栈处理。遇到*和/立即计算，+和-将数字入栈（-号取负），最后栈中所有数求和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int calculate(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    int num = 0;
    char op = '+';
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isDigit(c)) num = num * 10 + (c - '0');
        if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
            if (op == '+') stack.push(num);
            else if (op == '-') stack.push(-num);
            else if (op == '*') stack.push(stack.pop() * num);
            else if (op == '/') stack.push(stack.pop() / num);
            op = c; num = 0;
        }
    }
    int result = 0;
    for (int n : stack) result += n;
    return result;
}

时间复杂度：O(n)，空间复杂度：O(n)

171. 🟡 最长连续递增序列（Longest Continuous Increasing Subsequence）- LeetCode 674

题目：给定未排序的整数数组，找出最长连续递增子序列的长度。

分析：一次遍历，维护当前连续递增长度。

1
2
3
4
5
6
7
8
public int findLengthOfLCIS(int[] nums) {
    int max = 1, curr = 1;
    for (int i = 1; i < nums.length; i++) {
        curr = nums[i] > nums[i - 1] ? curr + 1 : 1;
        max = Math.max(max, curr);
    }
    return max;
}

时间复杂度：O(n)，空间复杂度：O(1)

172. 🟡 有效的字母异位词（Valid Anagram）- LeetCode 242

题目：判断两个字符串是否是字母异位词。

分析：字符计数数组比较。

1
2
3
4
5
6
7
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) { count[s.charAt(i) - 'a']++; count[t.charAt(i) - 'a']--; }
    for (int c : count) if (c != 0) return false;
    return true;
}

时间复杂度：O(n)，空间复杂度：O(1)

173. 🟡 最小绝对差（Minimum Absolute Difference in BST）- LeetCode 530

题目：给定BST，找出任意两个节点值之间的最小绝对差。

分析：中序遍历BST得到有序序列，最小差一定在相邻元素之间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private int minDiff = Integer.MAX_VALUE;
private TreeNode prev = null;

public int getMinimumDifference(TreeNode root) {
    inorder(root);
    return minDiff;
}

private void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    if (prev != null) minDiff = Math.min(minDiff, node.val - prev.val);
    prev = node;
    inorder(node.right);
}

时间复杂度：O(n)，空间复杂度：O(h)

174. 🟡 两数之和 II - 输入有序数组（Two Sum II）- LeetCode 167

题目：在有序数组中找到两个数使得它们的和等于目标值。

分析：双指针从两端向中间收缩。

1
2
3
4
5
6
7
8
9
10
public int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) return new int[]{left + 1, right + 1};
        else if (sum < target) left++;
        else right--;
    }
    return new int[0];
}

时间复杂度：O(n)，空间复杂度：O(1)

175. 🟡 最长字符串链（Longest String Chain）- LeetCode 1048

题目：给定单词列表，找出最长的字符串链（每次添加一个字母形成新单词）。

分析：按长度排序，DP。对每个单词尝试删除每个字符，看前驱是否存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int longestStrChain(String[] words) {
    Arrays.sort(words, (a, b) -> a.length() - b.length());
    Map<String, Integer> dp = new HashMap<>();
    int max = 1;
    for (String word : words) {
        int best = 1;
        for (int i = 0; i < word.length(); i++) {
            String prev = word.substring(0, i) + word.substring(i + 1);
            best = Math.max(best, dp.getOrDefault(prev, 0) + 1);
        }
        dp.put(word, best);
        max = Math.max(max, best);
    }
    return max;
}

时间复杂度：O(n·m²)，m为单词最大长度，空间复杂度：O(n·m)

176. 🟡 岛屿的最大面积（Max Area of Island）- LeetCode 695

题目：给定二维网格，找出最大岛屿的面积。

分析：DFS，每次访问一个’1’就计数并标记为已访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxAreaOfIsland(int[][] grid) {
    int max = 0;
    for (int i = 0; i < grid.length; i++)
        for (int j = 0; j < grid[0].length; j++)
            if (grid[i][j] == 1) max = Math.max(max, dfs(grid, i, j));
    return max;
}

private int dfs(int[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) return 0;
    grid[i][j] = 0;
    return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
}

时间复杂度：O(m·n)，空间复杂度：O(m·n)

177. 🟡 字符串相乘（Multiply Strings）- LeetCode 43

题目：给定两个以字符串形式表示的非负整数，返回它们的乘积。

分析：模拟竖式乘法。num1[i] * num2[j]的结果放在result[i+j]和result[i+j+1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public String multiply(String num1, String num2) {
    int m = num1.length(), n = num2.length();
    int[] result = new int[m + n];
    for (int i = m - 1; i >= 0; i--)
        for (int j = n - 1; j >= 0; j--) {
            int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
            int p1 = i + j, p2 = i + j + 1;
            int sum = mul + result[p2];
            result[p2] = sum % 10;
            result[p1] += sum / 10;
        }
    StringBuilder sb = new StringBuilder();
    for (int r : result) if (!(sb.length() == 0 && r == 0)) sb.append(r);
    return sb.length() == 0 ? "0" : sb.toString();
}

时间复杂度：O(m·n)，空间复杂度：O(m+n)

178. 🟡 LFU缓存（LFU Cache）- LeetCode 460

题目：设计LFU缓存，支持get和put操作，均为O(1)。

分析：HashMap + 频率到双向链表的映射。维护最小频率。

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
class LFUCache {
    private Map<Integer, int[]> cache = new HashMap<>(); // key -> [val, freq]
    private Map<Integer, LinkedHashSet<Integer>> freqMap = new HashMap<>();
    private int capacity, minFreq;

    public LFUCache(int capacity) { this.capacity = capacity; }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        int[] info = cache.get(key);
        updateFreq(key, info[1]);
        info[1]++;
        return info[0];
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        if (cache.containsKey(key)) {
            int[] info = cache.get(key);
            info[0] = value;
            updateFreq(key, info[1]);
            info[1]++;
            return;
        }
        if (cache.size() == capacity) {
            int evict = freqMap.get(minFreq).iterator().next();
            freqMap.get(minFreq).remove(evict);
            cache.remove(evict);
        }
        cache.put(key, new int[]{value, 1});
        freqMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }

    private void updateFreq(int key, int freq) {
        freqMap.get(freq).remove(key);
        if (freqMap.get(freq).isEmpty()) { freqMap.remove(freq); if (minFreq == freq) minFreq++; }
        freqMap.computeIfAbsent(freq + 1, k -> new LinkedHashSet<>()).add(key);
    }
}

时间复杂度：get/put均O(1)，空间复杂度：O(capacity)

179. 🟡 设计哈希映射（Design HashMap）- LeetCode 706

题目：不使用内置哈希表库，设计HashMap。

分析：拉链法。数组+链表，哈希函数取模。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class MyHashMap {
    private static final int SIZE = 1009;
    private List<int[]>[] buckets;

    public MyHashMap() {
        buckets = new List[SIZE];
        for (int i = 0; i < SIZE; i++) buckets[i] = new ArrayList<>();
    }

    public void put(int key, int value) {
        int idx = key % SIZE;
        for (int[] pair : buckets[idx]) { if (pair[0] == key) { pair[1] = value; return; } }
        buckets[idx].add(new int[]{key, value});
    }

    public int get(int key) {
        for (int[] pair : buckets[key % SIZE]) if (pair[0] == key) return pair[1];
        return -1;
    }

    public void remove(int key) { buckets[key % SIZE].removeIf(p -> p[0] == key); }
}

时间复杂度：均摊O(1)，空间复杂度：O(n)

180. 🟡 最长有效括号变体 - 删除无效的括号（Remove Invalid Parentheses）- LeetCode 301

题目：删除最少数量的无效括号，使字符串有效，返回所有可能的结果。

分析：BFS逐层删除。每层删除一个括号，找到有效的就停止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public List<String> removeInvalidParentheses(String s) {
    List<String> res = new ArrayList<>();
    Queue<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    queue.offer(s); visited.add(s);
    boolean found = false;
    while (!queue.isEmpty()) {
        String curr = queue.poll();
        if (isValid(curr)) { res.add(curr); found = true; }
        if (found) continue;
        for (int i = 0; i < curr.length(); i++) {
            if (curr.charAt(i) != '(' && curr.charAt(i) != ')') continue;
            String next = curr.substring(0, i) + curr.substring(i + 1);
            if (visited.add(next)) queue.offer(next);
        }
    }
    return res;
}

private boolean isValid(String s) {
    int count = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') count++;
        else if (c == ')') { if (--count < 0) return false; }
    }
    return count == 0;
}

时间复杂度：O(2^n)，空间复杂度：O(2^n)

181. 🟡 最大二叉树（Maximum Binary Tree）- LeetCode 654

题目：给定不含重复元素的整数数组，构建最大二叉树（根是最大值，左右子树递归构建）。

分析：递归。找到最大值作为根，左边递归构建左子树，右边递归构建右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
public TreeNode constructMaximumBinaryTree(int[] nums) {
    return build(nums, 0, nums.length - 1);
}

private TreeNode build(int[] nums, int lo, int hi) {
    if (lo > hi) return null;
    int maxIdx = lo;
    for (int i = lo + 1; i <= hi; i++) if (nums[i] > nums[maxIdx]) maxIdx = i;
    TreeNode root = new TreeNode(nums[maxIdx]);
    root.left = build(nums, lo, maxIdx - 1);
    root.right = build(nums, maxIdx + 1, hi);
    return root;
}

时间复杂度：平均O(n·log n)，最坏O(n²)，空间复杂度：O(n)

182. 🟡 有效的完全平方数（Valid Perfect Square）- LeetCode 367

题目：不使用内置函数，判断一个正整数是否是完全平方数。

分析：二分查找。

1
2
3
4
5
6
7
8
9
10
11
public boolean isPerfectSquare(int num) {
    long lo = 1, hi = num;
    while (lo <= hi) {
        long mid = lo + (hi - lo) / 2;
        long sq = mid * mid;
        if (sq == num) return true;
        else if (sq < num) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

时间复杂度：O(log n)，空间复杂度：O(1)

183. 🟡 x的平方根（Sqrt(x)）- LeetCode 69

题目：计算并返回x的算术平方根（整数部分）。

分析：二分查找。找最大的mid使得mid*mid <= x。

1
2
3
4
5
6
7
8
9
public int mySqrt(int x) {
    long lo = 0, hi = x;
    while (lo <= hi) {
        long mid = lo + (hi - lo) / 2;
        if (mid * mid <= x) lo = mid + 1;
        else hi = mid - 1;
    }
    return (int) hi;
}

时间复杂度：O(log n)，空间复杂度：O(1)

184. 🟡 最长公共前缀（Longest Common Prefix）- LeetCode 14

题目：找出字符串数组中的最长公共前缀。

分析：纵向扫描。逐字符比较所有字符串的同一位置。

1
2
3
4
5
6
7
8
public String longestCommonPrefix(String[] strs) {
    for (int i = 0; i < strs[0].length(); i++) {
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; j++)
            if (i >= strs[j].length() || strs[j].charAt(i) != c) return strs[0].substring(0, i);
    }
    return strs[0];
}

时间复杂度：O(S)，S为所有字符总数，空间复杂度：O(1)

185. 🟡 回文数（Palindrome Number）- LeetCode 9

题目：判断一个整数是否是回文数，不将整数转为字符串。

分析：反转后半部分数字与前半部分比较。

1
2
3
4
5
6
public boolean isPalindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;
    int rev = 0;
    while (x > rev) { rev = rev * 10 + x % 10; x /= 10; }
    return x == rev || x == rev / 10;
}

时间复杂度：O(log n)，空间复杂度：O(1)

186. 🟡 反转整数（Reverse Integer）- LeetCode 7

题目：给定32位有符号整数，反转其数字。溢出返回0。

分析：逐位取出，检查溢出。

1
2
3
4
5
6
7
8
9
10
public int reverse(int x) {
    int rev = 0;
    while (x != 0) {
        int digit = x % 10;
        if (rev > Integer.MAX_VALUE / 10 || rev < Integer.MIN_VALUE / 10) return 0;
        rev = rev * 10 + digit;
        x /= 10;
    }
    return rev;
}

时间复杂度：O(log n)，空间复杂度：O(1)

187. 🟡 二进制求和（Add Binary）- LeetCode 67

题目：给定两个二进制字符串，返回它们的和（也是二进制字符串）。

分析：从末尾开始逐位相加，处理进位。

1
2
3
4
5
6
7
8
9
10
11
12
public String addBinary(String a, String b) {
    StringBuilder sb = new StringBuilder();
    int i = a.length() - 1, j = b.length() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry > 0) {
        int sum = carry;
        if (i >= 0) sum += a.charAt(i--) - '0';
        if (j >= 0) sum += b.charAt(j--) - '0';
        sb.append(sum % 2);
        carry = sum / 2;
    }
    return sb.reverse().toString();
}

时间复杂度：O(max(m,n))，空间复杂度：O(max(m,n))

188. 🟡 删除排序数组中的重复项（Remove Duplicates）- LeetCode 26

题目：原地删除排序数组中的重复项，返回新长度。

分析：双指针。慢指针记录不重复元素的位置。

1
2
3
4
5
6
public int removeDuplicates(int[] nums) {
    int j = 0;
    for (int i = 1; i < nums.length; i++)
        if (nums[i] != nums[j]) nums[++j] = nums[i];
    return j + 1;
}

时间复杂度：O(n)，空间复杂度：O(1)

189. 🟡 移除元素（Remove Element）- LeetCode 27

题目：原地移除数组中所有等于val的元素，返回新长度。

分析：双指针。

1
2
3
4
5
public int removeElement(int[] nums, int val) {
    int j = 0;
    for (int n : nums) if (n != val) nums[j++] = n;
    return j;
}

时间复杂度：O(n)，空间复杂度：O(1)

190. 🟡 实现strStr()（Find the Index of the First Occurrence）- LeetCode 28

题目：在haystack中找到needle第一次出现的位置。

分析：KMP算法或直接滑动窗口。面试中直接法即可。

1
2
3
4
5
6
7
8
9
public int strStr(String haystack, String needle) {
    int m = haystack.length(), n = needle.length();
    for (int i = 0; i <= m - n; i++) {
        int j = 0;
        while (j < n && haystack.charAt(i + j) == needle.charAt(j)) j++;
        if (j == n) return i;
    }
    return -1;
}

时间复杂度：O(m·n)，空间复杂度：O(1)

191. 🟡 缺失的第一个正数（First Missing Positive）- LeetCode 41

题目：给定未排序的整数数组，找出其中没有出现的最小正整数，要求O(n)时间O(1)空间。

分析：原地哈希。将每个数放到它应该在的位置（nums[i]放到nums[nums[i]-1]）。

1
2
3
4
5
6
7
8
9
public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++)
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            int tmp = nums[nums[i] - 1]; nums[nums[i] - 1] = nums[i]; nums[i] = tmp;
        }
    for (int i = 0; i < n; i++) if (nums[i] != i + 1) return i + 1;
    return n + 1;
}

时间复杂度：O(n)，空间复杂度：O(1)

192. 🟡 外观数列（Count and Say）- LeetCode 38

题目：给定正整数n，输出外观数列的第n项。

分析：迭代模拟。对上一项进行”读”操作生成下一项。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public String countAndSay(int n) {
    String s = "1";
    for (int i = 1; i < n; i++) {
        StringBuilder sb = new StringBuilder();
        int count = 1;
        for (int j = 1; j < s.length(); j++) {
            if (s.charAt(j) == s.charAt(j - 1)) count++;
            else { sb.append(count).append(s.charAt(j - 1)); count = 1; }
        }
        sb.append(count).append(s.charAt(s.length() - 1));
        s = sb.toString();
    }
    return s;
}

时间复杂度：O(n·m)，m为字符串长度，空间复杂度：O(m)

193. 🟡 解码方法（Decode Ways）- LeetCode 91

题目：给定数字字符串，计算有多少种解码方式（A=1, B=2, …, Z=26）。

分析：动态规划。dp[i]表示前i个字符的解码方式数。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int numDecodings(String s) {
    if (s.charAt(0) == '0') return 0;
    int n = s.length();
    int prev2 = 1, prev1 = 1;
    for (int i = 1; i < n; i++) {
        int curr = 0;
        if (s.charAt(i) != '0') curr = prev1;
        int two = Integer.parseInt(s.substring(i - 1, i + 1));
        if (two >= 10 && two <= 26) curr += prev2;
        prev2 = prev1; prev1 = curr;
    }
    return prev1;
}

时间复杂度：O(n)，空间复杂度：O(1)

194. 🟡 交错字符串（Interleaving String）- LeetCode 97

题目：判断s3是否由s1和s2交错组成。

分析：二维DP。dp[i][j]表示s1前i个和s2前j个能否交错组成s3前i+j个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean isInterleave(String s1, String s2, String s3) {
    int m = s1.length(), n = s2.length();
    if (m + n != s3.length()) return false;
    boolean[] dp = new boolean[n + 1];
    for (int i = 0; i <= m; i++)
        for (int j = 0; j <= n; j++) {
            if (i == 0 && j == 0) dp[j] = true;
            else if (i == 0) dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
            else if (j == 0) dp[j] = dp[j] && s1.charAt(i - 1) == s3.charAt(i - 1);
            else dp[j] = (dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                      || (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
        }
    return dp[n];
}

时间复杂度：O(m·n)，空间复杂度：O(n)

195. 🟡 不同路径 II（Unique Paths II）- LeetCode 63

题目：网格中有障碍物，从左上角到右下角有多少条不同路径。

分析：动态规划。障碍物位置dp值为0。

1
2
3
4
5
6
7
8
9
10
11
public int uniquePathsWithObstacles(int[][] grid) {
    int n = grid[0].length;
    int[] dp = new int[n];
    dp[0] = 1;
    for (int[] row : grid)
        for (int j = 0; j < n; j++) {
            if (row[j] == 1) dp[j] = 0;
            else if (j > 0) dp[j] += dp[j - 1];
        }
    return dp[n - 1];
}

时间复杂度：O(m·n)，空间复杂度：O(n)

196. 🟡 加一（Plus One）- LeetCode 66

题目：给定一个由整数组成的非空数组表示的非负整数，加一。

分析：从末尾开始加一，处理进位。

1
2
3
4
5
6
7
8
9
public int[] plusOne(int[] digits) {
    for (int i = digits.length - 1; i >= 0; i--) {
        if (digits[i] < 9) { digits[i]++; return digits; }
        digits[i] = 0;
    }
    int[] result = new int[digits.length + 1];
    result[0] = 1;
    return result;
}

时间复杂度：O(n)，空间复杂度：O(1)

197. 🟡 杨辉三角（Pascal’s Triangle）- LeetCode 118

题目：给定行数，生成杨辉三角。

分析：每行第一个和最后一个是1，中间的数等于上一行相邻两数之和。

1
2
3
4
5
6
7
8
9
10
public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < numRows; i++) {
        List<Integer> row = new ArrayList<>();
        for (int j = 0; j <= i; j++)
            row.add(j == 0 || j == i ? 1 : res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
        res.add(row);
    }
    return res;
}

时间复杂度：O(n²)，空间复杂度：O(n²)

198. 🟡 二叉树的前序遍历（Binary Tree Preorder Traversal）- LeetCode 144

题目：给定二叉树，返回前序遍历结果（迭代实现）。

分析：用栈模拟。先压右子节点再压左子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return res;
}

时间复杂度：O(n)，空间复杂度：O(n)

199. 🟡 有效的括号字符串（Valid Parenthesis String）- LeetCode 678

题目：给定只包含’(‘、’)’和’‘的字符串，’‘可以是’(‘、’)’或空，判断是否有效。

分析：贪心。维护未匹配左括号数量的最小值和最大值范围。

1
2
3
4
5
6
7
8
9
10
11
public boolean checkValidString(String s) {
    int lo = 0, hi = 0; // 未匹配左括号的最小和最大可能数量
    for (char c : s.toCharArray()) {
        if (c == '(') { lo++; hi++; }
        else if (c == ')') { lo--; hi--; }
        else { lo--; hi++; } // '*'可以是(、)或空
        if (hi < 0) return false; // 右括号太多
        lo = Math.max(lo, 0); // 最小值不能为负
    }
    return lo == 0;
}

时间复杂度：O(n)，空间复杂度：O(1)

200. 🟡 图的深拷贝变体 - 太平洋大西洋水流问题（Pacific Atlantic Water Flow）- LeetCode 417

题目：m×n矩阵表示海拔，水可以向四个方向流向相同或更低的格子。左上边界是太平洋，右下边界是大西洋。找出能同时流向两个大洋的格子。

分析：反向思维。从两个大洋的边界出发DFS/BFS，标记能到达的格子，取交集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<List<Integer>> pacificAtlantic(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    boolean[][] pacific = new boolean[m][n], atlantic = new boolean[m][n];
    for (int i = 0; i < m; i++) { dfs(heights, pacific, i, 0); dfs(heights, atlantic, i, n - 1); }
    for (int j = 0; j < n; j++) { dfs(heights, pacific, 0, j); dfs(heights, atlantic, m - 1, j); }
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (pacific[i][j] && atlantic[i][j]) res.add(Arrays.asList(i, j));
    return res;
}

private void dfs(int[][] heights, boolean[][] visited, int i, int j) {
    visited[i][j] = true;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    for (int[] d : dirs) {
        int ni = i + d[0], nj = j + d[1];
        if (ni >= 0 && ni < heights.length && nj >= 0 && nj < heights[0].length
            && !visited[ni][nj] && heights[ni][nj] >= heights[i][j])
            dfs(heights, visited, ni, nj);
    }
}

时间复杂度：O(m·n)，空间复杂度：O(m·n)