LeetCode Hot 100

引言

LeetCode Hot 100 是 LeetCode 上最热门的 100 道题目，涵盖了算法和数据结构的核心知识点。这份清单作为刷题的参考和进度跟踪。

题目按 Hot 100 的原始顺序排列，每道题标注了难度等级（E=Easy, M=Medium, H=Hard）和主要技术点，方便快速定位和复习。

统计

• 总数: 100 题
• 难度分布:
  • Easy: 约 20 题
  • Medium: 约 60 题
  • Hard: 约 20 题
• 主要技术点: 数组、链表、树、动态规划、回溯、双指针、滑动窗口、栈、队列、图等

题目列表

详细题解

160. 相交链表

LT.160. Intersection of Two Linked Lists

这道题的核心思想是使用两个指针分别遍历两个链表，当其中一个指针到达链表末尾时，将其指向另一个链表的头部，继续遍历。这样做的目的是消除两个链表长度不同的影响，让两个指针同时到达相交节点。

关键洞察：如果两个链表相交，设链表 A 的不相交部分长度为 a，链表 B 的不相交部分长度为 b，公共部分长度为 c。当指针 pa 遍历完 A 再遍历 B，指针 pb 遍历完 B 再遍历 A 时，两个指针会同时到达相交点，因为它们都走了 a + b + c 的长度。

边界情况：

• 如果两个链表不相交，两个指针最终都会变成 null，循环结束返回 null
• 如果其中一个链表为空，直接返回 null

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pa = headA;
        ListNode pb = headB;
        while (pa != pb) {
            pa = pa != null ? pa.next : headB;
            pb = pb != null ? pb.next : headA;
        }
        return pa;
    }
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

// time: O(m + n), m 和 n 分别是两个链表的长度
// space: O(1)

为什么能保证找到交点或同时到达 null：

• 如果相交：pa 走 a + c + b，pb 走 b + c + a，两者在交点相遇
• 如果不相交：pa 走 m + n，pb 走 n + m，两者同时到达 null

这是空间复杂度 O(1) 的最优解，相比使用哈希表存储已访问节点的 O(m + n) 空间解法更加优雅。

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

LT.236. Lowest Common Ancestor of a Binary Tree

这道题的核心思想是使用递归自底向上查找，通过 DFS 后序遍历的方式，让每个节点向上返回它是否包含目标节点 p 或 q。

思考过程：

1. 边界情况：如果当前节点为 null，或者当前节点就是 p 或 q，直接返回当前节点
2. 递归查找：分别在左子树和右子树中查找 p 和 q
3. 判断结果：
   • 如果左右子树都找到了节点（left != null && right != null），说明当前节点就是 LCA（p 和 q 分别在左右子树）
   • 如果只有一边找到了，说明 p 和 q 都在那一边的子树中，返回那边找到的结果
   • 如果两边都没找到，返回 null

关键洞察：LCA 一定是第一个能让左右子树都返回非 null 的节点。如果只有一边返回非 null，说明 LCA 在那边的子树中；如果两边都返回非 null，当前节点就是 LCA。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) {
            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;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

// time: O(n), n 是树中节点的个数
// space: O(h), h 是树的高度，递归栈的深度

234. 回文链表

LT.234. Palindrome Linked List

这道题的核心思想是使用快慢指针找到链表中点，然后反转后半部分，再比较前半部分和反转后的后半部分。

思考过程：

1. 使用快慢指针找到中点：fast 每次走两步，slow 每次走一步
2. 反转后半部分链表：从 slow.next 开始反转
3. 比较两部分：前半部分和反转后的后半部分逐一比较

关键点：快慢指针在不同长度下的位置：

• 偶数长度（如 1->2->2->1，4 个节点）：

  • fast 停在倒数第二个节点（第二个 2）
  • slow 停在第二个节点（第一个 2），即前半部分的最后一个节点
  • slow.next 是后半部分的起始节点（第二个 2）

• 奇数长度（如 1->2->3->2->1，5 个节点）：

  • fast 停在最后一个节点（最后一个 1）
  • slow 停在中间节点（3），即前半部分的最后一个节点
  • slow.next 是后半部分的起始节点（第二个 2）
  • 中间节点不参与比较，这正是我们想要的

为什么 fast.next != null && fast.next.next != null：

• 这样保证 fast 能走两步时才继续
• 偶数长度时，fast 停在倒数第二个节点（fast.next != null 但 fast.next.next == null）
• 奇数长度时，fast 停在最后一个节点（fast.next == null）

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        // 使用快慢指针找到中点
        // slow 会停在前半部分的最后一个节点
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next; // fast 走两步
            slow = slow.next;      // slow 走一步
        }
        // slow.next 是后半部分的起始节点
        ListNode p1 = head;
        ListNode p2 = reverse(slow.next); // 反转后半部分
        
        // 比较前半部分和反转后的后半部分
        while (p2 != null) {
            if (p1.val != p2.val) return false;
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }

    // 反转链表
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next; // 保存下一个节点
            head.next = prev;          // 反转当前节点
            prev = head;               // prev 前移
            head = next;               // head 前移
        }
        return prev;
    }
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

