【寸铁的刷题笔记】图论、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);}
}

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';//把最后棋盘中与外界连通的标记 * 替换为 Oelse 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);}
}

133. 克隆图

考点

哈希表、bfs

思路

思想: bfs,宽搜。
从起点节点开始出发,入队,出队，将该起点节点的邻接节点入队,并标记被搜索过（哈希表记录）
再弹出当前队列的节点,入队,并继续标记其邻接节点。
依次一层一层的搜索下去,直至最后队列为空,说明已经拷贝完图的所有节点。

代码

/*
// Definition for a Node.
class Node {public int val;public List<Node> neighbors;public Node() {val = 0;neighbors = new ArrayList<Node>();}public Node(int _val) {val = _val;neighbors = new ArrayList<Node>();}public Node(int _val, ArrayList<Node> _neighbors) {val = _val;neighbors = _neighbors;}
}
*/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];}
}

207. 课程表

考点

bfs、拓扑排序

思路

思想: 要想修一门课程,则需要先修它的先修课程。
所以, 我们可以把他看成是一个有向无环图。
判断最后每个点是不是入度、出度为0的节点数等于课程数即可。

做法

先将先修课程向要修课程连一条边，同时记录要修课程的入度。
再统计每个点的入度,在bfs时,将待修课程节点的入度--
最后, 判断入度为0的节点数是否等于课程数。
等于则说明可以完成所有课程的学习。
不等于则说明存在环,陷入死循环中,无法完成课程的学习。

代码

class Solution {/*思想: 要想修一门课程,则需要先修它的先修课程。所以, 我们可以把他看成是一个有向无环图。判断最后每个点是不是入度、出度为0的节点数等于课程数即可。先将先修课程向要修课程连一条边再统计每个点的入度,在bfs搜索时,将先修课程节点的出度--最后, 入读和出度都为0,则说明可以完成所有课程的学习。最后, 判断入度、出度为0的节点数是否等于课程数。等于则说明可以完成所有课程的学习。不等于则说明存在环,陷入死循环中,无法完成课程的学习。*/public boolean canFinish(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){//要想修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;}
}

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;//返回结果数组}
}