200. Number of Islands

  • 33.0%

https://leetcode.com/problems/number-of-islands/?tab=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.

1
2
3
4
5
6
7
Example 1:

11110
11010
11000
00000
Answer: 1
1
2
3
4
5
6
7
Example 2:

11000
11000
00100
00011
Answer: 3

方法一:

深度优先遍历

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if(grid.empty() || grid[0].empty()) return 0;
int res = 0;
for(int i=0; i<grid.size(); i++){
for(int j=0; j<grid[0].size(); j++){
if(grid[i][j]=='1'){
res++;
helper(grid, i, j);
}
}
}
return res;
}

void helper(vector<vector<char>>& grid, int i, int j){
// 此处是=,而不是==,区分 = 与 ==
grid[i][j] = '0';
if(i-1>=0 && grid[i-1][j]=='1')
helper(grid, i-1, j);
if(i+1<grid.size() && grid[i+1][j]=='1')
helper(grid, i+1, j);
if(j-1>=0 && grid[i][j-1]=='1')
helper(grid, i, j-1);
if(j+1<grid[0].size() && grid[i][j+1]=='1')
helper(grid, i, j+1);
}

};

helper函数中的向左遍历和向下遍历,不能省略

否则对于样例,111,010, 111通不过,应该为1,输出却为2

https://discuss.leetcode.com/topic/11589/dfs-and-bfs-in-c

DFS and BFS in C++

When we met a ‘1’, the answer add 1, we also need to search all ‘1’ which connected to it directly or indirectly, and change it to ‘0’. And we can use DFS or BFS to search.

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution
{
public:
int numIslands(vector<vector<char>> &grid)
{
if(grid.size() == 0 || grid[0].size() == 0)
return 0;

int res = 0;
for(int i = 0; i < grid.size(); ++ i)
for(int j = 0; j < grid[0].size(); ++ j)
if(grid[i][j] == '1')
{
++ res;
DFS(grid, i, j);
}
return res;
}
private:
void DFS(vector<vector<char>> &grid, int x, int y)
{
grid[x][y] = '0';
if(x > 0 && grid[x - 1][y] == '1')
DFS(grid, x - 1, y);
if(x < grid.size() - 1 && grid[x + 1][y] == '1')
DFS(grid, x + 1, y);
if(y > 0 && grid[x][y - 1] == '1')
DFS(grid, x, y - 1);
if(y < grid[0].size() - 1 && grid[x][y + 1] == '1')
DFS(grid, x, y + 1);
}
};

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution
{
public:
int numIslands(vector<vector<char>> &grid)
{
if(grid.size() == 0 || grid[0].size() == 0)
return 0;

int res = 0;
for(int i = 0; i < grid.size(); ++ i)
for(int j = 0; j < grid[0].size(); ++ j)
if(grid[i][j] == '1')
{
++ res;
BFS(grid, i, j);
}
return res;
}
private:
void BFS(vector<vector<char>> &grid, int x, int y)
{
queue<vector<int>> q;
q.push({x, y});
grid[x][y] = '0';

while(!q.empty())
{
x = q.front()[0], y = q.front()[1];
q.pop();

if(x > 0 && grid[x - 1][y] == '1')
{
q.push({x - 1, y});
grid[x - 1][y] = '0';
}
if(x < grid.size() - 1 && grid[x + 1][y] == '1')
{
q.push({x + 1, y});
grid[x + 1][y] = '0';
}
if(y > 0 && grid[x][y - 1] == '1')
{
q.push({x, y - 1});
grid[x][y - 1] = '0';
}
if(y < grid[0].size() - 1 && grid[x][y + 1] == '1')
{
q.push({x, y + 1});
grid[x][y + 1] = '0';
}
}
}
};

https://discuss.leetcode.com/topic/13045/my-accepted-c-solution-may-be-trivial

My accepted c++ solution (may be trivial)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
void contaminate(vector<vector<char> > &grid, int i, int j){
if(i>0&&grid[i-1][j]=='1'){
grid[i-1][j]='0';
contaminate(grid, i-1, j);
}
if(j>0&&grid[i][j-1]=='1'){
grid[i][j-1]='0';
contaminate(grid, i, j-1);
}
if(i<grid.size()-1&&grid[i+1][j]=='1'){
grid[i+1][j]='0';
contaminate(grid, i+1, j);
}
if(j<grid[0].size()-1&&grid[i][j+1]=='1'){
grid[i][j+1]='0';
contaminate(grid, i, j+1);
}
}
int numIslands(vector<vector<char>> &grid) {
int n=grid.size();
if(n==0) return 0;
int m=grid[0].size();

int cnt=0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(grid[i][j]=='1'){
cnt++;
contaminate(grid, i, j);
}
}
}
return cnt;
}
};

