Skip to content

Commit 880afc7

Browse files
JstarfishJstarfish
committed
📖dfs
1 parent 5488199 commit 880afc7

File tree

5 files changed

+249
-52
lines changed

5 files changed

+249
-52
lines changed

‎docs/.DS_Store‎

0 Bytes
Binary file not shown.

‎docs/data-management/.DS_Store‎

0 Bytes
Binary file not shown.

‎docs/data-structure-algorithms/algorithm/DFS-BFS.md‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -123,6 +123,82 @@ categories: BFS DFS
123123

124124
**说明**：深度优先遍历的结果通常与图的顶点如何存储有关，所以图的深度优先遍历的结果并不唯一。
125125

126+
#### [课程表](https://leetcode.cn/problems/course-schedule/)
127+
128+
> 你这个学期必须选修 `numCourses` 门课程，记为 `0` 到 `numCourses - 1` 。
129+
>
130+
> 在选修某些课程之前需要一些先修课程。 先修课程按数组 `prerequisites` 给出，其中 `prerequisites[i] = [ai, bi]` ，表示如果要学习课程 `ai` 则 **必须** 先学习课程 `bi` 。
131+
>
132+
> - 例如，先修课程对 `[0, 1]` 表示：想要学习课程 `0` ，你需要先完成课程 `1` 。
133+
>
134+
> 请你判断是否可能完成所有课程的学习？如果可以，返回 `true` ；否则，返回 `false` 。
135+
>
136+
> ```
137+
> 输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
138+
> 输出：false
139+
> 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
140+
> ```
141+
142+
思路：对于课程表问题，实际上是在寻找一个有向无环图（DAG）的环，以确定是否存在一个有效的课程学习顺序。
143+
144+
```java
145+
public class Solution {
146+
private boolean hasCycle = false;
147+
148+
public boolean canFinish(int numCourses, int[][] prerequisites) {
149+
// 构建图的邻接表表示
150+
List<List<Integer>> graph = new ArrayList<>();
151+
for (int i = 0; i < numCourses; i++) {
152+
graph.add(new ArrayList<>());
153+
}
154+
for (int[] prerequisite : prerequisites) {
155+
int course = prerequisite[0];
156+
int prerequisiteCourse = prerequisite[1];
157+
graph.get(prerequisiteCourse).add(course);
158+
}
159+
160+
// 初始化访问状态数组
161+
boolean[] visited = new boolean[numCourses];
162+
boolean[] recursionStack = new boolean[numCourses];
163+
164+
// 对每个节点进行DFS遍历
165+
for (int i = 0; i < numCourses; i++) {
166+
if (!visited[i]) {
167+
dfs(graph, visited, recursionStack, i);
168+
}
169+
// 如果在DFS过程中检测到了环，则提前返回false
170+
if (hasCycle) {
171+
return false;
172+
}
173+
}
174+
175+
// 如果没有检测到环，则返回true
176+
return true;
177+
}
178+
179+
private void dfs(List<List<Integer>> graph, boolean[] visited, boolean[] recursionStack, int node) {
180+
// 将当前节点标记为已访问
181+
visited[node] = true;
182+
// 将当前节点加入递归栈
183+
recursionStack[node] = true;
184+
185+
// 遍历当前节点的所有邻接节点
186+
for (int neighbor : graph.get(node)) {
187+
// 如果邻接节点未被访问，则递归访问
188+
if (!visited[neighbor]) {
189+
dfs(graph, visited, recursionStack, neighbor);
190+
} else if (recursionStack[neighbor]) {
191+
// 如果邻接节点已经在递归栈中，说明存在环
192+
hasCycle = true;
193+
}
194+
}
195+
196+
// 将当前节点从递归栈中移除
197+
recursionStack[node] = false;
198+
}
199+
}
200+
```
201+
126202

127203

128204
### 2.4 深度优先遍历的两种实现方式

‎docs/data-structure-algorithms/soultion/Binary-Tree-Solution.md‎

