200. 岛屿数量
难度中等1021
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
代码语言：javascript复制输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1详细解析
DFS1
代码语言：javascript复制class Solution {
public int numIslands(char[][] grid) {
//边界条件判断
if (grid == null || grid.length == 0)
return 0;
//统计岛屿的个数
int count = 0;
//两个for循环遍历每一个格子
for (int i = 0; i < grid.length; i )
for (int j = 0; j < grid[0].length; j ) {
//只有当前格子是1才开始计算
if (grid[i][j] == '1') {
//如果当前格子是1，岛屿的数量加1
count ;
//然后通过dfs把当前格子的上下左右4
//个位置为1的都要置为0，因为他们是连着
//一起的算一个岛屿，
dfs(grid, i, j);
}
}
//最后返回岛屿的数量
return count;
}
//这个方法会把当前格子以及他邻近的为1的格子都会置为1
public void dfs(char[][] grid, int i, int j) {
//边界条件判断，不能越界
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0')
return;
//把当前格子置为0，然后再从他的上下左右4个方向继续遍历
grid[i][j] = '0';
dfs(grid, i - 1, j);//上
dfs(grid, i 1, j);//下
dfs(grid, i, j 1);//左
dfs(grid, i, j - 1);//右
}
}DFS2
代码语言：javascript复制package com.nie.o3;/* * *@auth wenzhao *@date 2021/3/8 21:23 */
public class LEE200 {
private static final int[][] DIR = {
{
-1, 0}, {
0, 1}, {
0, -1,}, {
1, 0}};
private boolean[][] visited;
private int rows;
private int cols;
private char[][] grid;
public int numIsland(char[][] grid) {
this.rows = grid.length;
this.cols = grid[0].length;
if (rows == 0) {
return 0;
}
this.visited = new boolean[rows][cols];
int count = 0;
this.grid = grid;
for (int i = 0; i < rows; i ) {
for (int j = 0; j < cols; j ) {
if (grid[i][j] == '1' & !visited[i][j]) {
dfs(i, j);
count ;
}
}
}
return count;
}
private void dfs(int i, int j) {
visited[i][j] = true;
for (int k = 0; k < DIR.length; k ) {
int newX = i DIR[k][0];
int newY = j DIR[k][1];
// 如果不越界、还是陆地、没有被访问过
if (inArea(newX, newY) && grid[newX][newY] == '1' && !visited[newX][newY]) {
dfs(newX, newY);
}
}
}
private boolean inArea(int x, int y) {
return x >= 0 && x < rows && y >= 0 && y < cols;
}
}并查集
代码语言：javascript复制public class Solution {
private int rows;
private int cols;
public int numIslands(char[][] grid) {
rows = grid.length;
if (rows == 0) {
return 0;
}
cols = grid[0].length;
// 空地的数量
int spaces = 0;
UnionFind unionFind = new UnionFind(rows * cols);
int[][] directions = {
{
1, 0}, {
0, 1}};
for (int i = 0; i < rows; i ) {
for (int j = 0; j < cols; j ) {
if (grid[i][j] == '0') {
spaces ;
} else {
// 此时 grid[i][j] == '1'
for (int[] direction : directions) {
int newX = i direction[0];
int newY = j direction[1];
// 先判断坐标合法，再检查右边一格和下边一格是否是陆地
if (newX < rows && newY < cols && grid[newX][newY] == '1') {
unionFind.union(getIndex(i, j), getIndex(newX, newY));
}
}
}
}
}
return unionFind.getCount() - spaces;
}
private int getIndex(int i, int j) {
return i * cols j;
}
private class UnionFind {
/** * 连通分量的个数 */
private int count;
private int[] parent;
public int getCount() {
return count;
}
public UnionFind(int n) {
this.count = n;
parent = new int[n];
for (int i = 0; i < n; i ) {
parent[i] = i;
}
}
private int find(int x) {
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public void union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot == yRoot) {
return;
}
parent[xRoot] = yRoot;
count--;
}
}
}