python


202ms, 15.49%, October 18, 2016

https://discuss.leetcode.com/topic/16749/7-lines-python-14-lines-java

7 lines Python, ~ 14 lines Java

Sink and count the islands.

Python Solution

1
2
3
4
5
6
7
8
def numIslands(self, grid):
def sink(i, j):
if 0 <= i < len(grid) and 0 <= j < len(grid[i]) and grid[i][j] == '1':
grid[i][j] = '0'
map(sink, (i+1, i-1, i, i), (j, j, j+1, j-1))
return 1
return 0
return sum(sink(i, j) for i in range(len(grid)) for j in range(len(grid[i])))

Java Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
char[][] g;
public int numIslands(char[][] grid) {
int islands = 0;
g = grid;
for (int i=0; i<g.length; i++)
for (int j=0; j<g[i].length; j++)
islands += sink(i, j);
return islands;
}
int sink(int i, int j) {
if (i < 0 || i == g.length || j < 0 || j == g[i].length || g[i][j] == '0')
return 0;
g[i][j] = '0';
sink(i+1, j); sink(i-1, j); sink(i, j+1); sink(i, j-1);
return 1;
}
}

Java Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public int numIslands(char[][] grid) {
int islands = 0;
for (int i=0; i<grid.length; i++)
for (int j=0; j<grid[i].length; j++)
islands += sink(grid, i, j);
return islands;
}
int sink(char[][] grid, int i, int j) {
if (i < 0 || i == grid.length || j < 0 || j == grid[i].length || grid[i][j] == '0')
return 0;
grid[i][j] = '0';
for (int k=0; k<4; k++)
sink(grid, i+d[k], j+d[k+1]);
return 1;
}
int[] d = {0, 1, 0, -1, 0};
}

java


https://discuss.leetcode.com/topic/13248/very-concise-java-ac-solution

Very concise Java AC solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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);
}
}

https://discuss.leetcode.com/topic/11590/simple-java-solution

Simple Java Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class NumberofIslands {
static int[] dx = {-1,0,0,1};
static int[] dy = {0,1,-1,0};
public static int numIslands(char[][] grid) {
if(grid==null || grid.length==0) return 0;
int islands = 0;
for(int i=0;i<grid.length;i++) {
for(int j=0;j<grid[i].length;j++) {
if(grid[i][j]=='1') {
explore(grid,i,j);
islands++;
}
}
}
return islands;
}
public static void explore(char[][] grid, int i, int j) {
grid[i][j]='x';
for(int d=0;d<dx.length;d++) {
if(i+dy[d]<grid.length && i+dy[d]>=0 && j+dx[d]<grid[0].length && j+dx[d]>=0 && grid[i+dy[d]][j+dx[d]]=='1') {
explore(grid,i+dy[d],j+dx[d]);
}
}
}
}

The algorithm works as follow:

  1. Scan each cell in the grid.
  2. If the cell value is ‘1’ explore that island.
  3. Mark the explored island cells with ‘x’.
  4. Once finished exploring that island, increment islands counter.

The arrays dx[], dy[] store the possible moves from the current cell. Two land cells [‘1’] are considered from the same island if they are horizontally or vertically adjacent (possible moves (-1,0),(0,1),(0,-1),(1,0)). Two ‘1’ diagonally adjacent are not considered from the same island.


https://discuss.leetcode.com/topic/20080/clear-easy-java-solution

Clear & Easy Java Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
public int numIslands(char[][] grid) {
int count = 0;

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

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

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

https://discuss.leetcode.com/topic/11705/simple-dfs-sulotion

Simple DFS sulotion

Dont need the extra space, and O(mn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int numIslands(char[][] grid) {
int islands = 0;
if (grid != null && grid.length != 0 && grid[0].length != 0) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
islands++;
}
}
}
}
return islands;
}

private void dfs(char[][] grid, int x, int y) {
if (x < 0 || grid.length <= x || y < 0 || grid[0].length <= y || grid[x][y] != '1') {
return;
}
grid[x][y] = 'x';
dfs(grid, x + 1, y);
dfs(grid, x - 1, y);
dfs(grid, x, y + 1);
dfs(grid, x, y - 1);
}
谢谢你,可爱的朋友。