DFS

LeetCode 329 https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题为记忆化 DFS。使用 memo[i][j] 维护以 matrix[i][j] 为起点的最长递增路径的长度。 时间复杂度：O(mn)，其中 m 和 n 分别是矩阵的行数和列数。深度优先搜索的时间复杂度是 O(V+E)，其中 V 是节点数，E 是边数。在矩阵中，O(V)=O(mn)，O(E)≈O(4mn)=O(mn)。 空间复杂度：O(mn)，其中 m 和 n 分别是矩阵的行数和列数。空间复杂度主要取决于缓存和递归调用深度，缓存的空间复杂度是 O(mn)，递归调用深度不会超过 mn。 ...

LeetCode 207 https://leetcode.cn/problems/course-schedule/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 三色标记法找环。 对于每个节点 x，都定义三种颜色值： 0：x 尚未被访问到。 1：x 正在被访问，dfs(x) 尚未结束。 2：x 已访问完毕，dfs(x) 已返回。 如果在递归过程中，发现下一个节点在递归栈中（正在访问中），则找到了环。 时间复杂度：O(n+m)，其中 n 是 numCourses，m 是 prerequisites 的长度。每个节点至多递归访问一次，每条边至多遍历一次。 空间复杂度：O(n+m)。存储 g 需要 O(n+m) 的空间。 ...

LeetCode:695 https://leetcode.cn/problems/max-area-of-island/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 网格图 DFS，类似 LeetCode 200 岛屿数量，增加一个当前岛屿面积的计算。 时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。 空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。 ...

LeetCode 200 https://leetcode.cn/problems/number-of-islands/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是一道图论 DFS 的题目。初始图中的陆地为 1，水为 0。当我们遍历陆地的时候，将遍历过的陆地改为 2，以防止重复访问。 遍历整张图，如果发现 grid[i][j] == 1，说明这是一块没被访问过的岛屿，dfs(i, j)，岛屿数量加一。 时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。 空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。 ...