// time: O(n), n 是链表长度
// space: O(1), 只使用了常数额外空间

739. 每日温度

LT.739. Daily Temperatures

这道题的核心思想是使用单调栈（单调递减栈）来找到每个温度右侧第一个比它高的温度。

思考过程：

1. 使用单调递减栈：栈中存储索引，从栈底到栈顶对应的温度递减
2. 遍历温度数组：对于每个温度，如果它比栈顶索引对应的温度高，说明找到了栈顶元素右侧第一个更高的温度
3. 更新答案：计算索引差 i - j，即需要等待的天数
4. 维护单调性：弹出所有比当前温度低的栈顶元素，然后压入当前索引

关键洞察：

• 栈中存储的是"等待答案"的索引
• 当遇到更高的温度时，可以为栈中所有比当前温度低的元素提供答案
• 因为栈是单调递减的，所以弹出的顺序是合理的（从栈顶开始）

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        // 单调递减栈，存储索引（从栈底到栈顶对应的温度递减）
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            // 当栈不为空且当前温度高于栈顶索引对应的温度时
            // 说明找到了栈顶元素右侧第一个更高的温度
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int j = stack.pop();
                ans[j] = i - j; // 计算等待天数
            }
            // 将当前索引压入栈（等待后续更高的温度）
            stack.push(i);
        }
        // 栈中剩余元素的 ans 保持为 0（没有更高的温度）
        return ans;
    }
}

// time: O(n), 每个元素最多进出栈一次
// space: O(n), 栈的空间最多为 n

226. 翻转二叉树

LT.226. Invert Binary Tree

这道题的核心思想是使用递归自底向上翻转每个节点的左右子树。

思考过程：

1. 边界情况：如果当前节点为 null，直接返回 null
2. 递归翻转：先递归翻转左子树和右子树，得到翻转后的子树
3. 交换左右子树：将翻转后的左子树赋给右子树，翻转后的右子树赋给左子树
4. 返回当前节点：返回翻转后的根节点

关键洞察：翻转二叉树就是翻转每个节点的左右子树。递归地先翻转子树，再交换当前节点的左右子树，自然就能翻转整棵树。

变量命名改进：使用 invertedLeft 和 invertedRight 能更清晰地表达这些是翻转后的子树，避免与 root.left、root.right 混淆。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        // 递归翻转左右子树
        TreeNode invertedLeft = invertTree(root.left);
        TreeNode invertedRight = invertTree(root.right);
        // 交换左右子树
        root.left = invertedRight;
        root.right = invertedLeft;
        return root;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

// time: O(n), n 是树中节点的个数
// space: O(h), h 是树的高度，递归栈的深度

221. 最大正方形

LT.221. Maximal Square

这道题的核心思想是使用动态规划（二维 DP）来找到矩阵中最大的由 '1' 组成的正方形。

思考过程：

1. 定义状态：dp[i][j] 表示以 matrix[i-1][j-1] 为右下角的最大正方形的边长
2. 使用 (i+1, j+1) 索引：为了避免边界判断，dp 数组使用 (m+1) x (n+1) 大小
3. 状态转移：如果当前位置是 '1'，取上方、左方、左上方三个方向的最小值再加 1
4. 更新最大值：遍历过程中记录最大边长
5. 返回面积：返回 maxSide * maxSide

关键洞察 - 为什么用 min：

• 要形成一个 k x k 的正方形，需要上方、左方、左上方三个方向都能形成至少 (k-1) x (k-1) 的正方形
• 取三者最小值，相当于取三个方向中能扩展的最小"半径"
• 类似于木桶效应：最短的板决定了桶的容量

技术要点：

