給定一個由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格，計算島嶼的數(shù)量。一個島被水包圍，并且它是通過水平方向或垂直方向上相鄰的陸地連接而成的。你可以假設(shè)網(wǎng)格的四個邊均被水包圍。
示例 1:
輸入:
11110
11010
11000
00000輸出: 1
示例 2:輸入:
11000
11000
00100
00011輸出: 3
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/number-of-islands
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
使用并查集
class Solution {
/**
* 使用并查集
*
* @param grid
* @return
*/
public int numIslands(char[][] grid) {
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
// 初始化并查集對象
UnionFind uf = new UnionFind(m * n);
// 遍歷所有的島嶼，合并島嶼
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '0') {
// 島嶼數(shù)量減1
uf.decCount();
continue;
}
// 與左邊的島嶼合并
if (i > 0 && grid[i - 1][j] == '1') {
uf.union((i - 1) * n + j, i * n + j);
}
// 與上面的島嶼合并
if (j > 0 && grid[i][j - 1] == '1') {
uf.union(i * n + (j - 1), i * n + j);
}
}
}
return uf.getCount();
}
class UnionFind {
int[] roots; // 存儲并查集
int count = 0; // 島嶼個數(shù)
public UnionFind(int n) {
roots = new int[n];
// 初始化并查集
for (int i = 0; i < n; i++) {
// 并查集節(jié)點自己指向自己
roots[i] = i;
count ++;
}
}
/**
* 獲取root
*
* @param p
* @return
*/
public int findRoot(int p) {
// 獲取root
int root = p;
while (root != roots[root]) {
root = roots[root];
}
// 縮短路徑，將路徑上的所有節(jié)點的root全部賦為找到root
int i = p;
while (i != roots[i]) {
int tmp = roots[i];
roots[i] = root;
i = tmp;
}
return root;
}
/**
* 合并
*
* @param p1
* @param p2
*/
public void union(int p1, int p2) {
int root1 = findRoot(p1);
int root2 = findRoot(p2);
if (root1 != root2) {
roots[root2] = root1;
// 兩個島嶼合并，計數(shù)減1
decCount();
}
}
public void decCount() {
count --;
}
public int getCount() {
return count;
}
}
public static void main(String[] args) {
char[][] grids = {{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'}};
int result = new Solution().numIslands(grids);
System.out.println(result);
}
}
運行效率
DFS深度優(yōu)先搜索
class Solution {
private char[][] grid;
private boolean[][] visited; // 已經(jīng)瀏覽過的島嶼
private int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private int row; // 行
private int column; // 列
/**
* DFS
*
* @param grid
* @return
*/
public int numIslands(char[][] grid) {
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
this.grid = grid;
this.row = grid.length;
this.column = grid[0].length;
this.visited = new boolean[row][column];
int count = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if (visited[i][j] || grid[i][j] == '0') {
continue;
}
visit(i, j);
count ++;
}
}
return count;
}
/**
* DFS深度優(yōu)先搜索，找到一個就延四個方向深入搜索
*
* @param x
* @param y
*/
private void visit(int x, int y) {
visited[x][y] = true;
for (int i = 0; i < direction.length; i++) {
int dirX = direction[i][0];
int dirY = direction[i][1];
if (x + dirX < 0 || x + dirX >= row || y + dirY < 0 || y + dirY >= column
|| visited[x + dirX][y + dirY] || grid[x + dirX][y + dirY] == '0') {
continue;
}
visit(x + dirX, y + dirY);
}
}
}
運行效率
BFS廣度優(yōu)先搜索
class Solution {
private char[][] grid;
private boolean[][] visited;
private int row;
private int column;
// 存儲坐標(biāo)(x, y) 的計算值，需要能夠通過值得到 (x, y)
// value = x * row * column + y
// y = value % (row * column)
// x = (value - y) / (row * column)
private Queue<Integer> queue;
private int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private int count = 0;
/**
* BFS廣度優(yōu)先搜索
*
* @param grid
* @return
*/
public int numIslands(char[][] grid) {
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
this.grid = grid;
this.row = grid.length;
this.column = grid[0].length;
this.visited = new boolean[row][column];
this.queue = new LinkedList<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if (!visited[i][j] && grid[i][j] == '1') {
visited[i][j] = true;
queue.add(i * (row * column) + j);
visit();
count++;
}
}
}
return count;
}
/**
* BFS廣度優(yōu)先搜索
*/
private void visit() {
while (!queue.isEmpty()) {
int position = queue.remove();
int y = position % (row * column);
int x = (position - y) / (row * column);
for (int[] dir : direction) {
int dirX = dir[0];
int dirY = dir[1];
if (validPosition(x + dirX, y + dirY)
&& !visited[x + dirX][y + dirY] && grid[x + dirX][y + dirY] == '1') {
visited[x + dirX][y + dirY] = true;
queue.add((x + dirX) * row * column + (y + dirY));
}
}
}
}
/**
* 校驗坐標(biāo)是否合法
*
* @param x
* @param y
* @return
*/
private boolean validPosition(int x, int y) {
return x >= 0 && x < row && y >= 0 && y < column;
}
public static void main(String[] args) {
char[][] grid = {{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'}};
int result = new Solution().numIslands(grid);
System.out.println(result);
}
}
運行效率
