企业官网建设流程全解析

基础建设审计网站,桂林北站停车场收费标准,免费收录平台,阿里指数数据分析平台官网827. 最大人工岛 问题描述 给你一个大小为 n x n 的二进制矩阵 grid#xff0c;其中 0 表示海洋#xff0c;1 表示陆地。 你可以将 恰好一个 海洋格子#xff08;即 0#xff09;变为陆地#xff08;即 1#xff09;。 返回执行此操作后#xff0c;矩阵中 最大岛屿面积。…827. 最大人工岛问题描述给你一个大小为n x n的二进制矩阵grid其中0表示海洋1表示陆地。你可以将恰好一个海洋格子即0变为陆地即1。返回执行此操作后矩阵中最大岛屿面积。岛屿是由 4 个方向上相连的1形成的。示例输入:grid[[1,0],[0,1]]输出:3解释:将 grid[0][1]变为1可形成面积为3的岛屿。输入:grid[[1,1],[1,0]]输出:4解释:将 grid[1][0]变为1整个矩阵变成一个面积为4的岛屿。输入:grid[[1,1],[1,1]]输出:4解释:矩阵中已经没有海洋格子最大岛屿面积为4。算法思路岛屿编号标记遍历所有陆地计算每个独立岛屿的面积使用 DFS/BFS 遍历每个未访问的陆地格子为每个岛屿分配唯一的编号从 2 开始避免与原始的 0、1 冲突记录每个编号对应的岛屿面积遍历所有海洋格子模拟填海操作对于每个海洋格子 (0)检查其四个方向相邻的岛屿使用 Set 去重避免重复计算同一个岛屿计算填海后可能形成的最大岛屿面积1 所有相邻不同岛屿面积之和边界情况处理如果矩阵中全是陆地直接返回总面积如果矩阵中全是海洋返回 1填一个格子代码实现classSolution{// 方向数组上下左右四个方向privatestaticfinalint[][]DIRECTIONS{{-1,0},{1,0},{0,-1},{0,1}};/** * 计算将一个海洋格子变为陆地后的最大岛屿面积 * * param grid n x n 的二进制矩阵0表示海洋1表示陆地 * return 最大岛屿面积 */publicintlargestIsland(int[][]grid){intngrid.length;// 岛屿编号从2开始避免与原始的0、1冲突intislandId2;// 记录每个岛屿编号对应的面积MapInteger,IntegerislandAreanewHashMap();// 遍历所有格子识别并标记所有岛屿for(inti0;in;i){for(intj0;jn;j){// 如果当前格子是陆地值为1开始DFS计算岛屿面积if(grid[i][j]1){intareadfs(grid,i,j,islandId);islandArea.put(islandId,area);islandId;// 为下一个岛屿准备新的编号}}}// 初始化结果为当前最大岛屿面积不进行填海操作的情况intmaxArea0;for(intarea:islandArea.values()){maxAreaMath.max(maxArea,area);}// 遍历所有海洋格子模拟填海操作for(inti0;in;i){for(intj0;jn;j){// 只处理海洋格子值为0if(grid[i][j]0){// 使用Set记录相邻的不同岛屿编号避免重复计算SetIntegerneighborIslandsnewHashSet();// 检查四个方向的相邻格子for(int[]dir:DIRECTIONS){intniidir[0];intnjjdir[1];// 检查边界条件if(ni0ninnj0njn){// 如果相邻格子是陆地编号2加入Setif(grid[ni][nj]2){neighborIslands.add(grid[ni][nj]);}}}// 计算填海后的总面积1新填的格子 所有相邻岛屿面积之和inttotalArea1;for(intid:neighborIslands){totalAreaislandArea.get(id);}maxAreaMath.max(maxArea,totalArea);}}}returnmaxArea;}/** * 深度优先搜索计算岛屿面积并标记岛屿编号 * * param grid 网格矩阵 * param row 当前行坐标 * param col 当前列坐标 * param islandId 当前岛屿的编号 * return 岛屿的面积 */privateintdfs(int[][]grid,introw,intcol,intislandId){intngrid.length;// 边界检查超出边界或不是陆地原始值为1if(row0||rown||col0||coln||grid[row][col]!1){return0;}// 标记当前格子为当前岛屿编号grid[row][col]islandId;// 初始化面积为1当前格子intarea1;// 递归遍历四个方向的相邻格子for(int[]dir:DIRECTIONS){areadfs(grid,rowdir[0],coldir[1],islandId);}returnarea;}}算法分析时间复杂度O(n²)每个格子最多被访问一次进行DFS总时间复杂度 O(n²)遍历所有海洋格子每个格子检查4个邻居总时间复杂度 O(n²)空间复杂度O(n²)岛屿面积映射表最多存储 O(n²) 个岛屿信息DFS递归栈深度最坏情况下为 O(n²)Set临时存储最多4个相邻岛屿编号空间为 O(1)算法过程输入grid [[1,0],[0,1]]岛屿识别和标记格子(0,0)值为1开始DFS标记为岛屿2面积1grid变为[[2,0],[0,1]]格子(1,1)值为1开始DFS标记为岛屿3面积1grid变为[[2,0],[0,3]]岛屿面积映射{2: 1, 3: 1}模拟填海格子(0,1)海洋格子上无下grid[1][1]3左grid[0][0]2右无相邻岛屿{2, 3}总面积1 1 1 3格子(1,0)海洋格子上grid[0][0]2下无左无右grid[1][1]3相邻岛屿{2, 3}总面积1 1 1 3结果初始最大面积1填海后最大面积3返回结果3测试用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1对角线岛屿int[][]grid1{{1,0},{0,1}};System.out.println(Test 1: solution.largestIsland(grid1));// 3// 测试用例2三格陆地一格海洋int[][]grid2{{1,1},{1,0}};System.out.println(Test 2: solution.largestIsland(grid2));// 4// 测试用例3全陆地int[][]grid3{{1,1},{1,1}};System.out.println(Test 3: solution.largestIsland(grid3));// 4// 测试用例4全海洋int[][]grid4{{0,0},{0,0}};System.out.println(Test 4: solution.largestIsland(grid4));// 1// 测试用例5复杂情况int[][]grid5{{1,0,1},{0,0,0},{1,0,1}};System.out.println(Test 5: solution.largestIsland(grid5));// 5// 测试用例6单格int[][]grid6{{0}};System.out.println(Test 6: solution.largestIsland(grid6));// 1int[][]grid7{{1}};System.out.println(Test 7: solution.largestIsland(grid7));// 1// 测试用例8大岛屿int[][]grid8{{0,0,0,0,0,0,0},{0,1,1,1,1,0,0},{0,1,0,0,1,0,0},{0,1,0,0,1,0,0},{0,1,1,1,1,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0}};System.out.println(Test 8: solution.largestIsland(grid8));// 17}关键点岛屿编号使用 ≥2 的编号标记不同岛屿避免与原始数据冲突编号本身作为岛屿的唯一标识符去重处理使用 Set 存储相邻岛屿编号防止同一岛屿被重复计算边界情况全陆地直接返回总面积全海洋返回1填一个格子的最小面积单格矩阵根据值返回1常见问题为什么岛屿编号从2开始原始矩阵中只有0海洋和1陆地使用≥2的编号可以清楚区分哪些是原始陆地哪些是已标记的岛屿。为什么需要Set去重岛屿形状如U形海洋格子可能被同一个岛屿从多个方向包围如果不使用Set去重会重复计算同一个岛屿的面积。