-
【寸铁的刷题笔记】图论、bfs、dfs
【寸铁的刷题笔记】图论、bfs、dfs
大家好 我是寸铁👊
金三银四，图论基础结合bfs、dfs是必考的知识点✨
快跟着寸铁刷起来！面试顺利上岸👋
喜欢的小伙伴可以点点关注 💝
🌞详见如下专栏🌞
🍀🍀🍀寸铁的刷题笔记🍀🍀🍀
200. 岛屿数量
考点
递归、dfs
思路
思路:遍历二维数组,遇到陆地则计数器加
1
然后,向该陆地上、下、左、右四个方向进行搜索。
遇到边界则停止搜索,如果搜索到的网格为陆地,则说明该网格和遍历到的陆地连通。
同时,把该搜索到的陆地'1',置为海洋'0'
由于之前遍历二维数组时遇到陆地时计数器加1,由于连通,算作1个岛屿。
这样就避免下次遍历二维数组时重复遍历陆地,导致岛屿数量多算了。代码
class Solution { /* 思路:遍历二维数组,遇到陆地则计数器加1 然后,向该陆地上、下、左、右四个方向进行搜索。 遇到边界则停止搜索,如果搜索到的网格为陆地,则该网格和遍历到的陆地连通。 同时,把该搜索到的陆地'1',置为海洋'0' 由于之前遍历二维数组时遇到陆地时计数器加1,由于连通,算作1个岛屿。 这样就避免下次遍历二维数组时,重复遍历陆地,导致岛屿数量多算了。 */ 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'){//如果说遍历到的节点是陆地'1' dfs(grid , i , j);//则调用递归函数将该陆地周围的陆地进行置0操作 count++;//陆地数量++ } } } return count;//返回陆地的数量 } public void dfs(char [][]grid , int i , int j){ //边界条件,遇到边界则搜索停下来。 if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0')return; //将陆地周围联通的陆地进行置0 , 避免重复遍历,统计陆地的数量不正确。 grid[i][j] = '0'; //向上、下、左、右四个方向进行遍历,把能走通的陆地进行置0,避免重复遍历。 //上 dfs(grid , i -1 , j); //下 dfs(grid , i + 1 , j); //左 dfs(grid , i , j - 1); //右 dfs(grid , i , j + 1); } }- 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
130. 被围绕的区域
考点
递归、dfs
思路
题目描述
这道题是让我们寻找所有被
X围绕的区域,并将这块区域中的所有的'O用X进行填充。转换问题
那么怎么样去寻找所有被
X围绕的区域呢？
直接做肯定不好做,不妨反过来思考,什么样的才是不被X围绕的区域呢？
观察题目图形,我们发现如果
O位于棋盘边界的位置,则说明O不被X所围绕,与外界连通。那么问题就转换为去搜索从边界的
O开始连通的O区域,这一部分连通的区域必定是不满足条件的,也就是不用替换为X的。
所以,我们从边界的位置出发,去搜索从边界的O开始连通的O区域,并把搜索过的O标记为*,避免后面被重复遍历。如下图
绿色为棋盘的边界部分
复原操作
最后,对棋盘的字符进行复原操作,把标记的
*复原为X。
剩下的O则为被包围的区域,进行替换为X即可。
代码
class Solution { /* 思路: 这道题是让我们寻找所有被'X'围绕的区域,并将这块区域中的所有'O'用'X'进行填充。 那么,怎么样去寻找所有被'X'围绕的区域呢？ 直接做肯定不好做,不妨反过来思考,什么样的才是不被'X'围绕的区域呢？ 观察图形,我们发现如果O位于棋盘边界的位置,则说明'O'不被'X'所围绕。 那么问题就转换为去搜索从边界的'O'开始连通的'O'区域,这一部分连通的区域必定是不满足条件的,也就是不用替换为'X'的。 所以,我们从边界的位置出发,去搜索从边界的'O'开始连通的'O'区域,并把搜索过的'O'标记为'*',避免后面被重复遍历。 最后,对棋盘的字符进行复原操作,把标记的'*'复原为'X'。 剩下的'O'则为被包围的区域,进行替换为'X'即可。 */ int m;//棋盘的行数 int n;//棋盘的列数 public void solve(char[][] board) { 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 i = 1; i < n - 1; i++){ dfs(board , 0 , i);//第一行除了头尾之外的位置 dfs(board , m - 1, i);//最后一行除了头尾之外的位置 } //dfs处理完毕后,再进行棋盘复原操作 for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ //如果说最后的棋盘为O 则直接进行赋值为X即可 if(board[i][j] == 'O')board[i][j] = 'X'; //把最后棋盘中与外界连通的标记 * 替换为 O else if(board[i][j] == '*')board[i][j] = 'O'; } } } //寻找与外界棋盘O字符连通的区域 public void dfs(char [][]board , int i , int j){ //如果说越界了或者说之前被标记为'*'(已经被遍历过)或者是'X'则停止搜索 if(i < 0 || j < 0 || i >= m || j >= n || board[i][j] == '*' || board[i][j] == 'X')return; board[i][j] = '*'; //标记为* 表示与外界连通并且这个位置已经被遍历过了,不再重复遍历。 //上 dfs(board , i - 1 , j); //下 dfs(board , i + 1 , j); //左 dfs(board , i , j - 1); //右 dfs(board , i , j + 1); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
133. 克隆图
考点
哈希表、bfs
思路
思想:
bfs,宽搜。
从起点节点开始出发,入队,出队，将该起点节点的邻接节点入队,并标记被搜索过（哈希表记录）
再弹出当前队列的节点,入队,并继续标记其邻接节点。
依次一层一层的搜索下去,直至最后队列为空,说明已经拷贝完图的所有节点。代码
/* // Definition for a Node. class Node { public int val; public Listneighbors; public Node() { val = 0; neighbors = new ArrayList class Solution { public Node cloneGraph(Node node) { /* 思想: bfs,宽搜。 从起点节点开始出发,入队,出队，将该起点节点的邻接节点入队,并标记被搜索过。 再弹出当前队列的节点,入队,并继续标记其邻接节点。 依次一层一层的搜索下去,直至最后队列为空,说明已经拷贝完图的所有节点。 */ if(node == null)return null;//空节点不拷贝 Node []cloneNodes = new Node[110];//存储的是每一个已经拷贝(克隆)的节点,标记已被搜索过 cloneNodes[node.val] = new Node(node.val);//克隆起点节点 Queue<Node>queue = new LinkedList<>();//存储bfs的队列 queue.offer(node); //起点节点入队 Node cur; // 记录当前处理的节点 while(!queue.isEmpty()){ cur = queue.poll(); //从队列中获取一个待处理的节点 Node cloneNode = cloneNodes[cur.val];//待处理的节点一定是克隆好的,直接获取其克隆节点 for(Node neighbor : cur.neighbors){ if(cloneNodes[neighbor.val] == null){ //如果邻接节点未拷贝则进行拷贝 cloneNodes[neighbor.val] = new Node(neighbor.val); queue.offer(neighbor);//邻接节点入队,用于下一轮的节点获取。 } //克隆节点的邻居添加入遍历过的拷贝节点的邻接节点 cloneNode.neighbors.add(cloneNodes[neighbor.val]); } } //返回克隆节点的记录数组即可 return cloneNodes[node.val]; } }(); } public Node(int _val) { val = _val; neighbors = new ArrayList (); } public Node(int _val, ArrayList _neighbors) { val = _val; neighbors = _neighbors; } } */ - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
207. 课程表
考点
bfs、拓扑排序
思路
思想: 要想修一门课程,则需要先修它的先修课程。
所以, 我们可以把他看成是一个有向无环图。
判断最后每个点是不是入度、出度为0的节点数等于课程数即可。做法
-
先将先修课程向要修课程连一条边，同时记录要修课程的
入度。 -
再统计每个点的入度,在
bfs时,将待修课程节点的入度-- -
最后, 判断
入度为0的节点数是否等于课程数。
等于则说明可以完成所有课程的学习。
不等于则说明存在环,陷入死循环中,无法完成课程的学习。
代码
class Solution { /* 思想: 要想修一门课程,则需要先修它的先修课程。 所以, 我们可以把他看成是一个有向无环图。 判断最后每个点是不是入度、出度为0的节点数等于课程数即可。 先将先修课程向要修课程连一条边 再统计每个点的入度,在bfs搜索时,将先修课程节点的出度-- 最后, 入读和出度都为0,则说明可以完成所有课程的学习。 最后, 判断入度、出度为0的节点数是否等于课程数。 等于则说明可以完成所有课程的学习。 不等于则说明存在环,陷入死循环中,无法完成课程的学习。 */ public boolean canFinish(int numCourses, int[][] prerequisites) { int []indegress = new int[numCourses]; Listqueue = new LinkedList<>(); for(int i = 0; i < numCourses; i++){ adjacency.add(new ArrayList<>()); } for(int []cp : prerequisites){ //要想修0必须先修1 //对0而言是入度,对1而言是出度 indegress[cp[0]]++;//入度++ //先修课程向要修课程向连一条边 adjacency.get(cp[1]).add(cp[0]); } //寻找入度为0的点开始进行拓扑排序 //入度为0则说明它是可以修的课程 for(int i = 0; i < numCourses; i++){ if(indegress[i] == 0)queue.add(i); } while(!queue.isEmpty()){ //弹出入度为0的节点,说明该课程可以被修。 int pre = queue.poll(); //同时课程数量-- numCourses--; //遍历先修课程的节点 for(int cur : adjacency.get(pre)){ //出度-- //如果说点cur的入度与出度都为0 //则队列中添加节点cur,用于下一轮的搜索。 if(--indegress[cur] == 0){ queue.add(cur); } } } //最后,判断一下是不是课程数等于0 //如果说课程数等于0 则代表可以完成所有课程的学习。 return numCourses == 0; } } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
210. 课程表 II
考点
bfs、拓扑排序
思路
在课程表题目的基础上,多维护一个
数组,用于记录当前弹出的节点的路径（走过的节点）
弹出的节点是入度为0的节点,入度为0说明为已修的先修课程,并且是先修完的,可以按照这个顺序来。代码
class Solution { //在课程表题目的基础上,多维护一个数组,用于记录当前弹出的节点的路径 //弹出的节点是入度为0的节点,入度为0说明为已修的先修课程,并且是先修完的,可以按照这个顺序来。 public int[] findOrder(int numCourses, int[][] prerequisites) { int []indegress = new int[numCourses];//记录每个节点的入度 List<List<Integer>>adjacency = new ArrayList<>();//维护一个列表用于存储边 Queue<Integer>queue = new LinkedList<>();//创建队列,用于存储节点 for(int i = 0; i < numCourses; i++){ adjacency.add(new ArrayList<>());//每个节点先添加列表用于存连接的节点(边) } for(int []cp : prerequisites){ indegress[cp[0]]++; //要修课程的入度++ adjacency.get(cp[1]).add(cp[0]); //将先修课程和待修课程连一条边 //用于后续遍历入度为0节点的队列将待修课程的入度-- //用于下一轮的循环 } //先将入度为0的节点添加入队列 for(int i = 0; i < numCourses; i++){ if(indegress[i] == 0)queue.add(i); } //创建数组ans,用于记录学完所有课程所安排的学习顺序。 int ans[] = new int[numCourses]; int index = 0;//数组下标,用于存储学完的课程 while(!queue.isEmpty()){ int pre = queue.poll(); ans[index++]=pre;//入度为0的节点是确保能够修完的先修课程,存到结果数组中。 for(int cur : adjacency.get(pre)){//将每个待修课程的入度-- if(--indegress[cur] == 0){ queue.add(cur);//入度为0则入队 } } } //最后的结果是入度均为0 //如果说某个节点的入度 > 0 , 则说明不可能修完全部课程, 存在一个环。 //如[[0,1],[1,0]] //这里无法找到一个入度为0的节点,存在一个环。 for(int i = 0; i < indegress.length; i++){ if(indegress[i] > 0)return new int[0];//返回一个空数组即可 } //等价写法如下： //如果说index不等于课程数量,则说明存在入度不为0的点,也就是环。 // if(index != numCourses){ // return new int[0]; // } return ans;//返回结果数组 } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
看到这里的小伙伴，恭喜你又掌握了一个技能👊
希望大家能取得胜利，坚持就是胜利💪
我是寸铁！我们下期再见💕往期好文💕
保姆级教程
【保姆级教程】Windows11下go-zero的etcd安装与初步使用
【保姆级教程】Windows11安装go-zero代码生成工具goctl、protoc、go-zero
【Go-Zero】手把手带你在goland中创建api文件并设置高亮
报错解决
【Go-Zero】Error: user.api 27:9 syntax error: expected ‘:‘ | ‘IDENT‘ | ‘INT‘, got ‘(‘ 报错解决方案及api路由注意事项
【Go-Zero】Error: only one service expected goctl一键转换生成rpc服务错误解决方案
【Go-Zero】【error】 failed to initialize database, got error Error 1045 (28000):报错解决方案
【Go-Zero】Error 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using password: YES)报错解决方案
【Go-Zero】type mismatch for field “Auth.AccessSecret“, expect “string“, actual “number“报错解决方案
【Go-Zero】Error: user.api 30:2 syntax error: expected ‘)‘ | ‘KEY‘, got ‘IDENT‘报错解决方案
【Go-Zero】Windows启动rpc服务报错panic:context deadline exceeded解决方案
Go面试向
-
相关阅读:
在Flask中使用Jinjia2
练习编程题-第一期
双十一蓝牙耳机怎么挑选？2022公认音质最好的蓝牙耳机
【数据结构】字符串匹配（暴力匹配）
大家都在用MySQL count(*)统计总数，到底有什么问题？
【设计模式之单例模式二】
Yakit工具篇：中间人攻击(平替Burp)的相关技巧-03
结构体（1）
涨工资不是程序员跳槽的理由
如何选择编程语言Python Go还是Rust？
- 原文地址：https://blog.csdn.net/joeyoj/article/details/136283908