• 二维 DP：使用二维数组存储子问题结果
• 最优子结构：以某个位置为右下角的正方形大小依赖于其上方、左方、左上方的结果
• 边界处理：使用 (m+1) x (n+1) 的 dp 数组，让索引从 1 开始，避免边界判断

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) return 0;
        int n = matrix[0].length;
        // dp[i][j] 表示以 matrix[i-1][j-1] 为右下角的最大正方形的边长
        // 使用 (m+1) x (n+1) 大小，让索引从 1 开始，避免边界判断
        int[][] dp = new int[m + 1][n + 1];
        int maxSide = 0; // 记录最大边长

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    // 取上方、左方、左上方三个方向的最小值
                    // 因为要形成 k x k 正方形，三个方向都必须至少能形成 (k-1) x (k-1) 正方形
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                    maxSide = Math.max(dp[i][j], maxSide); // 更新最大边长
                }
                // 如果 matrix[i-1][j-1] == '0'，dp[i][j] 保持为 0
            }
        }

        return maxSide * maxSide; // 返回面积
    }
}

// time: O(m * n), m 和 n 分别是矩阵的行数和列数
// space: O(m * n), dp 数组的空间

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

LT.215. Kth Largest Element in an Array

这道题有两种主要解法：最小堆和快速选择（Quick Select）。快速选择使用三路分区（Three-Way Partition）可以高效处理重复元素。

思考过程：

1. 最小堆方法：维护大小为 k 的最小堆，堆顶即为第 k 大元素
2. 快速选择方法：使用 partition 将数组分成三部分，根据 pivot 位置决定递归方向
3. 三路分区的优势：当数组中有大量重复元素时，标准分区会导致 TLE，三路分区可以高效处理

方法一：最小堆（推荐，简单稳定）

核心思想：维护大小为 k 的最小堆，堆中存储当前见过的 k 个最大元素，堆顶即为第 k 大元素。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 最小堆（默认 PriorityQueue 是最小堆）
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int num : nums) {
            pq.offer(num);
            // 保持堆大小为 k，移除最小的元素
            if (pq.size() > k) {
                pq.poll();
            }
        }
        
        return pq.peek(); // 堆顶 = 第 k 大元素
    }
}

// time: O(n log k), n 是数组长度
// space: O(k), 堆的空间

方法二：快速选择 + 三路分区（处理重复元素）

为什么需要三路分区？

标准分区（两路分区）在遇到重复元素时会退化：

• 当所有元素相等时，标准分区会把所有元素分到一边
• 每次递归只减少一个元素 → O(n²) 时间复杂度 → TLE

三路分区将数组分成三部分：[< pivot] [= pivot] [> pivot]，当所有元素相等时可以直接返回，避免递归。

三路分区详解（Dutch National Flag Algorithm）

核心思想：使用三个指针将数组分成三个区域（实现中将 pivot 交换到 left 位置）：

• lt: [left+1, lt-1] 是 < pivot 的区域（lt 指向第一个 = pivot 的位置）
• i: 当前扫描指针，[i, gt] 是未处理的区域
• gt: [gt+1, right] 是 > pivot 的区域（gt 指向最后一个 = pivot 的位置）
• 分区后：[lt, gt] 是 = pivot 的区域（闭区间）

分区过程：

1. 随机选择 pivot 并交换到 left 位置（简化逻辑）
2. 如果 nums[i] < pivot: 交换到左区域，i++, lt++
3. 如果 nums[i] = pivot: 已经在正确位置，i++
4. 如果 nums[i] > pivot: 交换到右区域，gt--（不移动 i，需要检查交换来的元素）

详细示例：

Array: [3, 2, 3, 1, 3, 4, 5, 3], pivot = 3

初始状态：i=0, j=0, k=7, pivot=3
[3, 2, 3, 1, 3, 4, 5, 3]
 ↑
 i,j                     k

j=0: nums[0]=3 = pivot, j++
[3, 2, 3, 1, 3, 4, 5, 3]
 ↑  ↑
 i  j                  k

j=1: nums[1]=2 < pivot, swap(i,j), i++, j++
[2, 3, 3, 1, 3, 4, 5, 3]
    ↑  ↑
    i  j               k

j=2: nums[2]=3 = pivot, j++
[2, 3, 3, 1, 3, 4, 5, 3]
    ↑     ↑
    i     j            k

j=3: nums[3]=1 < pivot, swap(i,j), i++, j++
[2, 1, 3, 3, 3, 4, 5, 3]
       ↑  ↑
       i  j            k

j=4: nums[4]=3 = pivot, j++
[2, 1, 3, 3, 3, 4, 5, 3]
       ↑     ↑
       i     j         k

j=5: nums[5]=4 > pivot, swap(j,k), k--
[2, 1, 3, 3, 3, 3, 5, 4]
       ↑     ↑     ↑
       i     j     k
注意：j 不移动，需要检查交换来的元素

