cpa广告联盟网站建设教程,付公司网站建设费用会计分录,网站建设招标评分表,绍兴做网站的公司看完题目我还感觉这道题目有点难#xff0c;没想到20分钟不到就完全靠自己给写出来了。我就是按照自己的想法来#xff0c;我用一个等大的visit数组来表示grid数组中的这个元素是否被访问过#xff08;是否已经被判断了是不是岛屿#xff09;。
先用一个大的循环对grid数组… 看完题目我还感觉这道题目有点难没想到20分钟不到就完全靠自己给写出来了。我就是按照自己的想法来我用一个等大的visit数组来表示grid数组中的这个元素是否被访问过是否已经被判断了是不是岛屿。
先用一个大的循环对grid数组遍历去判断里面的元素grid[i][j]是不是一个岛屿。如果它是一个岛屿的话就要把岛屿数量1并且要把和grid[i][j]相连的陆地全部算在这个岛屿中所以要把和它相连的陆地的visit设置成true下次遍历到这个点就直接跳过。
那么如何把grid[i][j]的相连的陆地的visit全部置为true呢利用递归就可以了用setVisit(char[][] grid, boolean[][] visit, int i, int j),grid数组和visit数组就是全局的grid数组和visit数组(如果把这两个数组定义在类里面就不用传这两个参了)ij就是要进行置true的元素下标先把visit[i][j]置为true然后再递归调用setVist()方法把visit[i][j]的上下左右4个方向的visit置为true当然不是直接置true要进行判断假设相邻位置是m,n,首先必须要m,n大于等于0小于length其次grid[m][n]要等于1并且visit[m][n]要等于false然后直接递归调用setVisit方法把visit[m][n]置为true这样进行递归就会把与grid[i][j]相连的所有陆地都visit了
那么如何判断grid[i][j]是不是岛屿呢其实很简单如果grid[i][j]是1并且它没有被visit过他就是岛屿因为它如果没有被visit过只有两种可能第一种是没有任何陆地和它相连所以它没有被visit第二种是它是它所在的岛屿第一个被发现的陆地以上两种情况都可以把它判定为岛屿给岛屿属灵加一最后返回岛屿数量result即可以下是我的代码
class Solution {public int numIslands(char[][] grid) {int m grid.length;int n grid[0].length;boolean[][] visit new boolean [m][n];int result0;for(int i 0;im;i){for(int j0;jn;j){if(grid[i][j] 1 !visit[i][j]){result;setVisit(grid, visit, i, j);}}}return result;}public void setVisit(char[][] grid, boolean[][] visit, int i, int j){visit[i][j] true;if(i1visit.length grid[i1][j] 1 visit[i1][j] false)setVisit(grid, visit, i1, j);if(j1visit[0].length grid[i][j1] 1 visit[i][j1] false)setVisit(grid, visit, i, j1);if(i-10 grid[i-1][j] 1 visit[i-1][j] false)setVisit(grid, visit, i-1, j);if(j-10 grid[i][j-1] 1 visit[i][j-1] false)setVisit(grid, visit, i, j-1);}
}
看看官方题解的做法吧
题解的方法一用的是深度优先搜索和我的方法是一样的只不过它没有用标记数组visit而是直接再grid数组上把相连的陆地由1改成了0以下是题解方法一的代码
class Solution {void dfs(char[][] grid, int r, int c) {int nr grid.length;int nc grid[0].length;if (r 0 || c 0 || r nr || c nc || grid[r][c] 0) {return;}grid[r][c] 0;dfs(grid, r - 1, c);dfs(grid, r 1, c);dfs(grid, r, c - 1);dfs(grid, r, c 1);}public int numIslands(char[][] grid) {if (grid null || grid.length 0) {return 0;}int nr grid.length;int nc grid[0].length;int num_islands 0;for (int r 0; r nr; r) {for (int c 0; c nc; c) {if (grid[r][c] 1) {num_islands;dfs(grid, r, c);}}}return num_islands;}
}
题解的方法二用的是广度优先搜索如果gird[i][j]等于1就把它放到一个队列里面然后不断的从队列中取出元素把grid置为0每取出一个就把这个元素的上下左右放进队列(当然需要这些元素的grid为1)值得注意的是它放进队列的是这个元素在数组中的序号也就是行号*每行的个数列号所以这个队列中的这个序号被取出来后会通过模运算算出行号和列号方便找上下左右4个元素。以下是题解方法二的代码
class Solution {public int numIslands(char[][] grid) {if (grid null || grid.length 0) {return 0;}int nr grid.length;int nc grid[0].length;int num_islands 0;for (int r 0; r nr; r) {for (int c 0; c nc; c) {if (grid[r][c] 1) {num_islands;grid[r][c] 0;QueueInteger neighbors new LinkedList();neighbors.add(r * nc c);while (!neighbors.isEmpty()) {int id neighbors.remove();int row id / nc;int col id % nc;if (row - 1 0 grid[row-1][col] 1) {neighbors.add((row-1) * nc col);grid[row-1][col] 0;}if (row 1 nr grid[row1][col] 1) {neighbors.add((row1) * nc col);grid[row1][col] 0;}if (col - 1 0 grid[row][col-1] 1) {neighbors.add(row * nc col-1);grid[row][col-1] 0;}if (col 1 nc grid[row][col1] 1) {neighbors.add(row * nc col1);grid[row][col1] 0;}}}}}return num_islands;}
}
题解的方法三采用的是并查集的方法这个方法有点复杂先上代码
class Solution {class UnionFind {int count;int[] parent;int[] rank;public UnionFind(char[][] grid) {count 0;int m grid.length;int n grid[0].length;parent new int[m * n];rank new int[m * n];for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {parent[i * n j] i * n j;count;}rank[i * n j] 0;}}}public int find(int i) {if (parent[i] ! i) parent[i] find(parent[i]);return parent[i];}public void union(int x, int y) {int rootx find(x);int rooty find(y);if (rootx ! rooty) {if (rank[rootx] rank[rooty]) {parent[rooty] rootx;} else if (rank[rootx] rank[rooty]) {parent[rootx] rooty;} else {parent[rooty] rootx;rank[rootx] 1;}--count;}}public int getCount() {return count;}}public int numIslands(char[][] grid) {if (grid null || grid.length 0) {return 0;}int nr grid.length;int nc grid[0].length;int num_islands 0;UnionFind uf new UnionFind(grid);for (int r 0; r nr; r) {for (int c 0; c nc; c) {if (grid[r][c] 1) {grid[r][c] 0;if (r - 1 0 grid[r-1][c] 1) {uf.union(r * nc c, (r-1) * nc c);}if (r 1 nr grid[r1][c] 1) {uf.union(r * nc c, (r1) * nc c);}if (c - 1 0 grid[r][c-1] 1) {uf.union(r * nc c, r * nc c - 1);}if (c 1 nc grid[r][c1] 1) {uf.union(r * nc c, r * nc c 1);}}}}return uf.getCount();}
}它是采用了一个内部类UnionFind这个类有一个count属性表示岛屿的个数parent[]数组大小就是giad的数组的大小grid的每个元素都在parent中有对应的位置也是采用序号的方式(行号*每行的个数列号),比如grid[i][j]在parent中对应的下标就是parent[i*每行个数j],它表示grid[i][j]有那个序号的元素连接而找到通过
public int find(int i) {if (parent[i] ! i) parent[i] find(parent[i]);return parent[i];}
就可以找到序号i元素的最大祖先然后通过
public void union(int x, int y) {int rootx find(x);int rooty find(y);if (rootx ! rooty) {if (rank[rootx] rank[rooty]) {parent[rooty] rootx;} else if (rank[rootx] rank[rooty]) {parent[rootx] rooty;} else {parent[rooty] rootx;rank[rootx] 1;}--count;}}
rank是一个和gird等大的数组它表示rank[序号]所在树的深度
假设grid[i][j]的序号是x他的相邻元素的序号是y,通过find方法分别找到x和y的根节点rootx和rooty如果rootx和rooty不相等说明他们之前在两颗独立的树上因为x和y是相邻的所以他们其实在同一颗树上所以他们的树的深度是两颗树深度最大的一个大的那个root是小的root的parent如果两颗树的深度相等那么可以把其中一个root挂在另一个root的叶子上那么树的深度就1了因为他们两个树之前是独立的但其实他们是一起的也就是说之前count多加了一次所以count要-1
只要在numIslands中把grid的每个节点遍历一次最后返回count即可。
