沧州做网站哪家公司好,北京本地服务信息网,海南澄迈网站建设,县局网站建设招标目录
引入#xff1a;leetcode695.岛屿的最大面积
分析与转换
一维二维转换
四联通
完整代码解答#xff1a;
1#xff09;显示的创建图解决问题的代码
2#xff09;不显示的创建图解决此问题的代码
floodfill算法
定义 引入#xff1a;leetcode695.岛屿的最大面…目录
引入leetcode695.岛屿的最大面积
分析与转换
一维二维转换
四联通
完整代码解答
1显示的创建图解决问题的代码
2不显示的创建图解决此问题的代码
floodfill算法
定义 引入leetcode695.岛屿的最大面积 分析与转换
在题目中0是海水1是陆地。在我们自己设定的图中假设蓝色是海水红色是陆地。且每一个小格子都是一个顶点若某个红色顶点上下左右方向有另外的红色顶点与它相邻则在它俩中间连接一条边证明其一同构成了一个岛屿也就是同属于一个连通分量。这样我们就把这道题转换成了一个图论的问题。我们要求的问题也就转换成了找出包含顶点最多的连通分量顶点个数也就是面积的最大值。 一维二维转换
我们还可以通过数学公式将二维和一维相互转换。注意一维是从0开始计数 二维是从1开始计数。 四联通
我们需要搜索一个红色顶点的上下左右的顶点是否还是陆地那么如何搜索呢这就涉及到了四联通的概念。我们可以设立一个二维数组里面的四个元素代表了相较于本顶点而言它的行列坐标的位移也就是表示它的上下左右各移动一个单位的四个坐标。值得注意的是我们现在的坐标系不是我们熟知的数学坐标系而是我们计算机一般使用的屏幕坐标系我们可以理解成二维数组索引所在的坐标系。 d循环四次代表上下左右四个方向。 完整代码解答
1显示的创建图解决问题的代码
import java.util.HashSet;class Solution {private int[][] dirs {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};private int R, C;//行数列数private int[][] grid;private HashSetInteger[] G;//图的邻接表的表示private boolean[] visited;public int maxAreaOfIsland(int[][] grid){if(grid null) return 0;R grid.length;if(R 0) return 0;C grid[0].length;if(C 0) return 0;this.grid grid;G constructGraph();//进行建图操作int res 0;visited new boolean[G.length];for(int v 0; v G.length; v ){int x v / C, y v % C;if(grid[x][y] 1 !visited[v])//如果v没被遍历过就是证明找到了一个新的岛屿即一个新的连通分量。res Math.max(res, dfs(v));}return res;}private int dfs(int v){visited[v] true;int res 1;//1是这是深度优先遍历v这个顶点for(int w: G[v])if(!visited[w])res dfs(w);return res;}private HashSetInteger[] constructGraph(){HashSetInteger[] g new HashSet[R * C];//开辟空间for(int i 0; i g.length; i )g[i] new HashSet();for(int v 0; v g.length; v ){int x v / C, y v % C;//转换成二维坐标if(grid[x][y] 1){//只有它本身是陆地才去判断它四周是否有其他陆地与之相连for(int d 0; d 4; d ){int nextx x dirs[d][0];int nexty y dirs[d][1];if(inArea(nextx, nexty) grid[nextx][nexty] 1) {//判断nextx和nexty是否合法是否在网格范围中int next nextx * C nexty;//转为一维索引g[v].add(next);//添加一条边g[next].add(v);}}}}return g;}private boolean inArea(int x, int y){return x 0 x R y 0 y C;}public static void main(String[] args){int[][] grid {{0, 1}};System.out.println((new Solution()).maxAreaOfIsland(grid));}
}
2不显示的创建图解决此问题的代码
class Solution {private int[][] dirs {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};private int R, C;private int[][] grid;private boolean[][] visited;public int maxAreaOfIsland(int[][] grid){if(grid null) return 0;R grid.length;if(R 0) return 0;C grid[0].length;if(C 0) return 0;this.grid grid;visited new boolean[R][C];int res 0;for(int i 0; i R; i )//二重循环遍历每一个顶点for(int j 0; j C; j )if(grid[i][j] 1 !visited[i][j])res Math.max(res, dfs(i, j));return res;}private int dfs(int x, int y){visited[x][y] true;int res 1;for(int d 0; d 4; d ){int nextx x dirs[d][0], nexty y dirs[d][1];if(inArea(nextx, nexty) grid[nextx][nexty] 1 !visited[nextx][nexty])res dfs(nextx, nexty);}return res;}private boolean inArea(int x, int y){return x 0 x R y 0 y C;}
}
floodfill算法
定义
floodfill算法是一种图像处理算法用于填充连通区域。该算法从一个起始点开始将所有与该点相邻且颜色相同的像素点都标记为同一区域并继续递归处理该区域的相邻像素点直到所有相邻像素点都被标记为该区域。该算法通常用于图像处理、计算机图形学等领域中的填充操作例如对图像中的某个区域进行颜色填充、图形的边界检测等。
