Leetcode Answers 200

今晚第二道题,然后就该睡觉了。这次是二维矩阵上的递归问题。

题目:
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:

1
2
3
4
11110
11010
11000
00000

Answer: 1

Example 2:

1
2
3
4
11000
11000
00100
00011

Answer: 3

思路:
读完题之后的第一个反应就是,当我找到一个点是land的时候,我要怎样把整个Island都找全。第二个反应就是我要做怎样的标记来处理这个island以至于我不会再看它一眼。那么这里给了规则,就是横竖两个方向上相连的才算相连,斜线上的不算,那么递归一下就能找到所有的点了。其次,当我们找到一个land的时候,就可以选择对它进行标记,说白了只要把那个从‘1’改成随便什么不是‘1’的就好,因为我们只看‘1’,是当成水也好,改成随机内容也好,反正只要不是land,我们就知道ok这里我们已经看过了。那么我们第一次找到一个land的时候才算为一个land,递归部分的不算,所以我们需要一个外层包装结构。于是答案就出来了:一个专门用来递归的函数负责标记land,main负责看grid找‘1’,找到了count一下,标记land。grid看完就数完了。

Answer:

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
public class Solution {
public int NumIslands(char[,] grid) {
var count = 0;
int m = grid.GetLength(0), n = grid.GetLength(1);
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
if(grid[i, j] == '0') continue;
floodTheGround(grid, i, j);
count++;
}
}
return count;
}
private void floodTheGround(char[,] grid, int x, int y){
if(x < 0 || y < 0 || x >= grid.GetLength(0) || y >= grid.GetLength(1)) return;
if(grid[x, y] == '0') return;
grid[x, y] = '0';
floodTheGround(grid, x-1, y);
floodTheGround(grid, x+1, y);
floodTheGround(grid, x, y-1);
floodTheGround(grid, x, y+1);
}
}

考察:突然想到我没仔细了解过,int[,]int[][]是什么区别,就去查了一下。int[,]叫做multidimensional array,这个东西的memory alignment是连在一起的。而int[][]叫做array of array,相比而言memory是分散的。理论上multidimensional array的速度应该比array of array好,因为每一次查询其中的元素的时候,arr[10,5]找的是10 * len + 5,就像一元array一样,而arr[10][5]就真的是先去查询放在index = 10的那个array,然后再去查询这个arry的index = 5的元素。然而据说因为C#的编译器的implementation没有做好,导致实际上multidimensional array并没有array of array的效率高。真是尴尬。。。

以上。

17-04-23
@Sturbridge