NumberOfIslandes [source code]
public class NumberOfIslandes {
static
/******************************************************************************/
class Solution {
static int[] dirs = {-1, 0, 1, 0, -1};
public int numIslands(char[][] grid) {
if (grid.length == 0 || grid[0].length == 0)
return 0;
int R = grid.length, C = grid[0].length;
boolean[][] visited = new boolean[R][C];
int res = 0;
int[][] xy_to_idx = new int[R][C];
int[] idx_to_x = new int[R * C], idx_to_y = new int[R * C];
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) {
int idx = i * C + j;
xy_to_idx[i][j] = idx;
idx_to_x[idx] = i;
idx_to_y[idx] = j;
}
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) {
if (!visited[i][j] && grid[i][j] == '1') {
bfs (grid, i, j, visited, xy_to_idx, idx_to_x, idx_to_y);
res++;
}
}
return res;
}
void bfs (char[][] board, int rx, int ry, boolean[][] visited, int[][] xy_to_idx, int[] idx_to_x, int[] idx_to_y) {
Queue<Integer> queue = new LinkedList<> ();
queue.offer (xy_to_idx[rx][ry]);
while (!queue.isEmpty ()) {
int cur_idx = queue.poll ();
int x = idx_to_x[cur_idx], y = idx_to_y[cur_idx];
for (int i = 0; i < 4; i++) {
int nx = x + dirs[i], ny = y + dirs[i + 1];
if (inBound (board, nx, ny) && board[nx][ny] == '1' && !visited[nx][ny]) {
visited[nx][ny] = true;
queue.offer (xy_to_idx[nx][ny]);
}
}
}
}
boolean inBound (char[][] board, int x, int y) {
return x >= 0 && y >= 0 && x < board.length && y < board[0].length;
}
}
/******************************************************************************/
public static void main(String[] args) {
NumberOfIslandes.Solution tester = new NumberOfIslandes.Solution();
char[][][] inputs = {
{{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}}, {{'3'}},
{
{'1','1','1','1','1','0','1','1','1','1','1','1','1','1','1','0','1','0','1','1'},
{'0','1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','1','0'},
{'1','0','1','1','1','0','0','1','1','0','1','1','1','1','1','1','1','1','1','1'},
{'1','1','1','1','0','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},
{'1','0','0','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},
{'1','0','1','1','1','1','1','1','0','1','1','1','0','1','1','1','0','1','1','1'},
{'0','1','1','1','1','1','1','1','1','1','1','1','0','1','1','0','1','1','1','1'},
{'1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','0','1','1'},
{'1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','1','1','1','1','1'},
{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},
{'0','1','1','1','1','1','1','1','0','1','1','1','1','1','1','1','1','1','1','1'},
{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},
{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},
{'1','1','1','1','1','0','1','1','1','1','1','1','1','0','1','1','1','1','1','1'},
{'1','0','1','1','1','1','1','0','1','1','1','0','1','1','1','1','0','1','1','1'},
{'1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','1','1','0'},
{'1','1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','0','0'},
{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},
{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},
{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'}
}, {{'1'}},
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
char[][] grid = inputs[2 * i];
int ans = Character.getNumericValue (inputs[2 * i + 1][0][0]), output = tester.numIslands (grid);
System.out.printf ("%s -> %s, expected: %d\n",
Matrix.printMatrix (grid), Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
第一版代码:
class Solution {
static int[] dirs = {-1, 0, 1, 0, -1};
public int numIslands(char[][] grid) {
int R = grid.length, C = grid[0].length;
boolean[][] visited = new boolean[R][C];
int res = 0;
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) {
if (!visited[i][j]) {
dfs (grid, i, j, visited);
res++;
}
}
return res;
}
void dfs (char[][] board, int x, int y, boolean[][] visited) {
if (!inBound (board, x, y) || visited[x][y])
return;
visited[x][y] = true;
for (int i = 0; i < 4; i++)
dfs (board, x + dirs[i], y + dirs[i + 1], visited);
}
boolean inBound (char[][] board, int x, int y) {
return x >= 0 && y >= 0 && x < board.length && y < board[0].length;
}
}
正确性实际上是没有问题的, 不过因为用了recursion, 被break掉了;
上面的代码其实有问题, 但是没有意识到而已;
改成下面这个iterative的代码:
class Solution {
static int[] dirs = {-1, 0, 1, 0, -1};
public int numIslands(char[][] grid) {
if (grid.length == 0 || grid[0].length == 0)
return 0;
int R = grid.length, C = grid[0].length;
boolean[][] visited = new boolean[R][C];
int res = 0;
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) {
if (!visited[i][j] && grid[i][j] == '1') {
dfs (grid, i, j, visited);
res++;
}
}
return res;
}
void dfs (char[][] board, int rx, int ry, boolean[][] visited) {
Deque<int[]> stack = new ArrayDeque<> ();
stack.push (new int[] {rx, ry});
while (!stack.isEmpty ()) {
int[] cur = stack.pop ();
int x = cur[0], y = cur[1];
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dirs[i], ny = y + dirs[i + 1];
if (inBound (board, nx, ny) && board[nx][ny] == '1' && !visited[nx][ny]) {
stack.offer (new int[] {nx, ny});
}
}
}
}
boolean inBound (char[][] board, int x, int y) {
return x >= 0 && y >= 0 && x < board.length && y < board[0].length;
}
}
但是TLE了; 然后我就真的不知道怎么办了; 难道必须用UF来做? 这个其实已经是线性的复杂度了啊;
那就再改, 用BFS试试看;
然后改成BFS还是过不了, 然后我就没办法了, 不知道这个题目tag给BFS和DFS是什么意思; 不想了;
突然想到这里的一个优化我忘记了, 就是1D index的优化, 可能会让collection的操作快一点; 不过卡这种东西真的有意思吗;
看editorial的时候发现, 我上面的代码不是优化的问题, 好像是逻辑有毛病, 把那个TLE的case给拿到本地上, 也是直接就卡死了;
最后好容易是AC了, 速度是18ms (4%), 比较慢;
至于真正的原因, 其实也是之前碰到过的一个问题:
BFS visited: mark when enqueue if overlapping paths
这个问题其实也没啥好说的, 以前也总结过, 尤其容易在这种board的题目上面出现, 因为天然的就有overlap; 没想到今天这里又踩了一次这个坑;
具体内容就是这种有overlap的时候, BFS最好是在offer的时候mark visited, 而不是Poll的时候; 不然重复被offer的太多了;
不过最后为什么会卡死? 按说这种顶多是慢一点?
editorial
Approach #1 DFS [Accepted]
Intuition
Treat the 2d grid map as an undirected graph and there is an edge between two horizontally or vertically adjacent nodes of value '1'.
Algorithm
Linear scan the 2d grid map, if a node contains a '1', then it is a root node that triggers a Depth First Search. During DFS, every visited node should be set as '0' to mark as visited node. Count the number of root nodes that trigger DFS, this number would be the number of islands since each DFS starting at some root identifies an island.
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;
}
}
等于说DFS是可以的; 我大概知道为什么我的第一个代码爆栈了, 因为当时实际上代码里面还有其他的bug, 忘记修了, 当时的爆栈实际上不是因为用了recursion, 而是因为那些bug;
人家这里的recursion就好好的;
另外, 这里他们用的都是InPlace flag的操作, 按说这个应该不会有太大影响的; 而且以前也见到过一个说法, 就是modify input是可能从concurrency的角度上面有不利效果的;
Approach #2: BFS [Accepted]
Algorithm
Linear scan the 2d grid map, if a node contains a '1', then it is a root node that triggers a Breadth First Search. Put it into a queue and set its value as '0' to mark as visited node. Iteratively search the neighbors of enqueued nodes until the queue becomes empty.
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'; // mark as visited
Queue<Integer> 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[row+1][col] == '1') {
neighbors.add((row+1) * nc + col);
grid[row+1][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][col+1] == '1') {
neighbors.add(row * nc + col+1);
grid[row][col+1] = '0';
}
}
}
}
}
return num_islands;
}
}
这个BFS跟我的唯一的区别就是用了1D index; 然后我看了一下他这个速度, 是9%, 所以估计真的就是差这么一个小优化; 这个题目卡这个就真的没意思了; 而且上面recursion的DFS其实非常快;
不过说起来, 真正面试的时候如果确定自己的代码没问题(并不是那么简单的, 比如我上面recursion写法有问题我自己就没有意识到), 还是TLE, 那么可能就真的得往这些trivial的小优化的方向上面去思考, 能AC才是王道;
Approach #3: Union Find (aka Disjoint Set) [Accepted]
Algorithm
Traverse the 2d grid map and union adjacent lands horizontally or vertically, at the end, return the number of connected components maintained in the UnionFind data structure.
For details regarding to Union Find, you can refer to this article.
class Solution {
class UnionFind {
int count; // # of connected components
int[] parent;
int[] rank;
public UnionFind(char[][] grid) { // for problem 200
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) { // path compression
if (parent[i] != i) parent[i] = find(parent[i]);
return parent[i];
}
public void union(int x, int y) { // union with rank
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[r+1][c] == '1') {
uf.union(r * nc + c, (r+1) * 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][c+1] == '1') {
uf.union(r * nc + c, r * nc + c + 1);
}
}
}
}
return uf.getCount();
}
}
本来想做UF的, 不过当时也是没有想清楚一般UF算法设计的时候的workflow到底是什么(虽然记得几个常用的接口和需要维护的数据结构);
recursion写法的path compression, 注意看看;
仔细看了一下这里的代码, 这个代码非常指的学习, 可以说是目前看过的最全面而且clean的UF的实现了, 包括rank, count, path compression, 这些的实现细节, 全部都涵盖了;
另外一点需要注意的就是这里的workflow, 也就是如果你真的是知道了用UF来解这个题目, 你具体怎么把UF用在这里; 这题如果真的当时实际上开始写UF的话, 我估计还是可以写出来的; 但是当时我最后决定不写UF的一个最主要的原因, 是因为不知道, 就算我有了一个完整的UF结构, 我怎么具体的用他来解决这题的具体的问题;
另外, UF我的另外一个盲点, 就是复杂度;
Time complexity :
O(M×N) where M is the number of rows and N is the number of columns. Note that Union operation takes essentially constant time1 when UnionFind is implemented with both path compression and union by rank.
真要问为什么, 我也不知道; 但是要注意这里的两个修饰条件, rank和path compression都要实现了才能做到这个复杂度;
https://leetcode.com/problems/number-of-islands/discuss/56359/Very-concise-Java-AC-solution
public class Solution {
private int n;
private int m;
public int numIslands(char[][] grid) {
int count = 0;
n = grid.length;
if (n == 0) return 0;
m = grid[0].length;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++)
if (grid[i][j] == '1') {
DFSMarking(grid, i, j);
++count;
}
}
return count;
}
private void DFSMarking(char[][] grid, int i, int j) {
if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] != '1') return;
grid[i][j] = '0';
DFSMarking(grid, i + 1, j);
DFSMarking(grid, i - 1, j);
DFSMarking(grid, i, j + 1);
DFSMarking(grid, i, j - 1);
}
}
想想这题其实也没什么复杂的;
Nice solution :)
Op’s thought process - Just drown every island - one by one!!
这个解释有点意思;
注意这种解法的复杂度, worst case才会把MN都走完; 通常情况下, 是不会走完所有的, 因为不是每一个cell都能开始一个DFS;
For any problem I work on, I will try to generalize some reusable template out for future use. We have limited time during interview and too much to worry about, so having some code template to use is very handy. For this problem, although it is easier and probably suggested to use BFS, but Union find also comes handy and can be easily extended to solve Island 2 and Surrounded regions.
I separate all the union find logic in a separate class and use 1d version to make the code clear. I also use a 2d array for the 4 direction visit. int[][] distance = {{1,0},{-1,0},{0,1},{0,-1}} ;
int[][] distance = {{1,0},{-1,0},{0,1},{0,-1}};
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
UnionFind uf = new UnionFind(grid);
int rows = grid.length;
int cols = grid[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
for (int[] d : distance) {
int x = i + d[0];
int y = j + d[1];
if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == '1') {
int id1 = i*cols+j;
int id2 = x*cols+y;
uf.union(id1, id2);
}
}
}
}
}
return uf.count;
}
Union Find:
class UnionFind {
int[] father;
int m, n;
int count = 0;
UnionFind(char[][] grid) {
m = grid.length;
n = grid[0].length;
father = new int[m*n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
int id = i * n + j;
father[id] = id;
count++;
}
}
}
}
public void union(int node1, int node2) {
int find1 = find(node1);
int find2 = find(node2);
if(find1 != find2) {
father[find1] = find2;
count--;
}
}
public int find (int node) {
if (father[node] == node) {
return node;
}
father[node] = find(father[node]);
return father[node];
}
}
思路跟之前是差不多的; 这个人的观点是正确的, 这种经典算法, 你就是应该能够做到默写的程度; 看起来代码一大段, 但是假如你熟悉, 尤其是这种board类的题目, 常见的UF场景, 应该能很快的直接就把这个代码给默写出来; 然后主函数里面处理一下逻辑就行了;
不过这个人好像没有实现rank; 还是抽时间把editorial3给背下来比较好;
submission最快是recursion, 没仔细看了;
Problem Description
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110
11010
11000
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
Difficulty:Medium
Total Accepted:161.9K
Total Submissions:445.2K
Contributor:LeetCode
Companies
googlefacebookmicrosoftamazonzenefits
Related Topics
depth-first searchbreadth-first searchunion find
Similar Questions
Surrounded RegionsWalls and GatesNumber of Islands IINumber of Connected Components in an Undirected GraphNumber of Distinct IslandsMax Area of Island