j=5: nums[5]=3 = pivot, j++
[2, 1, 3, 3, 3, 3, 5, 4]
       ↑        ↑  ↑
       i        j  k

j=6: nums[6]=5 > pivot, swap(j,k), k--
[2, 1, 3, 3, 3, 3, 4, 5]
       ↑        ↑  ↑
       i        j  k

j=6: nums[6]=4 > pivot, swap(j,k), k--
[2, 1, 3, 3, 3, 3, 5, 4]
       ↑        ↑  ↑
       i        j  k
但此时 j=6 > k=5，循环结束

最终交换 pivot (nums[right]=3) 到位置 j
[2, 1, 3, 3, 3, 3, 5, 4] → [2, 1, 3, 3, 3, 3, 4, 5]
                              ↑        ↑     ↑
                            i=2        j=6  (pivot最终位置)

返回 [i=2, j=6]，表示 [2,6] 范围内的元素都等于 pivot（闭区间，两端都包含）

完整代码实现

实现要点：

• 使用随机 pivot避免最坏情况
• 将 pivot 交换到 left 位置，简化分区逻辑
• 使用迭代而非递归，空间更优
• 三指针分区：lt（小于区域边界）、i（扫描指针）、gt（大于区域边界）

class Solution {
    private final Random random = new Random();
   
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        // 将第 k 大转换为第 (n-k) 小（0-indexed）
        int target = n - k;
        int left = 0, right = n - 1;
        
        // 迭代版本的快速选择（避免递归栈空间）
        while (left <= right) {
            // 三路分区，返回等于 pivot 的范围 [lt, gt]（闭区间）
            int[] p = partition3(nums, left, right);
            int lt = p[0]; // 等于 pivot 区域的起始索引
            int gt = p[1]; // 等于 pivot 区域的结束索引
            
            if (target < lt) {
                // target 在左半部分（< pivot）
                right = lt - 1;
            } else if (target > gt) {
                // target 在右半部分（> pivot）
                left = gt + 1;
            } else {
                // target 在等于 pivot 的范围内，找到了！
                return nums[lt];
            }
        }
        return -1; // 不应该到达这里
    }

    // 三路分区（Dutch National Flag Algorithm）
    // 将数组分成三部分：[< pivot] [= pivot] [> pivot]
    // 返回：等于 pivot 的元素的起始和结束位置 [lt, gt]（闭区间）
    private int[] partition3(int[] nums, int left, int right) {
        // 随机选择 pivot，避免最坏情况
        int pivotIndex = left + random.nextInt(right - left + 1);
        int pivot = nums[pivotIndex];
        
        // 将 pivot 交换到 left 位置，简化分区逻辑
        swap(nums, left, pivotIndex);
        
        // 初始化三个指针：
        // lt: [left+1, lt-1] 是 < pivot 的区域（lt 指向第一个 = pivot 的位置）
        // i:  扫描指针，当前检查的位置
        // gt: [gt+1, right] 是 > pivot 的区域（gt 指向最后一个 = pivot 的位置）
        int lt = left;        // 小于区域的右边界（不包含），等于区域的起始位置
        int i = left + 1;     // 当前扫描位置，从 left+1 开始
        int gt = right;       // 大于区域的左边界（不包含），等于区域的结束位置
        
        // 扫描未处理的区域 [i, gt]
        while (i <= gt) {
            if (nums[i] < pivot) {
                // 小于 pivot：交换到左区域
                // 交换后，nums[lt] 是之前的小元素，nums[i] 是原来 lt 位置的值
                // lt++ 和 i++ 都移动，因为交换后 i 位置的值已经处理过
                swap(nums, i++, lt++);
            } else if (nums[i] > pivot) {
                // 大于 pivot：交换到右区域
                // 交换后，nums[gt] 是之前的大元素，nums[i] 是交换来的未知值
                // 只移动 gt--，i 不移动，因为需要检查交换来的元素
                swap(nums, i, gt--);
            } else {
                // 等于 pivot：已经在正确位置，继续扫描
                i++;
            }
        }
        
        // 分区完成后的状态：
        // [left+1, lt-1] 是 < pivot 的元素
        // [lt, gt] 是 = pivot 的元素（闭区间）
        // [gt+1, right] 是 > pivot 的元素
        // 注意：left 位置的 pivot 在分区过程中被交换到 [lt, gt] 范围内的某个位置
        
        // 返回等于 pivot 的范围（闭区间）
        return new int[]{lt, gt};
    }

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

// time: O(n) 平均时间，O(n²) 最坏情况（但三路分区使最坏情况很少发生）
// space: O(1) 额外空间，递归栈 O(log n) 平均，O(n) 最坏

