文章目录FloodFill算法简介一、图像渲染解题思路代码实现及解析总结二、岛屿数量解题思路代码实现及解析总结三、被围绕的区域解题思路代码实现及解析总结FloodFill算法简介FloodFill算法介绍AI总结FloodFill泛洪填充/漫水填充算法简单说就是从一个“种子点”出发像洪水蔓延一样查找到周围所有符合条件的位置共同形成这样的一个区块。它最直观的应用就是画图软件里的“油漆桶”工具。核心原理扩散与连通算法基于图遍历DFS或BFS实现核心逻辑如下起点选择一个起始像素点种子点。扩散检查该点的上下左右四邻域或有些时候也要求包括对角线八邻域的邻居。条件如果邻居的颜色与起点颜色相同且未被访问过就将其“感染”成新颜色并继续以该邻居为起点重复扩散。终止当所有符合条件的邻居都被处理完毕算法结束。两种实现方式DFS深度优先代码简洁像“一条路走到黑”。适合小区域但大区域容易导致栈溢出。BFS广度优先使用队列像“涟漪扩散”。空间占用更可控是工程实践中的首选。应用场景除了油漆桶它还在以下场景大显身手图像处理图像分割、连通区域标记。一、图像渲染Leetcode链接有一幅以 m x n 的二维整数数组表示的图画 image 其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数 sr , sc 和 color 。你应该从像素 image[sr][sc] 开始对图像进行上色 填充 。为了完成 上色工作从初始像素开始将其颜色改为 color。对初始坐标的 上下左右四个方向上 相邻且与初始像素的原始颜色同色的像素点执行相同操作。通过检查与初始像素的原始颜色相同的相邻像素并修改其颜色来继续 重复 此过程。当 没有 其它原始颜色的相邻像素时 停止 操作。最后返回经过上色渲染 修改 后的图像 。解题思路经典FloodFill算法使用BFS解题将当前位置入队列并更改其颜色并将它四周上下左右符合条件的位置的坐标入队列。对这些位置做同样的处理代码实现及解析classSolution{//向量数组偏移量数组publicint[]dxnewint[]{0,0,1,-1};publicint[]dynewint[]{1,-1,0,0};publicint[][]floodFill(int[][]image,intsr,intsc,intcolor){intmimage.length,nimage[0].length;Queueint[]quenewLinkedList();//队列储存一个(x,y)坐标intprveColorimage[sr][sc];if(prveColorcolor)returnimage;//如果起始点就等于color那就不用再处理了que.offer(newint[]{sr,sc});//将起始点入队列image[sr][sc]color;//更改该位置的颜色while(!que.isEmpty()){int[]tmpque.poll();intatmp[0],btmp[1];//取出x、y坐标//使用偏移量数组更便捷地定位到该位置四周的坐标for(inti0;i4;i){intxadx[i],ybdy[i];//找到基准坐标四周上下左右的位置if(x0xmy0ynimage[x][y]prveColor){//判断该位置是否符合条件que.offer(newint[]{x,y});//入队列image[x][y]color;//更改其颜色}}}returnimage;}}总结复习解题思路和代码的整体实现框架代码中向量数组偏移量数组的使用将坐标(x,y)中x、y的位置偏移量枚举出分别放入到两个数组dx、dy中当开始对一个基准位置定位四周的坐标时就可以使用dx、dy更便捷的找到其上下左右的坐标二、岛屿数量Leetcode链接给你一个由 ‘1’陆地和 ‘0’水组成的的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外你可以假设该网格的四条边均被水包围。示例 输入grid [[‘1’,‘1’,‘1’,‘1’,‘0’],[‘1’,‘1’,‘0’,‘1’,‘0’],[‘1’,‘1’,‘0’,‘0’,‘0’],[‘0’,‘0’,‘0’,‘0’,‘0’]]输出1解题思路我们遍历二维网络找到一块陆地就计数一个岛屿但是实际上是与该陆地连接的陆地共同所组成的一个岛屿此时我们要将这些陆地全部标记为“已访问”使用额外的visited矩阵对原矩阵每个位置的访问状态进行记录下次遍历这些被标记的陆地就不能再计数了也可以将访问过的陆地直接修改为“0”,只是面试时可能不允许修改原矩阵那么这个算法就使用的是BFS。代码实现及解析classSolution{//偏移量数组int[]dxnewint[]{0,0,1,-1};int[]dynewint[]{1,-1,0,0};//visited矩阵记录原矩阵每个位置的访问状态boolean[][]visitednewboolean[300][300];//一次给够空间也可以在下面方法中new一个合适的空间intm,n;publicintnumIslands(char[][]grid){intret0;//记录岛屿数量mgrid.length;ngrid[0].length;//遍历二维网络的每个位置来查找岛屿for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1!visited[i][j]){//找到了陆地岛屿1但该陆地不能是被访问过的visited中不能被标记为trueret;bfs(grid,i,j);//与该陆地连接的陆地共同组成一个岛屿将这些陆地全部标记为“已访问”下次遇到就不再计数了}}}returnret;}publicvoidbfs(char[][]grid,inti,intj){//以grid[i][j]为起点的所有相连陆地全部标记“已访问”使用BFS算法Queueint[]quenewLinkedList();que.offer(newint[]{i,j});visited[i][j]true;while(!que.isEmpty()){int[]tmpque.poll();intatmp[0],btmp[1];for(intk0;k4;k){//用k别与i冲突了intxadx[k],ybdy[k];if(x0xmy0yngrid[x][y]1!visited[x][y]){que.offer(newint[]{x,y});visited[x][y]true;//该位置标记为“已访问”防止下次重复访问}}}}}总结复习解题思路三、被围绕的区域Leetcode链接给你一个 m x n 的矩阵 board 由若干字符 ‘X’ 和 ‘O’ 组成捕获 所有 被围绕的区域连接一个单元格与水平或垂直方向上相邻的单元格连接。区域连接所有 ‘O’ 的单元格来形成一个区域。围绕如果一个区域中的所有 ‘O’ 单元格都不在棋盘的边缘则该区域被包围。这样的区域 完全 被 ‘X’ 单元格包围。通过 原地 将输入矩阵中的所有 ‘O’ 替换为 ‘X’ 来 捕获被围绕的区域。你不需要返回任何值。解题思路在正常遍历矩阵去处理’O’区块时无法判断出该’O’区块是否接触了边缘所以我们可以先遍历矩阵的边缘去处理这些接触了矩阵的边缘的’O’区块使用BFS。先将这些边缘’O’区块更改为其他字符如’ * ‘再整体正常地使用for循环遍历一遍矩阵这时矩阵剩下的字符’O’就一定不会接触边缘可以将其更改为’X’而同时我们再把矩阵中的 ’ * ’ 字符改回’O’就行了。代码实现及解析classSolution{//偏移量数组int[]dxnewint[]{0,0,1,-1};int[]dynewint[]{1,-1,0,0};intm,n;publicvoidsolve(char[][]board){mboard.length;nboard[0].length;//1.遍历边缘位置处理这些接触边缘的O区块,将其区域更改为其他字符避免在后续正常处理时被改为Xfor(intj0;jn;j){//处理上下两行这两个边缘位置if(board[0][j]O){bfs(board,0,j);//将该区域更改为字符*}if(board[m-1][j]O){bfs(board,m-1,j);}}for(inti0;im;i){//处理左右两列这两个边缘位置if(board[i][0]O){bfs(board,i,0);}if(board[i][n-1]O){bfs(board,i,n-1);}}//2.再来遍历矩阵替换矩阵中目标字符for(inti0;im;i){for(intj0;jn;j){if(board[i][j]O){board[i][j]X;}elseif(board[i][j]*){//这样将处于边缘区块的O再变回来board[i][j]O;}}}}publicvoidbfs(char[][]board,inti,intj){Queueint[]quenewLinkedList();que.offer(newint[]{i,j});board[i][j]*;while(!que.isEmpty()){int[]tmpque.poll();intatmp[0],btmp[1];for(intk0;k4;k){intxadx[k],ybdy[k];if(x0xmy0ynboard[x][y]O){board[x][y]*;que.offer(newint[]{x,y});}}}}}总结复习解题思路“正难则反”思想正着来不行无法判断当前O区域是否接触边缘那就反着来先遍历边缘先处理这些边缘O区域
【优选算法】专题十五——BFS解决FloodFill算法
文章目录FloodFill算法简介一、图像渲染解题思路代码实现及解析总结二、岛屿数量解题思路代码实现及解析总结三、被围绕的区域解题思路代码实现及解析总结FloodFill算法简介FloodFill算法介绍AI总结FloodFill泛洪填充/漫水填充算法简单说就是从一个“种子点”出发像洪水蔓延一样查找到周围所有符合条件的位置共同形成这样的一个区块。它最直观的应用就是画图软件里的“油漆桶”工具。核心原理扩散与连通算法基于图遍历DFS或BFS实现核心逻辑如下起点选择一个起始像素点种子点。扩散检查该点的上下左右四邻域或有些时候也要求包括对角线八邻域的邻居。条件如果邻居的颜色与起点颜色相同且未被访问过就将其“感染”成新颜色并继续以该邻居为起点重复扩散。终止当所有符合条件的邻居都被处理完毕算法结束。两种实现方式DFS深度优先代码简洁像“一条路走到黑”。适合小区域但大区域容易导致栈溢出。BFS广度优先使用队列像“涟漪扩散”。空间占用更可控是工程实践中的首选。应用场景除了油漆桶它还在以下场景大显身手图像处理图像分割、连通区域标记。一、图像渲染Leetcode链接有一幅以 m x n 的二维整数数组表示的图画 image 其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数 sr , sc 和 color 。你应该从像素 image[sr][sc] 开始对图像进行上色 填充 。为了完成 上色工作从初始像素开始将其颜色改为 color。对初始坐标的 上下左右四个方向上 相邻且与初始像素的原始颜色同色的像素点执行相同操作。通过检查与初始像素的原始颜色相同的相邻像素并修改其颜色来继续 重复 此过程。当 没有 其它原始颜色的相邻像素时 停止 操作。最后返回经过上色渲染 修改 后的图像 。解题思路经典FloodFill算法使用BFS解题将当前位置入队列并更改其颜色并将它四周上下左右符合条件的位置的坐标入队列。对这些位置做同样的处理代码实现及解析classSolution{//向量数组偏移量数组publicint[]dxnewint[]{0,0,1,-1};publicint[]dynewint[]{1,-1,0,0};publicint[][]floodFill(int[][]image,intsr,intsc,intcolor){intmimage.length,nimage[0].length;Queueint[]quenewLinkedList();//队列储存一个(x,y)坐标intprveColorimage[sr][sc];if(prveColorcolor)returnimage;//如果起始点就等于color那就不用再处理了que.offer(newint[]{sr,sc});//将起始点入队列image[sr][sc]color;//更改该位置的颜色while(!que.isEmpty()){int[]tmpque.poll();intatmp[0],btmp[1];//取出x、y坐标//使用偏移量数组更便捷地定位到该位置四周的坐标for(inti0;i4;i){intxadx[i],ybdy[i];//找到基准坐标四周上下左右的位置if(x0xmy0ynimage[x][y]prveColor){//判断该位置是否符合条件que.offer(newint[]{x,y});//入队列image[x][y]color;//更改其颜色}}}returnimage;}}总结复习解题思路和代码的整体实现框架代码中向量数组偏移量数组的使用将坐标(x,y)中x、y的位置偏移量枚举出分别放入到两个数组dx、dy中当开始对一个基准位置定位四周的坐标时就可以使用dx、dy更便捷的找到其上下左右的坐标二、岛屿数量Leetcode链接给你一个由 ‘1’陆地和 ‘0’水组成的的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外你可以假设该网格的四条边均被水包围。示例 输入grid [[‘1’,‘1’,‘1’,‘1’,‘0’],[‘1’,‘1’,‘0’,‘1’,‘0’],[‘1’,‘1’,‘0’,‘0’,‘0’],[‘0’,‘0’,‘0’,‘0’,‘0’]]输出1解题思路我们遍历二维网络找到一块陆地就计数一个岛屿但是实际上是与该陆地连接的陆地共同所组成的一个岛屿此时我们要将这些陆地全部标记为“已访问”使用额外的visited矩阵对原矩阵每个位置的访问状态进行记录下次遍历这些被标记的陆地就不能再计数了也可以将访问过的陆地直接修改为“0”,只是面试时可能不允许修改原矩阵那么这个算法就使用的是BFS。代码实现及解析classSolution{//偏移量数组int[]dxnewint[]{0,0,1,-1};int[]dynewint[]{1,-1,0,0};//visited矩阵记录原矩阵每个位置的访问状态boolean[][]visitednewboolean[300][300];//一次给够空间也可以在下面方法中new一个合适的空间intm,n;publicintnumIslands(char[][]grid){intret0;//记录岛屿数量mgrid.length;ngrid[0].length;//遍历二维网络的每个位置来查找岛屿for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1!visited[i][j]){//找到了陆地岛屿1但该陆地不能是被访问过的visited中不能被标记为trueret;bfs(grid,i,j);//与该陆地连接的陆地共同组成一个岛屿将这些陆地全部标记为“已访问”下次遇到就不再计数了}}}returnret;}publicvoidbfs(char[][]grid,inti,intj){//以grid[i][j]为起点的所有相连陆地全部标记“已访问”使用BFS算法Queueint[]quenewLinkedList();que.offer(newint[]{i,j});visited[i][j]true;while(!que.isEmpty()){int[]tmpque.poll();intatmp[0],btmp[1];for(intk0;k4;k){//用k别与i冲突了intxadx[k],ybdy[k];if(x0xmy0yngrid[x][y]1!visited[x][y]){que.offer(newint[]{x,y});visited[x][y]true;//该位置标记为“已访问”防止下次重复访问}}}}}总结复习解题思路三、被围绕的区域Leetcode链接给你一个 m x n 的矩阵 board 由若干字符 ‘X’ 和 ‘O’ 组成捕获 所有 被围绕的区域连接一个单元格与水平或垂直方向上相邻的单元格连接。区域连接所有 ‘O’ 的单元格来形成一个区域。围绕如果一个区域中的所有 ‘O’ 单元格都不在棋盘的边缘则该区域被包围。这样的区域 完全 被 ‘X’ 单元格包围。通过 原地 将输入矩阵中的所有 ‘O’ 替换为 ‘X’ 来 捕获被围绕的区域。你不需要返回任何值。解题思路在正常遍历矩阵去处理’O’区块时无法判断出该’O’区块是否接触了边缘所以我们可以先遍历矩阵的边缘去处理这些接触了矩阵的边缘的’O’区块使用BFS。先将这些边缘’O’区块更改为其他字符如’ * ‘再整体正常地使用for循环遍历一遍矩阵这时矩阵剩下的字符’O’就一定不会接触边缘可以将其更改为’X’而同时我们再把矩阵中的 ’ * ’ 字符改回’O’就行了。代码实现及解析classSolution{//偏移量数组int[]dxnewint[]{0,0,1,-1};int[]dynewint[]{1,-1,0,0};intm,n;publicvoidsolve(char[][]board){mboard.length;nboard[0].length;//1.遍历边缘位置处理这些接触边缘的O区块,将其区域更改为其他字符避免在后续正常处理时被改为Xfor(intj0;jn;j){//处理上下两行这两个边缘位置if(board[0][j]O){bfs(board,0,j);//将该区域更改为字符*}if(board[m-1][j]O){bfs(board,m-1,j);}}for(inti0;im;i){//处理左右两列这两个边缘位置if(board[i][0]O){bfs(board,i,0);}if(board[i][n-1]O){bfs(board,i,n-1);}}//2.再来遍历矩阵替换矩阵中目标字符for(inti0;im;i){for(intj0;jn;j){if(board[i][j]O){board[i][j]X;}elseif(board[i][j]*){//这样将处于边缘区块的O再变回来board[i][j]O;}}}}publicvoidbfs(char[][]board,inti,intj){Queueint[]quenewLinkedList();que.offer(newint[]{i,j});board[i][j]*;while(!que.isEmpty()){int[]tmpque.poll();intatmp[0],btmp[1];for(intk0;k4;k){intxadx[k],ybdy[k];if(x0xmy0ynboard[x][y]O){board[x][y]*;que.offer(newint[]{x,y});}}}}}总结复习解题思路“正难则反”思想正着来不行无法判断当前O区域是否接触边缘那就反着来先遍历边缘先处理这些边缘O区域
