企业官网建设流程全解析

医疗类网站备案,网站百度收录突然消失了,网站版式设计说明,旅游网站设计思路934. 最短的桥 问题描述 给你一个大小为 n x n 的二进制矩阵 grid#xff0c;其中 1 表示陆地#xff0c;0 表示水域。 保证恰好有两座岛#xff08;即两个由 1 组成的连通分量#xff09;。 你可以将 0 变成 1 来建造桥梁#xff0c;使得两座岛连接起来。 返回需要建…934. 最短的桥问题描述给你一个大小为n x n的二进制矩阵grid其中1表示陆地0表示水域。保证恰好有两座岛即两个由1组成的连通分量。你可以将0变成1来建造桥梁使得两座岛连接起来。返回需要建造的最短桥梁的长度即最少需要翻转多少个0。注意在二维网格中连通性是指上下左右四个方向。示例输入: grid [[0,1],[1,0]] 输出: 1 解释: 翻转 grid[0][0] 或 grid[1][1] 即可连接两座岛。 输入: grid [[0,1,0],[0,0,0],[0,0,1]] 输出: 2 解释: 翻转 grid[0][2] 和 grid[1][2]或者翻转 grid[1][0] 和 grid[2][0]。 输入: grid [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]] 输出: 1 解释: 中间的0只需要翻转一个即可连接。算法思路多源BFS步骤找到第一座岛使用DFS或BFS遍历找到其中一个连通分量岛标记第一座岛将第一座岛的所有位置标记为特殊值如2并将所有边界位置加入BFS队列多源BFS扩展从第一座岛的所有位置同时开始BFS寻找第二座岛返回距离当BFS第一次遇到值为1的位置时当前的BFS层数就是最短桥梁长度代码实现方法一DFS 多源BFSclassSolution{privatestaticfinalint[][]DIRECTIONS{{-1,0},{1,0},{0,-1},{0,1}};/** * 找到连接两座岛的最短桥梁长度 * * param grid n x n 的二进制矩阵 * return 最短桥梁长度 */publicintshortestBridge(int[][]grid){intngrid.length;booleanfoundFirstIslandfalse;Queueint[]queuenewLinkedList();// 1: 找到第一座岛并标记for(inti0;in!foundFirstIsland;i){for(intj0;jn!foundFirstIsland;j){if(grid[i][j]1){// 使用DFS标记第一座岛为2并将所有位置加入BFS队列dfsMarkIsland(grid,i,j,queue);foundFirstIslandtrue;}}}// 2: 多源BFS寻找第二座岛intbridgeLength0;while(!queue.isEmpty()){intsizequeue.size();// 处理当前BFS层的所有节点for(inti0;isize;i){int[]currentqueue.poll();introwcurrent[0];intcolcurrent[1];// 探索四个方向for(int[]dir:DIRECTIONS){intnewRowrowdir[0];intnewColcoldir[1];// 边界检查if(newRow0newRownnewCol0newColn){if(grid[newRow][newCol]1){// 找到第二座岛返回当前桥梁长度returnbridgeLength;}elseif(grid[newRow][newCol]0){// 水域标记为已访问并加入队列grid[newRow][newCol]2;queue.offer(newint[]{newRow,newCol});}// 如果是2第一座岛跳过}}}bridgeLength;}return-1;//}/** * DFS标记第一座岛为2并将所有位置加入BFS队列 */privatevoiddfsMarkIsland(int[][]grid,introw,intcol,Queueint[]queue){intngrid.length;// 边界检查和访问检查if(row0||rown||col0||coln||grid[row][col]!1){return;}// 标记为第一座岛2并加入BFS队列grid[row][col]2;queue.offer(newint[]{row,col});// 递归标记相邻的陆地for(int[]dir:DIRECTIONS){dfsMarkIsland(grid,rowdir[0],coldir[1],queue);}}}方法二BFS 多源BFSclassSolution{privatestaticfinalint[][]DIRECTIONS{{-1,0},{1,0},{0,-1},{0,1}};publicintshortestBridge(int[][]grid){intngrid.length;Queueint[]queuenewLinkedList();booleanfoundFirstIslandfalse;// 使用BFS找到并标记第一座岛for(inti0;in!foundFirstIsland;i){for(intj0;jn!foundFirstIsland;j){if(grid[i][j]1){bfsMarkIsland(grid,i,j,queue);foundFirstIslandtrue;}}}// 多源BFSreturnmultiSourceBFS(grid,queue);}privatevoidbfsMarkIsland(int[][]grid,intstartRow,intstartCol,Queueint[]queue){intngrid.length;Queueint[]islandQueuenewLinkedList();islandQueue.offer(newint[]{startRow,startCol});grid[startRow][startCol]2;queue.offer(newint[]{startRow,startCol});while(!islandQueue.isEmpty()){int[]currentislandQueue.poll();introwcurrent[0];intcolcurrent[1];for(int[]dir:DIRECTIONS){intnewRowrowdir[0];intnewColcoldir[1];if(newRow0newRownnewCol0newColngrid[newRow][newCol]1){grid[newRow][newCol]2;islandQueue.offer(newint[]{newRow,newCol});queue.offer(newint[]{newRow,newCol});}}}}privateintmultiSourceBFS(int[][]grid,Queueint[]queue){intngrid.length;intbridgeLength0;while(!queue.isEmpty()){intsizequeue.size();for(inti0;isize;i){int[]currentqueue.poll();introwcurrent[0];intcolcurrent[1];for(int[]dir:DIRECTIONS){intnewRowrowdir[0];intnewColcoldir[1];if(newRow0newRownnewCol0newColn){if(grid[newRow][newCol]1){returnbridgeLength;}elseif(grid[newRow][newCol]0){grid[newRow][newCol]2;queue.offer(newint[]{newRow,newCol});}}}}bridgeLength;}return-1;}}算法分析时间复杂度O(n²)DFS/BFS标记第一座岛O(n²)多源BFS扩展O(n²)空间复杂度O(n²)队列在最坏情况下可能存储O(n²)个元素递归DFS的栈深度最坏情况下也是O(n²)算法过程输入grid [[0,1],[1,0]]找到第一座岛在(0,1)找到第一个1DFS标记第一座岛只有(0,1)标记为2BFS队列[(0,1)]多源BFS层0队列[(0,1)]探索邻居(0,0)0→标记为2加入队列(1,1)0→标记为2加入队列(0,2)和(-1,1)越界层1队列[(0,0), (1,1)]从(1,1)探索(1,0)1→找到第二座岛返回桥梁长度 1输入grid [[0,1,0],[0,0,0],[0,0,1]]标记第一座岛(0,1)标记为2队列[(0,1)]BFS层0探索(0,0)0、(0,2)0、(1,1)0 → 队列[(0,0),(0,2),(1,1)]BFS层1从(0,2)探索(1,2)0从(1,1)探索(1,0)0、(1,2)0、(2,1)0 → 队列包含这些位置BFS层2从(1,2)探索(2,2)1 → 找到第二座岛返回2测试用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1最小情况int[][]grid1{{0,1},{1,0}};System.out.println(Test 1: solution.shortestBridge(grid1));// 1// 测试用例2标准示例int[][]grid2{{0,1,0},{0,0,0},{0,0,1}};System.out.println(Test 2: solution.shortestBridge(grid2));// 2// 测试用例3环形岛屿int[][]grid3{{1,1,1,1,1},{1,0,0,0,1},{1,0,1,0,1},{1,0,0,0,1},{1,1,1,1,1}};System.out.println(Test 3: solution.shortestBridge(grid3));// 1// 测试用例4大岛屿int[][]grid4{{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1},{0,0,0,1,1}};System.out.println(Test 4: solution.shortestBridge(grid4));// 3// 测试用例5相邻岛屿int[][]grid5{{1,0,1},{0,0,0},{0,0,0}};System.out.println(Test 5: solution.shortestBridge(grid5));// 1// 测试用例6单格岛屿int[][]grid6{{1,0,0},{0,0,0},{0,0,1}};System.out.println(Test 6: solution.shortestBridge(grid6));// 3// 测试用例7复杂形状int[][]grid7{{0,0,0,0,0,0},{0,1,1,0,0,0},{0,1,0,0,0,0},{0,0,0,0,1,0},{0,0,0,1,1,0},{0,0,0,0,0,0}};System.out.println(Test 7: solution.shortestBridge(grid7));// 2}关键点两阶段第一阶段识别并标记第一座岛第二阶段多源BFS寻找第二座岛多源BFS同时从第一座岛的所有位置开始搜索保证找到的路径是最短的BFS的层数直接对应桥梁长度标记使用2标记已访问的位置第一座岛和已探索的水域1表示第二座岛目标0表示未探索的水域边界处理网格边界检查访问状态检查避免重复访问常见问题为什么使用多源BFS而不是单源BFS多源BFS可以从第一座岛的所有边界同时扩展确保找到的路径是全局最短的单源BFS需要尝试每个起点效率低下