网站开发与应用论文公司注册网上申报流程

网站开发与应用论文,公司注册网上申报流程,四川省建设招标网站首页,网站免费模板思路#xff1a;#xff08;1#xff09;题目中每座岛屿只能由水平方向和竖直方向上相邻的陆地连接而成#xff0c;也就是说斜角度的连接不算。例如示例二#xff0c;是三个岛屿。#xff08;2#xff09;本题的思路是遇到一个没有遍历过的节点陆地#xff0c;计数器就…思路1题目中每座岛屿只能由水平方向和竖直方向上相邻的陆地连接而成也就是说斜角度的连接不算。例如示例二是三个岛屿。2本题的思路是遇到一个没有遍历过的节点陆地计数器就加1然后把该节点陆地所能遍历到的陆地都标记上。在遇到标记过的陆地节点和海洋节点的时候直接跳过这样计数器就是最终岛屿的数量。3把节点陆地所能遍历到的陆地都标记上就可以使用DFS、BFS或并查集。一、DFS1.目标是找到矩阵中“岛屿的数量”上下左右相连的1都被认为是连续岛屿。2.dfs方法设目前指针指向一个岛屿中的某一个点i,j寻找包括此点的岛屿边界。1从i,j向此点的上下左右i 1,j、i - 1,j、i,j 1、i、j - 1做深度搜索。2终止条件——i,j越过矩阵边界。——grid[i][j] 0表示此分支已越过岛屿边界。3搜索岛屿的同时执行grid[i][j] 0即将岛屿的所有节点删除以免之后重复搜索相同的岛屿。3.主循环遍历整个矩阵当遇到grid[i][j] 1的时候从此点开始做深度优先搜索dfs岛屿数count 1且在深度优先搜索中删除此岛屿。4.最终返回岛屿数count即可。附代码class Solution { 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){ //发现新岛屿 dfs(grid,i,j); //将整个岛屿标记为已访问(沉没整个岛屿) count; //岛屿数量 1 } } } return count; } private void dfs(char[][] grid,int i,int j){ //递归终止条件边界检查 遇到水/已访问的陆地 // ||操作具有短路特性只要前面的任何一个条件为true后面的条件就不会执行 //因此要先做边界检查当边界检查都通过后再判断grid[i][j] // 也有短路特性 if(i 0 || j 0 || i grid.length || j grid[0].length || grid[i][j] 0){ return; } //将当前陆地标记为已访问沉没岛屿改为‘0’ grid[i][j] 0; //向四个方向递归探索 dfs(grid,i 1,j); //下 dfs(grid,i,j 1); //右 dfs(grid,i - 1,j); //上 dfs(grid,i,j - 1); //左 } }二、BFS1.主循环和DFS类似不同点在于搜索某岛屿边界的方法不同。2.BFS方法1借用一个队列queue判断队列首部节点i,j是否未越界且为‘1’。——若是则置0删除岛屿节点并将此节点的上下左右节点i 1,j、i - 1,j、i,j 1、i,j - 1加入队列。——若不是则跳过此节点。2remove(pop)队列的首节点直到整个队列为空此时已经遍历完此岛屿。附代码class Solution { 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){ //发现新岛屿 bfs(grid, i, j); //将整个岛屿标记为已访问沉没整个岛屿 count; //岛屿计数 1 } } } return count; } private void bfs(char[][] grid, int i, int j){ LinkedListint[] queue new LinkedList(); //BFS队列 queue.add(new int[] { i, j }); //将起始点加入队列 while(!queue.isEmpty()){ int[] cur queue.remove(); //取出队首节点 i cur[0]; j cur[1]; //检查节点是否有效且是陆地 if(0 i i grid.length 0 j j grid[0].length grid[i][j] 1) { grid[i][j] 0; //标记为已访问改为水 //将四个方向的相邻节点加入到队列 queue.add(new int[] { i 1, j }); queue.add(new int[] { i - 1, j }); queue.add(new int[] { i, j 1 }); queue.add(new int[] { i, j - 1 }); } } } }