LeetCode 200. 岛屿数量

我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 200. 岛屿数量

题目

给你一个由?'1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

输入:
11110
11010
11000
00000
输出:?1

示例?2:

输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

比较自然能想到的是用dfs解决，且比较方便，也可以用bfs，每个1都需要一次bfs；

思路1-dfs给岛屿编号

每遇到一个1就dfs，并给从'2'开始的编号，遍历完最后的编号减去'2'即岛屿数；

算法复杂度:

• M为行数，N为列数；
• 时间复杂度： $ {\color{Magenta}{\Omicron\left(M \ast N\right)}} $
• 空间复杂度： $ {\color{Magenta}{\Omicron\left(M \ast N\right)}} $

思路2-bfs给岛屿编号

每遇到一个1就bfs，并给从'2'开始的编号，遍历完最后的编号减去'2'即岛屿数；

小技巧:以前bfs遇到数组这样的数据，在构造队列存储时需要用数组存二维坐标，但是本题把坐标转化为int存储

• row为行数，col为列数，对于坐标[i,j]，t=i*col+j，存t;
• 取的时候因为j<col，所以i=t/col，j=t%col，这样把二维压缩为一维就避免了创建数组这个比较耗时的操作；

算法复杂度:

• M为行数，N为列数；
• 时间复杂度： $ {\color{Magenta}{\Omicron\left(M \ast N\right)}} $
• 空间复杂度： $ {\color{Magenta}{\Omicron\left(Min\left(M,N\right)\right)}} $

算法源码示例

package leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author ZhouJie
 * @date 2020年4月20日 下午3:23:26 
 * @Description: 200. 岛屿数量
 *
 */
public class LeetCode_0200 {

}

class Solution_0200 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年4月20日 下午4:12:48 
	 * @param: @param grid
	 * @param: @return
	 * @return: int
	 * @Description: 1-DFS，每找到一个1就给岛屿一个编号并DFS，最后命名的数量就是岛屿数；
	 *
	 */
	public int numIslands_1(char[][] grid) {
		if (grid == null || grid.length == 0 || grid[0].length == 0) {
			return 0;
		}
		int row = grid.length;
		int col = grid[0].length;
		// 因为源数组是'1'，所以岛屿编号从'2'开始
		char count = '2';
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				// 每找到一个'1'就dfs并标记 为当前编号
				if (grid[i][j] == '1') {
					dfs(grid, i, j, count);
					// 标记完当前岛屿编号递增
					count++;
				}
			}
		}
		// 一共标记的岛屿数
		return count - '2';
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年4月20日 下午4:13:59 
	 * @param: @param grid
	 * @param: @param i
	 * @param: @param j
	 * @param: @param count
	 * @return: void
	 * @Description: dfs
	 *
	 */
	private void dfs(char[][] grid, int i, int j, char count) {
		if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == '1') {
			grid[i][j] = count;
			dfs(grid, i - 1, j, count);
			dfs(grid, i + 1, j, count);
			dfs(grid, i, j - 1, count);
			dfs(grid, i, j + 1, count);
		}
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年4月20日 下午4:22:47 
	 * @param: @param grid
	 * @param: @return
	 * @return: int
	 * @Description: 2-BFS，不同与同源BFS，本题恰是要计算不同源的数量，所以每遇到一个'1'就需要一次BFS； 
	 *
	 */
	public int numIslands_2(char[][] grid) {
		if (grid == null || grid.length == 0 || grid[0].length == 0) {
			return 0;
		}
		int row = grid.length;
		int col = grid[0].length;
		// 因为源数组是'1'，所以岛屿编号从'2'开始
		char count = '2';
		Deque<Integer> queue = new LinkedList<Integer>();
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				// 每找到一个'1'就dfs并标记 为当前编号
				if (grid[i][j] == '1') {
					// 这里存ij的位置很巧妙，用col乘以i再加j，因为j<col，所以取回时除以col就能再得到i，而对col取模就得到了j，避免了用数组存ij
					queue.offer(i * col + j);
					while (!queue.isEmpty()) {
						Integer poll = queue.poll();
						int x = poll / col;
						int y = poll % col;
						if (x > 0 && grid[x - 1][y] == '1') {
							grid[x - 1][y] = count;
							queue.offer((x - 1) * col + y);
						}
						if (y > 0 && grid[x][y - 1] == '1') {
							grid[x][y - 1] = count;
							queue.offer(x * col + y - 1);
						}
						if (x < row - 1 && grid[x + 1][y] == '1') {
							grid[x + 1][y] = count;
							queue.offer((x + 1) * col + y);
						}
						if (y < col - 1 && grid[x][y + 1] == '1') {
							grid[x][y + 1] = count;
							queue.offer(x * col + y + 1);
						}

					}
					// 标记完当前岛屿编号递增
					count++;
				}
			}
		}
		return count - '2';
	}
}

原文链接:https://www.cnblogs.com/izhoujie/p/12740362.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有