为什么三路分区能处理重复元素？

场景：所有元素相等 [5, 5, 5, 5, 5], k = 3

1. 三路分区后：所有元素都在 = pivot 区域
2. 返回范围 [0, 4]（闭区间）
3. k=2 在范围内（0 <= 2 <= 4）→ 直接返回，无需递归！

为什么使用 k <= pivotEnd 而不是 k < pivotEnd？

关键原因：三路分区返回的范围是闭区间 [pivotStart, pivotEnd]，两端都包含。

详细解释：

1. 循环结束后，j 指向第一个 > pivot 区域的位置（或 j = k+1，此时所有元素已处理）
2. 我们执行 swap(nums, j, right)，将 pivot（原来在 nums[right]）交换到位置 j
3. 交换后，nums[j] 也等于 pivot
4. 所以 [i, j] 范围内的所有元素（包括索引 j）都等于 pivot
5. 因此判断时必须使用 k <= pivotEnd 来包含索引 pivotEnd（即 j）本身

示例验证：

分区后：[2, 1, 3, 3, 3, 3, 4, 5]
        < pivot    = pivot    > pivot
索引：   0  1  2  3  4  5  6  7
                    ↑        ↑
                  i=2      j=6 (pivotEnd)

返回 [2, 6]，表示索引 2 到 6（包含）都等于 pivot
如果 k=6，应该被包含在范围内，所以需要 k <= 6

对比标准分区：

• 标准分区：所有元素分到一边，每次只减少一个元素 → O(n²)
• 三路分区：所有相等的元素被识别为一个整体，立即返回 → O(n)

复杂度分析

• 时间复杂度：
  • 平均：O(n) - 每次分区大约消除一半元素
  • 最坏：O(n²) - 但三路分区使最坏情况很少发生（所有元素相等时是 O(n)）
• 空间复杂度：O(1) 额外空间，递归栈 O(log n) 平均

方法选择建议

• 面试/实践：优先使用最小堆，简单稳定，易于解释
• 学习算法：实现三路分区，理解分区思想
• 性能优化：三路分区在重复元素多时更优

208. 实现Trie(前缀树)

LT.208. Implement Trie (Prefix Tree)

Trie（前缀树）是一种树形数据结构，用于高效存储和检索字符串集合。它的核心思想是利用字符串的公共前缀来减少存储空间，并支持快速的前缀匹配。

思考过程：

1. 节点结构：每个节点包含一个子节点数组（26个字母）和一个布尔标志（表示是否为单词结尾）
2. 插入操作：从根节点开始，沿着字符路径创建节点，到达单词末尾时标记为结束
3. 查找操作：从根节点开始，沿着字符路径查找，检查是否存在完整的单词或前缀
4. 辅助方法：find 方法统一处理路径查找，search 和 startsWith 复用该方法

核心思想：

• 共享前缀：具有相同前缀的单词共享路径，节省空间
• 路径表示字符：从根到某个节点的路径表示一个字符串前缀
• 结束标志：isEnd 标志区分完整单词和前缀

class Trie {
    // 根节点（不存储字符，作为所有单词的起始点）
    private final TrieNode root;

    public Trie() {
        root = new TrieNode();
    }
    
    // 插入单词到 Trie 中
    public void insert(String word) {
        TrieNode cur = root;
        // 沿着单词的每个字符路径向下
        for (char c : word.toCharArray()) {
            int idx = c - 'a'; // 将字符转换为索引（'a'=0, 'b'=1, ...）
            // 如果当前字符对应的子节点不存在，创建新节点
            if (cur.children[idx] == null) {
                cur.children[idx] = new TrieNode();
            }
            // 移动到子节点
            cur = cur.children[idx];
        }
        // 标记单词结束
        cur.isEnd = true;
    }
    
    // 查找完整的单词（必须是一个完整的单词，不能只是前缀）
    public boolean search(String word) {
        TrieNode node = find(word);
        // 找到节点且该节点标记为单词结尾
        return node != null && node.isEnd;
    }
    
    // 检查是否存在以给定前缀开头的单词
    public boolean startsWith(String prefix) {
        // 只要找到对应的节点路径即可（不需要是完整单词）
        return find(prefix) != null;
    }

