Number of Islands

Leave a comment

October 30, 2016 by oneOokay

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


二刷整体思想ok,但是清除岛屿没有写出来,用了四个while loop,实际上是错误的,应该用recursive。


Oct 30

这不看答案根本写不出来好吗

我的想法:

1. dp肯定行不通,放弃. 必须全部的scan。

2.想到能够找出每一个岛的边缘,但是也没什么用,按每个边缘去寻找海洋岛屿不切实际,边太大了。想不到接下去的办法。

3.看答案:答案其实就是把每一个岛屿转换成一个单个的1,这样消除了岛屿的所有其他土地,就不存在分辨边缘的问题。所以当接下来继续scan找到另一个1的时候,意味着这是另一个岛屿的边界,所以岛屿数+1.接着对这个新的岛屿进行消除。time complexity为grid mXn

public class Solution {
public int numIslands(char[][] grid) {
int count = 0;
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return count;
}

for (int i = 0; i < grid.length; i ++) {
for (int j = 0; j < grid[0].length; j ++ ) {
if (grid[i][j] == '1') {
count ++;
clearRestofIsland(grid, i, j);
}
}
}
return count;
}

private void clearRestofIsland(char[][] grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
return;
}

grid[i][j] = '0';
clearRestofIsland(grid, i - 1, j);
clearRestofIsland(grid, i + 1, j);
clearRestofIsland(grid, i, j + 1);
clearRestofIsland(grid, i, j - 1);
}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: