摘要:两个循环遍历整个矩阵,出现则将其周围相邻的全部标记为,用子函数递归标记。注意里每次递归都要判断边界。写一个的,写熟练。
Number of Islands Problem
Given a boolean/char 2D matrix, find the number of islands.
0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.
ExampleGiven graph:
[ [1, 1, 0, 0, 0], [0, 1, 0, 0, 1], [0, 0, 0, 1, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 1] ]
return 3.
Note两个for循环遍历整个矩阵,出现"1"则count++将其周围相邻的"1"全部标记为"0",用子函数mark()递归标记。
Solution DFS注意mark里每次递归都要判断边界。
public class Solution { public int numIslands(char[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) return 0; 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") { count++; mark(grid, i, j); } } } return count; } public void mark(char[][] grid, int i, int j) { if (grid[i][j] == "1" && i >= 0 && i < grid.length && j >= 0 && j < grid[0].length) { grid[i][j] = "0"; if (i-1 >= 0) mark(grid, i-1, j); if (i+1 < grid.length) mark(grid, i+1, j); if (j-1 >= 0) mark(grid, i, j-1); if (j+1 < grid[0].length) mark(grid, i, j+1); } } }Union Find
写一个Union Find的class,写熟练。
public class Solution { public int numIslands(char[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) return 0; int m = grid.length, n = grid[0].length; UnionFind uf = new UnionFind(m, n, grid); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == "0") continue; int x = i*n+j; int y; if (i < m-1 && grid[i+1][j] == "1") { y = x+n; uf.union(x, y); } if (j < n-1 && grid[i][j+1] == "1") { y = x+1; uf.union(x, y); } } } return uf.count; } class UnionFind { public int count; public int[] parents; public UnionFind(int m, int n, char[][] grid) { for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == "1") count++; } } parents = new int[m*n]; for (int i = 0; i < m*n; i++) parents[i] = i; } public int find(int i) { if (i == parents[i]) return i; parents[i] = find(parents[i]); return parents[i]; } public void union(int i, int j) { int pi = find(i); int pj = find(j); if (pi == pj) return; else parents[pi] = pj; count--; } } }Number of Islands II
search another post
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/65504.html
Problem Given a non-empty 2D array grid of 0s and 1s, an island is a group of 1s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are s...
摘要:同时我们每找到一个,就将其标为,这样就能把整个岛屿变成。我们只要记录对矩阵遍历时能进入多少次搜索,就代表有多少个岛屿。 Number of Islands 最新更新的思路,以及题II的解法请访问:https://yanjia.me/zh/2018/11/... Given a 2d grid map of 1s (land) and 0s (water), count the nu...
摘要:解题思路标零法对这个矩阵进行循环访问每一个点当这个点等于,岛屿数量,与其同时用算法访问周围的其他点,进行同样的操作且将访问过且等于的点标记为零。版本岛屿数量搜索右边搜索左边搜索下边搜索上边 Q: Number of Islands Given a 2d grid map of 1s (land) and 0s (water), count the number of islands. ...
Problem In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.) Now, we may change 0s to 1s so as to connect the two...
Problem Write an algorithm to determine if a number is happy.A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squar...
阅读 774·2019-08-30 14:05
阅读 1679·2019-08-30 11:08
阅读 3186·2019-08-29 15:41
阅读 3573·2019-08-23 18:31
阅读 1482·2019-08-23 18:29
阅读 520·2019-08-23 14:51
阅读 2078·2019-08-23 13:53
阅读 2103·2019-08-23 13:02