    // 辅助方法：查找字符串对应的节点
    // 如果路径存在返回对应节点，否则返回 null
    private TrieNode find(String s) {
        TrieNode cur = root;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            // 如果路径中断，返回 null
            if (cur.children[idx] == null) return null;
            cur = cur.children[idx];
        }
        return cur;
    }

    // Trie 节点定义
    private static class TrieNode {
        // 子节点数组，每个索引对应一个字母（'a' 到 'z'）
        private TrieNode[] children = new TrieNode[26];
        // 标记当前节点是否为某个单词的结尾
        private boolean isEnd = false;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

// 时间复杂度：
//   insert: O(m), m 是单词长度
//   search: O(m), m 是单词长度
//   startsWith: O(m), m 是前缀长度
// 空间复杂度：O(ALPHABET_SIZE × N × M)，N 是单词数量，M 是平均单词长度

207. 课程表

LT.207. Course Schedule

这道题本质上是判断有向图是否存在环。如果能完成所有课程，说明图中没有环（可以进行拓扑排序）。

思考过程：

1. 问题转换：课程依赖关系构成有向图，判断是否存在环
2. BFS 方法（拓扑排序）：从入度为 0 的节点开始，逐步移除节点，如果所有节点都能被访问，说明无环
3. DFS 方法（状态标记）：使用三种状态标记节点，如果在 DFS 过程中遇到 "visiting" 状态的节点，说明存在环

核心思想：

• 拓扑排序：有向无环图（DAG）可以进行拓扑排序
• 入度统计：BFS 方法通过统计入度，从没有依赖的节点开始处理
• 状态标记：DFS 方法通过状态标记（0=未访问, 1=访问中, 2=已访问）检测后向边（back edge）

方法一：BFS + 拓扑排序（Kahn's Algorithm）

核心思想：从入度为 0 的节点开始，逐步移除节点并更新其邻居的入度，如果所有节点都能被访问，说明无环。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建邻接表表示的有向图
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        // 统计每个节点的入度
        int[] indegree = new int[numCourses];
        
        // 构建图和入度数组
        for (int[] prerequisite : prerequisites) {
            int to = prerequisite[0];   // 目标课程
            int from = prerequisite[1]; // 先修课程
            graph.get(from).add(to);    // from -> to 的边
            indegree[to]++;             // to 的入度加 1
        }

        // 将所有入度为 0 的节点加入队列（没有依赖的课程）
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        // BFS：从入度为 0 的节点开始，逐步移除节点
        int visited = 0;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            visited++;
            // 遍历当前节点的所有邻居
            for (int next : graph.get(cur)) {
                // 减少邻居的入度
                if (--indegree[next] == 0) {
                    // 如果邻居的入度变为 0，加入队列
                    queue.offer(next);
                }
            }
        }
        // 如果所有节点都被访问，说明无环，可以完成所有课程
        return visited == numCourses;
    }
}

// time: O(V + E), V 是课程数，E 是依赖关系数
// space: O(V + E), 图的空间和队列的空间

方法二：DFS + 状态标记（Cycle Detection）

核心思想：使用三种状态标记节点，在 DFS 过程中如果遇到 "visiting" 状态的节点，说明存在后向边（back edge），即存在环。

状态定义：

• 0 (UNVISITED): 未访问
• 1 (VISITING): 正在访问（在递归栈中）
• 2 (VISITED): 已访问（已完成 DFS）

关键洞察：如果在 DFS 过程中遇到状态为 VISITING 的节点，说明存在后向边，即存在环。

class Solution {
    private static final int UNVISITED = 0;
    private static final int VISITING = 1;
    private static final int VISITED = 2;
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建邻接表
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] prerequisite : prerequisites) {
            int to = prerequisite[0];
            int from = prerequisite[1];
            graph.get(from).add(to);
        }
        
        // 状态数组：0=未访问, 1=访问中, 2=已访问
        int[] state = new int[numCourses];
        
        // 对每个节点进行 DFS
        for (int i = 0; i < numCourses; i++) {
            if (state[i] == UNVISITED) {
                if (hasCycle(graph, state, i)) {
                    return false; // 发现环，无法完成
                }
            }
        }
        return true; // 无环，可以完成
    }
    
    // DFS 检测是否存在环
    private boolean hasCycle(List<List<Integer>> graph, int[] state, int node) {
        // 如果节点正在访问中，说明存在后向边（back edge），存在环
        if (state[node] == VISITING) {
            return true;
        }
        // 如果节点已访问，说明这个分支已经检查过，无环
        if (state[node] == VISITED) {
            return false;
        }
        
        // 标记为访问中（进入递归栈）
        state[node] = VISITING;
        
        // 递归访问所有邻居
        for (int next : graph.get(node)) {
            if (hasCycle(graph, state, next)) {
                return true; // 发现环
            }
        }
        
        // 标记为已访问（离开递归栈）
        state[node] = VISITED;
        return false; // 无环
    }
}

