LeetCode 200 Number of Islands

LeetCode 200 Number of Islands

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

题目大意：

给定一个由字符‘1’（陆地）和‘0’（水域）组成的二维网格地图，计算岛屿的个数。岛屿被水域环绕，由竖直或者水平方向邻接的陆地构成。你可以假设网格地图的四条边都被水域包围。

BFS解题思路：

BFS入列后立即标记为已访问，否则会有空间和时间问题。
二维变成一维，不但节省空间，还可以避免创建Point的新class。a = x * C + y(C为列数) <=> x = a/C, y = a%C

注意事项：

1. 注意到题目给定输入数组的类型，用其来标记已访问的单元（节点）。
2. BFS中如果cell为0或X就要跳过，不要漏掉0，因为如果是海不应做BFS。根据题目要求，可能还要将X恢复为1.

Python代码：

OFFSETS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.bfs(grid, i, j)
                    count += 1
        return count

    def bfs(self, nums, i, j):
        queue = deque([(i, j)])
        nums[i][j] = 'X'
        while queue:
            island = queue.popleft()
            for dx, dy in OFFSETS:
                x, y = island[0] + dx, island[1] + dy
                if x < 0 or x >= len(nums) or y < 0 or y >= len(nums[0]) or nums[x][y] in ['0', 'X']:
                    continue
                queue.append((x, y))
                nums[x][y] = 'X'

Java代码：

public int numIslands2(char[][] grid) {
	if (grid ==null || grid.length == 0 || grid[0].length == 0)
		return 0;
	
	boolean[][] visited = new boolean[grid.length][grid[0].length];
	int islands = 0;
	for(int i = 0; i < grid.length; i++)
		for(int j=0; j < grid[0].length; j++) {
			if(grid[i][j] == '0' || visited[i][j])
				continue;
	
			bfs3(grid, i, j, visited);
			islands++;
		}
	return islands;
}

public void bfs3(char[][] grid, int a, int b, boolean[][] visited) {
	Queue<Point> q = new LinkedList<>();
	int[][] directions = new int[][] {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
	q.offer(new Point(a, b));
	visited[a][b] = true;
	while(!q.isEmpty()) {
		Point point = q.poll();
		for(int i = 0; i < 4; i++) {
			Point neighbor = new Point(point.x + directions[i][0], point.y + directions[i][1]);
			if(!isValid(grid, neighbor.x, neighbor.y) || visited[neighbor.x][neighbor.y])
				continue;
			
			q.offer(neighbor);
			visited[neighbor.x][neighbor.y] = true;
		}
	}
}

算法分析：

时间复杂度为O(MN)，空间复杂度O(min{M,N})。M,N分别为矩阵长宽。因为最坏情况下，以矩形中心为root，最大的一层为矩形里面的最大正方形，它的长度为min{M,N}。

DFS解题思路：

遍历矩阵的每一个元素，对每个元素进行DFS四个方位搜索陆地，访问过的元素在原数组中进行标记。每次DFS搜索后，层数加1。

Java代码：

public int numIslands(char[][] grid) {
	int layer = 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);
				layer++;
		}
	
	return layer;
}

public void dfs(char[][] grid, int a, int b){
	if(!isValid(grid,a,b))
		return;
	
	grid[a][b] = 'x';
	dfs(grid, a+1, b);
	dfs(grid, a-1, b);
	dfs(grid, a, b+1);
	dfs(grid, a, b-1);
}

public boolean isValid(char[][] grid, int x, int y){
	if(x<0||x>=grid.length||y<0||y>=grid[0].length||grid[x][y]!='1')
		return false;
	return true;
}

算法分析：

时间复杂度为O(MN)，空间复杂度O(MN)。M,N分别为矩阵长宽。最坏情况，全为陆地，DFS退化成线性。

Union Find解题思路：

见Union Find算法详解。

1. 初始化UnionFind类，包括3个属性：count（独立连通数）, parent（某节点的父节点）, rank（连通集排名）。合格的节点的parent初始化为自己的id，rank为0，count为所有合格节点数量。
2. 遍历所有节点，union此节点及其相邻的节点（如上下左右）
3. union时候，先find两节点的根节点，若相同忽略。若不同，合并此两连通集：rank大的连通集，作为rank小的连通集的父节点。若rank相等，选任一作为另一个的父节点且把它的rank加1。count减1。
   如下图，union 6和11的，find(6)会进行压缩路径，把6接到5下。
   
4. find寻找根节点的同时，压缩成与根节点路径为1的连通。

Java代码：

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) {
		if (parent[i] != i) {
			parent[i] = find(parent[i]); // path compression
		}
		return parent[i];
	}

	// union with rank
	public void union(int x, int y) {
		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 numIslands3(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();
}

算法分析：

时间复杂度为O(MN)，空间复杂度O(MN)。M,N分别为矩阵长宽。遍历每个节点，而每个节点只会遍历4个相邻节点。

Follow-up:

1. 打印所有island坐标
2. 计算湖的数量。湖是被island维住的水域，与海有区别。解法是先从四条边界的海域进行DFS，标记为-1，然后采用上述算法，只要将搜寻1改为搜寻0即可。
3. 如果内存有限，不能一次读整个矩阵。方案是分块做，然后保留边界信息作为下一块的输入。
4. 地图中途被改动。分情况，若0->1，若此单元邻居只有一种label（即使多个邻居），岛屿数不变。无邻居，岛屿数+1。邻居有多种label为n，岛屿数减少n-1。Union Find也是一个更简洁方案。
   此情况比较简单，只要查看邻居即可，因为它只会增加连接。
   若1->0, 对此单元相邻的四个单元进行DFS重新label新数，新数的种数-四单元的DSF岛屿个数=岛屿增加的个数。
   此情况需要重新做DFS，因为它破坏连接，可能导致连通性变小。