给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
解题思路
岛屿问题是网格类型的典型案例，主要考察DFS（深度优先搜索）和BFS（广度优先搜索）以及Union find（并查集）。
DFS写法（使用迭代和递归）：遍历整个网格，如果一个位置是'1',则以该店进行深度搜索查询，计数的同时把位置'1'置为'0'(同时需要注意边界问题，防止出界)。
class Solution {
//dfs
private int rows;
private int cols;
private int count = 0;
public int numIslands(char[][] grid) {
if(grid == null || grid.length == 0) return 0;
rows = grid.length;
cols = grid[0].length;
for(int i = 0 ; i < rows ; i++)
{
for(int j = 0 ; j < cols ; j++)
{
if(grid[i][j] == '0') continue;
count++;
dfs(grid,i,j);
}
}
return count;
}
//每一个临界的'1'都要被重置为'0'，直到遍历完为止
private void dfs(char[][] grid, int i, int j)
{
if(i < 0 || j < 0 || i >= rows || j >= cols) return;
if(grid[i][j] == '1')
{
grid[i][j] = '0';
dfs(grid,i-1,j);
dfs(grid,i+1,j);
dfs(grid,i,j-1);
dfs(grid,i,j+1);
}
}
}
运算结果：执行用时：2ms，内存消耗：42MB
BFS写法（使用队列）:扫描整个网格，如果位置是'1'，则加入队列，并以该位置开始进行广度搜索，在广度搜索中每一个'1'都会被重置为'0'，知道队列为空，搜索结束。
class Solution {
public int numIslands(char[][] grid) {
if(grid == null || grid.length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
int count = 0;
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
if(grid[i][j] == '1')
{
grid[i][j] = '0';
count++;
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(i*cols+j);
//广度优先搜索
while(!queue.isEmpty())
{
int index = queue.poll();
int x = index/cols;
int y = index%cols;
if(x-1>=0 &&grid[x-1][y] == '1')
{
grid[x-1][y] = '0';
queue.offer((x-1)*cols+y);
}
if(x+1<rows &&grid[x+1][y] == '1')
{
grid[x+1][y] = '0';
queue.offer((x+1)*cols+y);
}
if(y-1>=0 &&grid[x][y-1] == '1')
{
grid[x][y-1] = '0';
queue.offer(x*cols+(y-1));
}
if(y+1<cols &&grid[x][y+1] == '1')
{
grid[x][y+1] = '0';
queue.offer(x*cols+(y+1));
}
}
}
}
}
return count;
}
}
运算结果：执行用时：6ms，内存消耗：42.4MB
union find（并查集）：并查集这种数据结构主要用于数据的分类和判断两个元素是否属于同一类别，可以借助该思想对题目中的满足条件的岛屿进行合并。
class Solution {
//union find
public int numIslands(char[][] grid) {
if(grid == null || grid.length == 0) return 0;
int row = grid.length;
int col = grid[0].length;
UnionFind uf = new UnionFind(grid);
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
if(grid[i][j] == '1')
{
grid[i][j] = '0';
if(i-1 >= 0 && grid[i-1][j] == '1')
{
uf.union(i*col+j,(i-1)*col+j);
}
if(i+1 < row && grid[i+1][j] == '1')
{
uf.union(i*col+j,(i+1)*col+j);
}
if(j-1 >= 0 && grid[i][j-1] == '1')
{
uf.union(i*col+j,i*col+j-1);
}
if(j+1 < col && grid[i][j+1] == '1')
{
uf.union(i*col+j,i*col+j+1);
}
}
}
}
return uf.getCount();
}
class UnionFind
{
private int[] parent;
private int[] rank;
private int count = 0;
public UnionFind(char[][] grid)
{
int row = grid.length;
int col = grid[0].length;
parent = new int[row*col];
rank = new int[row*col];
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
if(grid[i][j] == '1')
{
count++;
parent[i*col+j] = i*col+j; //每个岛屿‘1’都是一个集合，剩下的就是集合的合并
}
rank[i*col+j] = 0;
}
}
}
//递归找到root，方便后面union方法中x和root直接建立联系，压缩路径
public int find(int x)
{
if(x != parent[x]) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x,int y)
{
int rootX = find(x);
int rootY = find(y);
if(rootX != rootY)
{
//层级小的归并到层级大的集合上
if(rank[rootX] < rank[rootY])
{
parent[rootX] = rootY;
}else if(rank[rootX] > rank[rootY])
{
parent[rootY] = rootX;
}else
{
parent[rootY] = rootX;
rank[rootX] += 1;
}
//去除重复的关联岛屿
count--;
}
}
public int getCount()
{
return count;
}
}
}
执行结果：执行用时 : 6 ms 内存消耗 :42 MB
网友评论