// time: O(V + E), V 是课程数，E 是依赖关系数
// space: O(V + E), 图的空间和递归栈的空间

DFS 方法的工作原理：

示例：课程 0 -> 1 -> 2 -> 0（存在环）

DFS(0):
  state[0] = VISITING
  DFS(1):
    state[1] = VISITING
    DFS(2):
      state[2] = VISITING
      DFS(0):
        state[0] == VISITING → 发现环！返回 true

两种方法对比：

复杂度分析：

• 时间复杂度：O(V + E)，需要遍历所有节点和边
• 空间复杂度：O(V + E)，存储图和辅助数组/栈

206. 反转链表

LT.206. Reverse Linked List

这道题的核心思想是使用双指针（或三指针）逐个反转链表的连接方向。

思考过程：

1. 迭代方法：使用 prev、cur、next 三个指针，逐个反转每个节点的 next 指针
2. 递归方法：递归到链表末尾，然后从后往前反转每个节点
3. 关键点：在反转 cur.next 之前，需要先保存 cur.next，否则会丢失后续节点

核心思想：

• 三指针技巧：prev（前一个节点）、cur（当前节点）、next（下一个节点）
• 逐个反转：每次循环反转一个节点的 next 指针
• 边界处理：初始时 prev = null，最终 prev 成为新的头节点

方法一：迭代（推荐）

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;  // 前一个节点，初始为 null
        ListNode cur = head;  // 当前节点，从 head 开始
        
        while (cur != null) {
            // 先保存下一个节点，避免丢失
            ListNode next = cur.next;
            // 反转当前节点的 next 指针
            cur.next = prev;
            // 移动指针：prev 和 cur 都向前移动
            prev = cur;
            cur = next;
        }
        // prev 最终指向原链表的最后一个节点，即反转后的头节点
        return prev;
    }
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

// time: O(n), n 是链表长度
// space: O(1), 只使用了常数额外空间

执行过程可视化：

初始：NULL  1 → 2 → 3 → 4 → NULL
      ↑    ↑
     prev cur

第1步：保存 next = 2
      反转：NULL ← 1    2 → 3 → 4 → NULL
            ↑     ↑    ↑
           prev  cur  next
      移动：NULL ← 1    2 → 3 → 4 → NULL
                 ↑     ↑
                prev  cur

第2步：保存 next = 3
      反转：NULL ← 1 ← 2    3 → 4 → NULL
                 ↑    ↑    ↑
                prev cur  next
      移动：NULL ← 1 ← 2    3 → 4 → NULL
                      ↑     ↑
                     prev  cur

...继续直到 cur == null

最终：NULL ← 1 ← 2 ← 3 ← 4
                      ↑
                     prev (新头节点)

方法二：递归

核心思想：递归到链表末尾，然后从后往前反转每个节点。

class Solution {
    public ListNode reverseList(ListNode head) {
        //  base case：空链表或只有一个节点
        if (head == null || head.next == null) {
            return head;
        }
        
        // 递归反转后续链表，返回新的头节点
        ListNode newHead = reverseList(head.next);
        
        // 反转当前节点和下一个节点的连接
        head.next.next = head;
        head.next = null;
        
        return newHead;
    }
}

// time: O(n), n 是链表长度
// space: O(n), 递归栈的深度

递归过程可视化：

原链表：1 → 2 → 3 → 4 → NULL

递归调用栈：
reverseList(1)
  reverseList(2)
    reverseList(3)
      reverseList(4) → 返回 4（base case）
    反转：4 → 3，返回 4
  反转：4 → 3 → 2，返回 4
反转：4 → 3 → 2 → 1，返回 4

最终：NULL ← 1 ← 2 ← 3 ← 4
                      ↑
                    newHead

两种方法对比：

推荐：优先使用迭代方法，空间效率更高。

200. 岛屿数量

LT.200. Number of Islands

这道题的核心思想是使用 DFS 或 BFS 遍历网格，将连通的 '1' 区域标记为已访问，统计有多少个独立的连通区域。

思考过程：

1. 问题转换：网格中的 '1' 表示陆地，连通的 '1' 组成一个岛屿
2. 遍历策略：遍历整个网格，遇到 '1' 时，使用 DFS/BFS 标记所有连通的 '1'
3. 标记方法：将访问过的 '1' 改为 '0'（"沉没"岛屿），避免重复计算
4. 计数：每次遇到新的 '1'，说明发现一个新岛屿，计数加 1

核心思想：

