LeetCode 200、岛屿数量
LeetCode 200、岛屿数量
视频地址：LeetCode 200、岛屿数量
一、题目描述
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1
输入：
grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]输出：
1示例 2
输入：
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]输出：
3二、题目解析
三、参考代码
1、Java 代码
DFS解法
class Solution {
// 上下左右四个方向的数组
private final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// 构建DFS函数
private void DFS(char[][] grid, int i, int j, boolean[][] checkList) {
// 将该点标记为已经检查过
checkList[i][j] = true;
// 遍历上下左右四个方向的邻点坐标
for (int[] dir : DIRECTIONS) {
int next_i = i + dir[0];
int next_j = j + dir[1];
// 若近邻点满足三个条件：
// 1.没有越界 2. 近邻点尚未被检查过 3.近邻点也为陆地
if (next_i >= 0 && next_i < grid.length && next_j >= 0 && next_j < grid[0].length
&& !checkList[next_i][next_j] && grid[next_i][next_j] == '1') {
// 对近邻点进行DFS搜索
DFS(grid, next_i, next_j, checkList);
}
}
}
public int numIslands(char[][] grid) {
int x = grid.length; // 获得网格长
int y = grid[0].length; // 获得网格宽
int ans = 0; // 初始化答案为0
// 初始化数组checkList用于DFS遍历过程中的检查
// false表示尚未访问，true表示已经访问
boolean[][] checkList = new boolean[x][y];
// 对整个grid二维数组进行双重循环遍历
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
// 若该点为陆地且还没有进行过搜寻
if (grid[i][j] == '1' && !checkList[i][j]) {
// 可以进行DFS
DFS(grid, i, j, checkList);
// 做完DFS，连通块数量+1，更新答案
ans++;
}
}
}
return ans;
}
}BFS解法
class Solution {
// 上下左右四个方向的数组
private final int[][] DIRECTIONS = {{0,1}, {1,0}, {0,-1}, {-1,0}};
public int numIslands(char[][] grid) {
int xLen = grid.length; // 获得网格长
int yLen = grid[0].length; // 获得网格宽
int ans = 0; // 初始化陆地数目为0
// 初始化和grid一样大小的二维数组checkList用于BFS遍历过程中的检查
int[][] checkList = new int[xLen][yLen];
// 双重遍历grid数组
for (int i = 0; i < xLen; i++) {
for (int j = 0; j < yLen; j++) {
// 若该点为陆地且还没有进行过搜寻
// 找到了一个BFS搜索的起始位置(i,j)
if (grid[i][j] == '1' && checkList[i][j] == 0) {
// 对于该片连通块，构建一个队列，初始化包含该点
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
// 修改checkList[i][j]为1，表示该点已经搜寻过
checkList[i][j] = 1;
// 进行BFS，退出循环的条件是队列为空
while (!queue.isEmpty()) {
// 弹出队头的点(x,y)，搜寻该点上下左右的近邻点
int[] current = queue.poll();
int x = current[0];
int y = current[1];
// 遍历(x,y)上下左右的四个方向的近邻点
for (int[] dir : DIRECTIONS) {
int xNext = x + dir[0];
int yNext = y + dir[1];
// 如果近邻点满足三个条件
if (xNext >= 0 && xNext < xLen && yNext >= 0 && yNext < yLen
&& checkList[xNext][yNext] == 0 && grid[xNext][yNext] == '1') {
// 对近邻点做两件事：
// 1. 入队 2. 标记为已检查过
queue.offer(new int[]{xNext, yNext});
checkList[xNext][yNext] = 1;
}
}
}
// 连通块的数量+1
ans++;
}
}
}
return ans;
}
}**2、**C++ 代码
DFS解法
class Solution {
private:
// 上下左右四个方向的数组
vector<pair<int, int>> DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// 构建DFS函数
void DFS(vector<vector<char>>& grid, int i, int j, vector<vector<bool>>& checkList) {
// 将该点标记为已经检查过
checkList[i][j] = true;
// 遍历上下左右四个方向的邻点坐标
for (auto& dir : DIRECTIONS) {
int next_i = i + dir.first;
int next_j = j + dir.second;
// 若近邻点满足三个条件：
// 1.没有越界 2. 近邻点尚未被检查过 3.近邻点也为陆地
if (next_i >= 0 && next_i < grid.size() && next_j >= 0 && next_j < grid[0].size()
&& !checkList[next_i][next_j] && grid[next_i][next_j] == '1') {
// 对近邻点进行DFS搜索
DFS(grid, next_i, next_j, checkList);
}
}
}
public:
int numIslands(vector<vector<char>>& grid) {
int x = grid.size(); // 获得网格长
int y = grid[0].size(); // 获得网格宽
int ans = 0; // 初始化答案为0
// 初始化数组checkList用于DFS遍历过程中的检查
// false表示尚未访问，true表示已经访问
vector<vector<bool>> checkList(x, vector<bool>(y, false));
// 对整个grid二维数组进行双重循环遍历
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
// 若该点为陆地且还没有进行过搜寻
if (grid[i][j] == '1' && !checkList[i][j]) {
// 可以进行DFS
DFS(grid, i, j, checkList);
// 做完DFS，连通块数量+1，更新答案
ans++;
}
}
}
return ans;
}
};BFS解法
class Solution {
private:
// 上下左右四个方向的数组
vector<pair<int, int>> DIRECTIONS = {{0,1}, {1,0}, {0,-1}, {-1,0}};
public:
int numIslands(vector<vector<char>>& grid) {
int xLen = grid.size(); // 获得网格长
int yLen = grid[0].size(); // 获得网格宽
int ans = 0; // 初始化陆地数目为0
// 初始化和grid一样大小的二维数组checkList用于BFS遍历过程中的检查
vector<vector<int>> checkList(xLen, vector<int>(yLen, 0));
// 双重遍历grid数组
for (int i = 0; i < xLen; i++) {
for (int j = 0; j < yLen; j++) {
// 若该点为陆地且还没有进行过搜寻
// 找到了一个BFS搜索的起始位置(i,j)
if (grid[i][j] == '1' && checkList[i][j] == 0) {
// 对于该片连通块，构建一个队列，初始化包含该点
queue<pair<int, int>> q;
q.push({i, j});
// 修改checkList[i][j]为1，表示该点已经搜寻过
checkList[i][j] = 1;
// 进行BFS，退出循环的条件是队列为空
while (!q.empty()) {
// 弹出队头的点(x,y)，搜寻该点上下左右的近邻点
int x = q.front().first;
int y = q.front().second;
q.pop();
// 遍历(x,y)上下左右的四个方向的近邻点
for (auto& dir : DIRECTIONS) {
int xNext = x + dir.first;
int yNext = y + dir.second;
// 如果近邻点满足三个条件
if (xNext >= 0 && xNext < xLen && yNext >= 0 && yNext < yLen
&& checkList[xNext][yNext] == 0 && grid[xNext][yNext] == '1') {
// 对近邻点做两件事：
// 1. 入队 2. 标记为已检查过
q.push({xNext, yNext});
checkList[xNext][yNext] = 1;
}
}
}
// 连通块的数量+1
ans++;
}
}
}
return ans;
}
};3、Python 代码
DFS解法
# 题目：LC200. 岛屿数量
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：DFS
# 代码看不懂的地方，请直接在群上提问
# 初始化上下左右四个方向的数组
DIRECTIONS = [(0,1), (1,0), (0,-1), (-1,0)]
class Solution:
# 构建DFS函数
def DFS(self, grid, i, j, checkList):
# 将该点标记为已经检查过
checkList[i][j] = True
# 遍历上下左右四个方向的邻点坐标
for dx, dy in DIRECTIONS:
next_i, next_j = i + dx, j + dy
# 若近邻点满足三个条件：
# 1.没有越界 2. 近邻点尚未被检查过 3.近邻点也为陆地
if ((0 <= next_i < self.x and 0 <= next_j < self.y) and checkList[next_i][next_j] == False
and grid[next_i][next_j] == "1"):
# 对近邻点(ni, nj)进行DFS搜索
self.DFS(grid, next_i, next_j, checkList)
def numIslands(self, grid: List[List[str]]) -> int:
self.x = len(grid) # 获得网格长
self.y = len(grid[0]) # 获得网格宽
ans = 0 # 初始化答案为0
# 初始化数组checkList用于DFS遍历过程中的检查
# 0表示尚未访问，1表示已经访问
checkList = [[False] * self.y for _ in range(self.x)]
# 对整个grid二维数组进行双重循环遍历
for i in range(self.x):
for j in range(self.y):
# 若该点为陆地且还没有进行过搜寻
if grid[i][j] == "1" and checkList[i][j] == False:
# 可以进行DFS
self.DFS(grid, i, j, checkList)
# 做完DFS，连通块数量+1，更新答案
ans += 1
return ansBFS解法
# 题目：LC200. 岛屿数量
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：BFS
# 代码看不懂的地方，请直接在群上提问
# 初始化上下左右四个方向的数组
DIRECTIONS = [(0,1), (1,0), (0,-1), (-1,0)]
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
x_len, y_len = len(grid), len(grid[0]) # 获得网格长宽
ans = 0 # 初始化陆地数目为0
# 初始化和grid一样大小的二维数组checkList用于DFS遍历过程中的检查
checkList = [[0] * y_len for _ in range(x_len)]
# 双重遍历grid数组
for i in range(x_len):
for j in range(y_len):
# 若该点为陆地且还没有进行过搜寻
# 找到了一个BFS搜索的起始位置(i,j)
if grid[i][j] == "1" and checkList[i][j] == 0:
# 对于该片连通块，构建一个队列，初始化包含该点
q = deque()
q.append((i,j))
# 修改checkList[i][j]为1，表示该点已经搜寻过
checkList[i][j] = 1
# 进行BFS，退出循环的条件是队列为空
while len(q) > 0:
# 弹出栈队头的点(x,y) 搜寻该点上下左右的近邻点
x, y = q.popleft()
# 遍历(x,y)上下左右的四个方向的近邻点
for dx, dy in DIRECTIONS:
x_next, y_next = x+dx, y+dy
# 如果近邻点满足三个条件
if (0 <= x_next < x_len and 0 <= y_next < y_len and checkList[x_next][y_next] == 0
and grid[x_next][y_next] == "1"):
# 对近邻点做两件事：
# 1. 入队 2. 标记为已检查过
q.append((x_next, y_next))
checkList[x_next][y_next] = 1
# 连通块的数量+1
ans += 1
return ans