200.Number of Islands (M)
https://leetcode.com/problems/number-of-islands/
1.Description
Given a boolean 2D matrix,0
is represented as the sea,1
is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.
Find the number of islands.
Example
Given graph:
[
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1]
]
return3
.
2.Code
https://www.jiuzhang.com/problem/number-of-islands/
时间 O(NM) 空间 O(max(N,M)) 递归栈空间
Version 1: BFS
bfs 用一个queue记录“1”和他的周围是“1”的位置,把二维变成一维存储。
private int m,n;
public int numIslands(boolean[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int result=0;
m=grid.length;
n=grid[0].length;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==true){
result++;
bfs(grid,i,j);
}
}
}
return result;
}
public void bfs(boolean[][] grid,int x,int y){
//first set itself as false
grid[x][y]=false;
LinkedList<Integer> queue=new LinkedList<Integer>();
//transfer two-dimension to one-dimension
int node=x*n+y;
queue.offer(node);
//queue record the "1" and its adjacent node
while(!queue.isEmpty()){
int current=queue.poll();
//switch current to two-dimension
int i=current/n;
int j=current%n;
//check upward if it is "1" set it as "0" and push into queue
if(i>0 && grid[i-1][j]==true){
grid[i-1][j]=false;
queue.offer((i-1)*n+j);
}
//check downward
if(i<m-1 && grid[i+1][j]==true){
grid[i+1][j]=false;
queue.offer((i+1)*n+j);
}
//check left
if(j>0 && grid[i][j-1]==true){
grid[i][j-1]=false;
queue.offer(i*n+j-1);
}
//check right
if(j<n-1 && grid[i][j+1]==true){
grid[i][j+1]=false;
queue.offer(i*n+j+1);
}
}
}
Version 2: BFS
算法思路: 两层for循环按行列遍历题目所给的数组,当遍历点值为1时,答案值(岛屿数量)加一,然后从这个点开始bfs,搜索所有与其相连的点。将当前点推入队列,每次从取出队头点(x,y),将(x,y)的上下左右四个方向中所有合法点(坐标合法且值为1)推入队列,推入队列时将点数值改为0以标记已走过该点,当队列为空时,遍历结束.
Note:
1.这个题目, 在模板里里的int size = queue.size(); for(int i = 0;i< size; i++){} 其实不需要,因为两个方向数组把这个功能概括了,每次只能取这个点上下左右四个方向。
2, 这个题目不需要visited. 原因是visited过的在BFS范围内的都变成0了,不会再加进queue。变成0这个把visited功能概括了。(下面的题解还是用了TT200.)
class Node { int x; int y;
public Node(int x, int y)
{
this.x = x;
this.y = y;
}
}
public class Solution {
public int numIslands(char[][] grid)
{
if(grid == null || grid.length == 0 || grid[0].length == 0)
{
return 0;
}
int height = grid.length;
int length = grid[0].length;
int result = 0;
for(int i= 0; i< height; i++)
{
for(int j = 0; j< length; j++)
{
if(grid[i][j] == '1')
{
bfsNode(grid, i, j);
result++;
}
}
}
return result;
}
public void bfsNode(char[][] grid, int x, int y)
{
int[] directionX = {0, 0, -1, 1};
int[] directionY = {-1, 1, 0, 0};
Queue<Node> queue = new LinkedList<Node>();
Set<Node> visited = new HashSet<Node>();
queue.offer(new Node(x, y));
grid[x][y] = '0';
while(!queue.isEmpty())
{
Node current = queue.poll();
for(int j = 0; j< 4; j++)
{
int next_x = current.x + directionX[j];
int next_y = current.y + directionY[j];
if(inBound(grid, next_x, next_y))
{
Node adjacent = new Node(next_x, next_y);
if(grid[next_x][next_y] == '1' && !visited.contains(adjacent))
{
queue.offer(adjacent);
visited.add(adjacent);
grid[next_x][next_y] = '0';
}
}
}
}
}
public boolean inBound(char[][] grid, int x, int y)
{
int m = grid.length;
int n = grid[0].length;
return x>=0 && y>=0 && x<m && y<n;
}
}
Version 3: DFS
只要遍历一遍,碰到一个1,就把它周围所有相连的1都标记为非1,这样整个遍历过程中碰到的1的个数就是所求解。
岛屿系列问题可以用 DFS/BFS 算法或者 Union-Find 并查集算法 来解决。
用 DFS 算法解决岛屿题目是最常见的,每次遇到一个岛屿中的陆地,就用 DFS 算法吧这个岛屿「淹掉」。
如何使用 DFS 算法遍历二维数组?你把二维数组中的每个格子看做「图」中的一个节点,这个节点和周围的四个节点连通,这样二维矩阵就被抽象成了一幅网状的「图」。
为什么每次遇到岛屿,都要用 DFS 算法把岛屿「淹了」呢?主要是为了省事,避免维护 visited
数组。
图算法遍历基础 说了,遍历图是需要 visited
数组记录遍历过的节点防止走回头路。
因为 dfs
函数遍历到值为 0
的位置会直接返回,所以只要把经过的位置都设置为 0
,就可以起到不走回头路的作用。
// 主函数,计算岛屿数量
int numIslands(char[][] grid) {
int res = 0;
int m = grid.length, n = grid[0].length;
// 遍历 grid
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
// 每发现一个岛屿,岛屿数量加一
res++;
// 然后使用 DFS 将岛屿淹了
dfs(grid, i, j);
}
}
}
return res;
}
// 从 (i, j) 开始,将与之相邻的陆地都变成海水
void dfs(char[][] grid, int i, int j) {
int m = grid.length, n = grid[0].length;
if (i < 0 || j < 0 || i >= m || j >= n) {
// 超出索引边界
return;
}
if (grid[i][j] == '0') {
// 已经是海水了
return;
}
// 将 (i, j) 变成海水
grid[i][j] = '0';
// 淹没上下左右的陆地
dfs(grid, i + 1, j);
dfs(grid, i, j + 1);
dfs(grid, i - 1, j);
dfs(grid, i, j - 1);
}
为什么每次遇到岛屿,都要用 DFS 算法把岛屿「淹了」呢?主要是为了省事,避免维护 visited 数组。因为 dfs 函数遍历到值为 0 的位置会直接返回,所以只要把经过的位置都设置为 0,就可以起到不走回头路的作用。
PS:这类 DFS 算法还有个别名叫做 FloodFill 算法,现在有没有觉得 FloodFill 这个名字还挺贴切的~
Last updated
Was this helpful?