• 连通性：上下左右相邻的 '1' 属于同一个岛屿
• 标记访问：通过修改原数组标记已访问（"沉没"技术），无需额外空间
• DFS 递归：从每个 '1' 开始，递归标记所有连通的 '1'

DFS 方法（推荐）：

class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        
        // 遍历整个网格
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    // 发现新的岛屿，计数加 1
                    count++;
                    // 使用 DFS 标记所有连通的 '1'（"沉没"整个岛屿）
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }

    // DFS：标记所有与 (i, j) 连通的 '1'
    private void dfs(char[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;
        
        // 边界检查：越界则返回
        if (i < 0 || i >= m || j < 0 || j >= n) return;
        // 如果不是 '1'（可能是 '0' 或已访问），返回
        if (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); // 左
    }
}

// time: O(m × n), m 和 n 是网格的行数和列数
// space: O(m × n), 最坏情况下递归栈的深度（整个网格都是 '1'）

执行过程示例：

初始网格：
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

第1步：发现 (0,0) = '1'，count = 1
DFS(0,0) → 标记所有连通的 '1'：
0 0 0 0 0  (第一个岛屿被"沉没")
0 0 0 0 0
0 0 1 0 0
0 0 0 1 1

第2步：发现 (2,2) = '1'，count = 2
DFS(2,2) → 标记：
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0  (第二个岛屿被"沉没")
0 0 0 1 1

第3步：发现 (3,3) = '1'，count = 3
DFS(3,3) → 标记：
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0  (第三个岛屿被"沉没")

返回 3

关键技巧 - "沉没"技术：

• 将访问过的 '1' 改为 '0'，这样在后续遍历中不会重复计算
• 无需额外的 visited 数组，节省空间
• 修改原数组是安全的，因为题目只要求计数，不要求保留原数组

复杂度分析：

• 时间复杂度：O(m × n)，每个格子最多访问一次
• 空间复杂度：O(m × n)，最坏情况下递归栈的深度（整个网格都是 '1' 时，形成一条长链）

优化提示：如果网格很大，可以考虑使用 BFS（迭代）来避免递归栈溢出。

198. 打家劫舍

LT.198. House Robber

这道题的核心思想是使用动态规划，对于每个房子，我们有两个选择：偷或不偷，选择收益更大的方案。

思考过程：

1. 定义状态：dp[i] 表示前 i 个房子能获得的最大金额
2. 状态转移：对于第 i 个房子，有两种选择：
   • 不偷：dp[i] = dp[i-1]（保持前 i-1 个房子的最大金额）
   • 偷：dp[i] = dp[i-2] + nums[i]（前 i-2 个房子的最大金额 + 当前房子金额）
   • 取两者最大值
3. 边界情况：前 0 个房子为 0，前 1 个房子为 nums[0]

核心思想：

• 最优子结构：前 i 个房子的最优解依赖于前 i-1 和前 i-2 个房子的最优解
• 状态转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
• 空间优化：由于只依赖前两个状态，可以用 O(1) 空间

方法一：标准 DP（你的实现）

你的代码是正确的！可以稍微简化边界处理。

class Solution {
    public int rob(int[] nums) {
        // 边界情况处理
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        
        // dp[i] 表示前 i 个房子能获得的最大金额
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        // 对于每个房子，选择偷或不偷
        for (int i = 2; i < nums.length; i++) {
            // 不偷当前房子：保持前 i-1 个房子的最大金额
            // 偷当前房子：前 i-2 个房子的最大金额 + 当前房子金额
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        
        return dp[nums.length - 1];
    }
}

// time: O(n), n 是房子数量
// space: O(n), dp 数组的空间

改进建议：

1. 简化边界处理：可以统一处理，让代码更简洁
2. 空间优化：只依赖前两个状态，可以优化到 O(1) 空间

方法二：简化版本（统一边界处理）

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        
        return dp[n - 1];
    }
}

方法三：空间优化版本（O(1) 空间）

核心思想：由于 dp[i] 只依赖 dp[i-1] 和 dp[i-2]，可以用两个变量代替整个数组。

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        // 用两个变量代替 dp 数组
        int prev2 = nums[0];           // dp[i-2]
        int prev1 = Math.max(nums[0], nums[1]); // dp[i-1]
        
        for (int i = 2; i < n; i++) {
            // 计算 dp[i]
            int cur = Math.max(prev1, prev2 + nums[i]);
            // 更新状态：向前移动
            prev2 = prev1;
            prev1 = cur;
        }
        
        return prev1;
    }
}

// time: O(n)
// space: O(1), 只使用了常数额外空间