Lines changed: 44 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -652,7 +652,7 @@ public int minDepth(TreeNode root) {
652652
在**前序位置操作**是为了确保在递归遍历时，首先处理当前节点的子树，具体是交换左右子树的顺序。这样做能够保证在遍历左右子树之前，当前节点的左右子节点已经被正确地交换。
653653
654654
```java
655-
public static TreeNode invertTree(TreeNode root) {
655+
public TreeNode invertTree(TreeNode root) {
656656
if(root == null){
657657
return root;
658658
}
@@ -1526,19 +1526,20 @@ class Solution {
15261526
int[] result = dfs(root);
15271527
return Math.max(result[0], result[1]);
15281528
}
1529-
1529+
1530+
// 返回数组：int[0]表示偷当前节点的最大值，int[1]表示不偷的最大值
15301531
private int[] dfs(TreeNode node) {
1531-
if (node == null) {
1532-
return new int[]{0, 0}; // {rob(node), notRob(node)}
1533-
}
1534-
1535-
int[] left = dfs(node.left);
1536-
int[] right = dfs(node.right);
1537-
1538-
int robNode = node.val + left[1] + right[1]; // 抢劫当前节点
1539-
int notRobNode = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); // 不抢劫当前节点
1540-
1541-
return new int[]{robNode, notRobNode};
1532+
if (node == null) return new int[]{0, 0}; //
1533+
1534+
int[] left = dfs(node.left); // 左子树偷/不偷的最大值
1535+
int[] right = dfs(node.right); // 右子树偷/不偷的最大值
1536+
1537+
// 偷当前节点：左右子节点必须不偷
1538+
int robCurrent = node.val + left[1] + right[1];
1539+
// 不偷当前节点：左右子节点可偷或不偷（取最大值）
1540+
int skipCurrent = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
1541+
1542+
return new int[]{robCurrent, skipCurrent}; //
15421543
}
15431544
}
15441545
```
@@ -1554,9 +1555,9 @@ class Solution {
15541555
> ![img](https://assets.leetcode.com/uploads/2018/12/14/binarytree.png)
15551556
>
15561557
> ```
1557-
> 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
1558-
> 输出：3
1559-
> 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
1558+
> 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
1559+
> 输出：5
1560+
> 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
15601561
> ```
15611562
15621563
**思路：**
@@ -1573,13 +1574,33 @@ class Solution {
15731574
15741575
15751576
```java
1576-
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
1577-
if(root == null || root == p || root == q) return root;
1578-
TreeNode left = lowestCommonAncestor(root.left, p, q);
1579-
TreeNode right = lowestCommonAncestor(root.right, p, q);
1580-
if(left == null) return right;
1581-
if(right == null) return left;
1582-
return root;
1577+
public class Solution {
1578+
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
1579+
// 如果当前节点为空，则返回null
1580+
if (root == null) {
1581+
return null;
1582+
}
1583+
// 如果当前节点是p或q，则返回当前节点
1584+
if (root == p || root == q) {
1585+
return root;
1586+
}
1587+
// 递归地在左子树中查找p和q
1588+
TreeNode left = lowestCommonAncestor(root.left, p, q);
1589+
// 递归地在右子树中查找p和q
1590+
TreeNode right = lowestCommonAncestor(root.right, p, q);
1591+
1592+
// 根据left和right的值来判断最近公共祖先
1593+
if (left != null && right != null) {
1594+
// p和q分别位于左右子树中，当前节点是最近公共祖先
1595+
return root;
1596+
} else if (left != null) {
1597+
// p和q都在左子树中，返回左子树的结果
1598+
return left;
1599+
} else {
1600+
// p和q都在右子树中，返回右子树的结果
1601+
return right;
1602+
}
1603+
}
15831604
}
15841605
```
15851606

‎docs/data-structure-algorithms/soultion/DFS-Solution.md‎

Lines changed: 129 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -90,38 +90,43 @@ categories: leetcode
9090

9191
#### [岛屿数量『200』](https://leetcode.cn/problems/number-of-islands/)
9292

93-
- **问题描述**：给你一个由 `'1'`（陆地）和 `'0'`（水）组成的的二维网格，请你计算网格中岛屿的数量。
94-
95-
![](https://pic.leetcode-cn.com/c36f9ee4aa60007f02ff4298bc355fd6160aa2b0d628c3607c9281ce864b75a2.jpg)
96-
97-
```
98-
输入：grid = [
99-
["1","1","1","1","0"],
100-
["1","1","0","1","0"],
101-
["1","1","0","0","0"],
102-
["0","0","0","0","0"]
103-
]
104-
输出：1
105-
```
93+
> 给你一个由 `'1'`（陆地）和 `'0'`（水）组成的的二维网格，请你计算网格中岛屿的数量。
94+
>
95+
> 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
96+
>
97+
> 此外，你可以假设该网格的四条边均被水包围。![](https://pic.leetcode-cn.com/c36f9ee4aa60007f02ff4298bc355fd6160aa2b0d628c3607c9281ce864b75a2.jpg)
98+
>
99+
> ```
100+
> 输入：grid = [
101+
> ["1","1","1","1","0"],
102+
> ["1","1","0","1","0"],
103+
> ["1","1","0","0","0"],
104+
> ["0","0","0","0","0"]
105+
> ]
106+
> 输出：1
107+
> ```
106108
107-
- **DFS 思路**：遍历网格，遇到 '1' 时启动 DFS 淹没相连的陆地。
109+
**思路**：
108110
109-
- 代码实现：
111+
- 遍历网格，遇到未访问的`'1'`时启动DFS，将该岛屿所有相连陆地标记为已访问。
112+
- **标记方式**：直接修改原数组（如`'1'`→`'0'`），或使用独立`visited`数组
110113
111-
```java
114+
```java
115+
public Class Soultion{
112116
public int numIslands(char[][] grid) {
113-
int count = 0;
114-
for (int i = 0; i < grid.length; i++) {
115-
for (int j = 0; j < grid[0].length; j++) {
116-
if (grid[i][j] == '1') {
117-
dfs(grid, i, j);
118-
count++;
119-
}
120-
}
121-
}
122-
return count;
123-
}
124-
117+
int count = 0;
118+
for (int i = 0; i < grid.length; i++) {
119+
for (int j = 0; j < grid[0].length; j++) {
120+
//如果当前是陆地，才开始一次DFS遍历
121+
if (grid[i][j] == '1') {
122+
dfs(grid, i, j);
123+
count++;
124+
}
125+
}
126+
}
127+
return count;
128+
}
129+
125130
private void dfs(char[][] grid, int r, int c) {
126131
// 判断 base case
127132
// 检查边界条件和当前位置是否为陆地
@@ -134,7 +139,22 @@ categories: leetcode
134139
dfs(grid, r, c + 1);
135140
dfs(grid, r, c - 1);
136141
}
137-
```
142+
}
143+
144+
---单测
145+
@Test
146+
public void testNumIslands_singleIsland() {
147+
char[][] grid = {
148+
{'1', '1', '1', '1', '0'},
149+
{'1', '1', '0', '1', '0'},
150+
{'1', '1', '0', '0', '0'},
151+
{'0', '0', '0', '0', '0'}
152+
};
153+
DfsSolution solution = new DfsSolution();
154+
int result = solution.numIslands(grid);
155+
assertEquals(1, result);
156+
}
157+
```
138158
139159
- **复杂度**：时间 $O(MN)$，空间 $O(MN)$（递归栈）。
140160

@@ -491,6 +511,86 @@ public boolean check(TreeNode left,TreeNode right){
491511

492512
- **复杂度**：时间 O(4^N/√N)，空间 O(N)。
493513

514+
515+
516+
#### [课程表『207』](https://leetcode.cn/problems/course-schedule/)
517+
518+
> 你这个学期必须选修 `numCourses` 门课程，记为 `0` 到 `numCourses - 1` 。
519+
>
520+
> 在选修某些课程之前需要一些先修课程。 先修课程按数组 `prerequisites` 给出，其中 `prerequisites[i] = [ai, bi]` ，表示如果要学习课程 `ai` 则 **必须** 先学习课程 `bi` 。
521+
>
522+
> - 例如，先修课程对 `[0, 1]` 表示：想要学习课程 `0` ，你需要先完成课程 `1` 。
523+
>
524+
> 请你判断是否可能完成所有课程的学习？如果可以，返回 `true` ；否则，返回 `false` 。
525+
>
526+
> ```
527+
> 输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
528+
> 输出：false
529+
> 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成 课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
530+
> ```
531+
532+
思路：要检测有向图中的环，我们可以使用DFS遍历图，并记录访问状态。在遍历过程中，如果我们遇到一个已经访问过的节点，并且它不是当前节点的父节点（在递归调用中），那么我们就找到了一个环。
533+
534+
```java
535+
public class Solution {
536+
private boolean hasCycle = false;
537+
538+
public boolean canFinish(int numCourses, int[][] prerequisites) {
539+
// 构建图的邻接表表示
540+
List<List<Integer>> graph = new ArrayList<>();
541+
for (int i = 0; i < numCourses; i++) {
542+
graph.add(new ArrayList<>());
543+
}
544+
for (int[] prerequisite : prerequisites) {
545+
int course = prerequisite[0];
546+
int prerequisiteCourse = prerequisite[1];
547+
graph.get(prerequisiteCourse).add(course);
548+
}
549+
550+
// 初始化访问状态数组
551+
boolean[] visited = new boolean[numCourses];
552+
boolean[] recursionStack = new boolean[numCourses];
553+
554+
// 对每个节点进行DFS遍历
555+
for (int i = 0; i < numCourses; i++) {
556+
if (!visited[i]) {
557+
dfs(graph, visited, recursionStack, i);
558+
}
559+
// 如果在DFS过程中检测到了环，则提前返回false
560+
if (hasCycle) {
561+
return false;
562+
}
563+
}
564+
565+
// 如果没有检测到环，则返回true
566+
return true;
567+
}
568+
569+
private void dfs(List<List<Integer>> graph, boolean[] visited, boolean[] recursionStack, int node) {
570+
// 将当前节点标记为已访问
571+
visited[node] = true;
572+
// 将当前节点加入递归栈
573+
recursionStack[node] = true;
574+
575+
// 遍历当前节点的所有邻接节点
576+
for (int neighbor : graph.get(node)) {
577+
// 如果邻接节点未被访问，则递归访问
578+
if (!visited[neighbor]) {
579+
dfs(graph, visited, recursionStack, neighbor);
580+
} else if (recursionStack[neighbor]) {
581+
// 如果邻接节点已经在递归栈中，说明存在环
582+
hasCycle = true;
583+
}
584+
}
585+
586+
// 将当前节点从递归栈中移除
587+
recursionStack[node] = false;
588+
}
589+
}
590+
```
591+
592+
593+
494594
#### [目标和『494』](https://leetcode.cn/problems/target-sum/)
495595

496596
- **问题描述**：向数组中的每个数前添加 '+' 或 '-'，使得总和等于 target。

0 commit comments

Comments
 (0)