給你一個(gè)由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格，請你計(jì)算網(wǎng)格中島嶼的數(shù)量。
島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。
此外，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍。
示例 1:
輸入:
11110
11010
11000
00000
輸出: 1
示例 2:
輸入:
11000
11000
00100
00011
輸出: 3
解釋: 每座島嶼只能由水平和/或豎直方向上相鄰的陸地連接而成。
解題思路
島嶼問題是網(wǎng)格類型的典型案例，主要考察DFS（深度優(yōu)先搜索）和BFS（廣度優(yōu)先搜索）以及Union find（并查集）。
DFS寫法（使用迭代和遞歸）：遍歷整個(gè)網(wǎng)格，如果一個(gè)位置是'1',則以該店進(jìn)行深度搜索查詢，計(jì)數(shù)的同時(shí)把位置'1'置為'0'(同時(shí)需要注意邊界問題，防止出界)。
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;
}
//每一個(gè)臨界的'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);
}
}
}
運(yùn)算結(jié)果：執(zhí)行用時(shí)：2ms，內(nèi)存消耗：42MB
BFS寫法（使用隊(duì)列）:掃描整個(gè)網(wǎng)格，如果位置是'1'，則加入隊(duì)列，并以該位置開始進(jìn)行廣度搜索，在廣度搜索中每一個(gè)'1'都會(huì)被重置為'0'，知道隊(duì)列為空，搜索結(jié)束。
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);
//廣度優(yōu)先搜索
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;
}
}
運(yùn)算結(jié)果：執(zhí)行用時(shí)：6ms，內(nèi)存消耗：42.4MB
union find（并查集）：并查集這種數(shù)據(jù)結(jié)構(gòu)主要用于數(shù)據(jù)的分類和判斷兩個(gè)元素是否屬于同一類別，可以借助該思想對題目中的滿足條件的島嶼進(jìn)行合并。
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; //每個(gè)島嶼‘1’都是一個(gè)集合，剩下的就是集合的合并
}
rank[i*col+j] = 0;
}
}
}
//遞歸找到root，方便后面union方法中x和root直接建立聯(lián)系，壓縮路徑
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;
}
//去除重復(fù)的關(guān)聯(lián)島嶼
count--;
}
}
public int getCount()
{
return count;
}
}
}
執(zhí)行結(jié)果：執(zhí)行用時(shí) : 6 ms 內(nèi)存消耗 :42 MB
