网站网站怎么做的杭州网站建设

网站网站怎么做的,杭州网站建设,网站建设公司宝安,沈阳网络优化公司哪家好力扣-真题-岛屿数量我的想法是 初始化一个 sum代表岛屿数量#xff0c; 没遍历到一个 1, sum sum 1 然后从这个位置开始 进行广度优先搜索 把所有相连的1 全部变成0 #xff08;原地修改#xff09;。 然后再继续向下遍历 。 就能得到所有岛屿数量了。public int numIslan…力扣-真题-岛屿数量我的想法是 初始化一个 sum代表岛屿数量没遍历到一个 1, sum sum 1然后从这个位置开始 进行广度优先搜索 把所有相连的1 全部变成0 原地修改。 然后再继续向下遍历 。就能得到所有岛屿数量了。publicintnumIslands(char[][]grid){intsum0;for(inti0;igrid.length;i){for(intj0;jgrid[0].length;j){if(grid[i][j]0)continue;sum;bfs(grid,i,j);}}returnsum;}publicvoidbfs(char[][]grid,inti,intj){//边界情况if(igrid.length||jgrid[0].length||i-1||j-1||grid[i][j]0)return;grid[i][j]0;//四个方向进行遍历bfs(grid,i,j1);bfs(grid,i1,j);bfs(grid,i-1,j);bfs(grid,i,j-1);}嗯 今天开始加一个环节复杂度分析首先空间复杂度 是 O(1) , 因为是原地修改 没有额外的存储空间浪费。然后时间复杂度计算咱们拆成几个部分 首先第一个部分 肯定就是 两层 for循环遍历总共需要遍历 数组的数量m × 单个数组的元素数量n 此即 时间复杂度 在这一部分是 O(m×n)第二部分 也就是最后的一部分就是BFS 遍历这一部分的分析 可以这样如果 这个 节点是grid[x][y] ‘0’ 啥也不用处理 O(1)如果 这个节点 是 grid[x][y] ‘1’ 那个 除了 grid[x][y]置为 ‘1’外主要就是找相邻的‘1’置为 ‘0’ 其实某种程度上来说 你把其他节点 的 ‘1’ 置为 ‘0’ 不就是帮其他节点做事吗 平摊下来 最多 每一个节点都把‘1’置为 ‘0’ 也就是 在遍历 m× n的时候 顺便加一步 ‘1’置为 ‘0’ 以及 如果是 ‘0’ 跳过的判断 这个时间复杂度 实际上是 O(1)当然啦 最坏的情况下 grid[0][0】开始 bfs 会直接遍历整个图 也就是m×n的复杂度。所以实际上 BFS的时间复杂度也是O(m×n)但是这两部分的时间复杂度是分开的互不影响总体的时间复杂度就是O(m×n m×n 2O(m×n)常数因子忽略 所以最终的时间复杂度就是O(m×n)