class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
}
};
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
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] 的值为 '0' 或 '1'原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 4.7 MB, 提交时间: 2023-09-28 15:05:39
type UnionFindSet struct {
Parents []int // 每个结点的顶级节点
SetCount int // 连通分量的个数
}
func (u *UnionFindSet) Init(grid [][]byte) {
row := len(grid)
col := len(grid[0])
count := row*col
u.Parents = make([]int, count)
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
u.Parents[i*col+j] = i*col+j
if grid[i][j] == '1' {
u.SetCount++
}
}
}
}
func (u *UnionFindSet) Find(node int) int {
if u.Parents[node] == node {
return node
}
root := u.Find(u.Parents[node])
u.Parents[node] = root
return root
}
func (u *UnionFindSet) Union(node1 int, node2 int) {
root1 := u.Find(node1)
root2 := u.Find(node2)
if root1 == root2 {
return
}
if root1 < root2 {
u.Parents[root1] = root2
} else {
u.Parents[root2] = root1
}
u.SetCount--
}
// 心得：并查集是一种搜索算法（针对聚合的）
func numIslands(grid [][]byte) int {
// 创建并初始化并查集
u := &UnionFindSet{}
row := len(grid)
col := len(grid[0])
u.Init(grid)
// 根据grid建立相应的并查集，并统计连通分量个数【每连接一次进行减一】
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
if grid[i][j] == '1' {
// 如果周边四个方向也是1就进行union
if i - 1 >= 0 && grid[i-1][j] == '1' {
u.Union(i*col+j, (i-1)*col+j)
}
if i + 1 < row && grid[i+1][j] == '1' {
u.Union(i*col+j, (i+1)*col+j)
}
if j - 1 >= 0 && grid[i][j-1] == '1' {
u.Union(i*col+j, i*col+(j-1))
}
if j + 1 < col && grid[i][j+1] == '1' {
u.Union(i*col+j, i*col+(j+1))
}
grid[i][j] = '0'
}
}
}
// 返回结果
return u.SetCount
}
golang 解法, 执行用时: 4 ms, 内存消耗: 3.6 MB, 提交时间: 2023-09-28 15:05:26
func numIslands(grid [][]byte) int {
res := 0
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[i]); j++ {
if grid[i][j] == '1' {
res++
dfs(grid, i, j)
}
}
}
return res
}
func dfs(grid [][]byte, r, c int) {
h, w := len(grid), len(grid[0])
if r < 0 || r >= h || c < 0 || c >= w {
return
}
if grid[r][c] == '0' {
return
}
grid[r][c] = '0'
dfs(grid, r-1, c)
dfs(grid, r+1, c)
dfs(grid, r, c-1)
dfs(grid, r, c+1)
}
golang 解法, 执行用时: 4 ms, 内存消耗: 3.8 MB, 提交时间: 2023-09-28 15:04:59
func dfs(grid [][]byte, i, j int, visited [][]bool) {
m, n := len(grid), len(grid[0])
//递归出口 越界 或者遇到海水
if i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == '0' {
return
}
//递归出口 已经遍历过(i,j)
if visited[i][j] {
return
}
//遍历位置(i,j)
visited[i][j] = true
dfs(grid, i-1, j, visited)
dfs(grid, i+1, j, visited)
dfs(grid, i, j-1, visited)
dfs(grid, i, j+1, visited)
}
// dfs
func numIslands(grid [][]byte) int {
res := 0
m, n := len(grid), len(grid[0])
//二维切片的声明方法
visited := make([][]bool, m)
for i := range visited {
visited[i] = make([]bool, n)
}
//遍历二维数组
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
//满足条件
if grid[i][j] == '1' && visited[i][j] == false {
res++
dfs(grid, i, j, visited)
}
}
}
return res
}
python3 解法, 执行用时: 188 ms, 内存消耗: 29.1 MB, 提交时间: 2023-09-28 15:04:04
class UnionFind:
def __init__(self, grid):
m, n = len(grid), len(grid[0])
self.count = 0
self.parent = [-1] * (m * n)
self.rank = [0] * (m * n)
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
self.parent[i * n + j] = i * n + j
self.count += 1
def find(self, i):
if self.parent[i] != i:
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
def union(self, x, y):
rootx = self.find(x)
rooty = self.find(y)
if rootx != rooty:
if self.rank[rootx] < self.rank[rooty]:
rootx, rooty = rooty, rootx
self.parent[rooty] = rootx
if self.rank[rootx] == self.rank[rooty]:
self.rank[rootx] += 1
self.count -= 1
def getCount(self):
return self.count
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
uf = UnionFind(grid)
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
grid[r][c] = "0"
for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
uf.union(r * nc + c, x * nc + y)
return uf.getCount()
python3 解法, 执行用时: 108 ms, 内存消耗: 26.3 MB, 提交时间: 2023-09-28 15:03:46
class Solution:
def dfs(self, grid, r, c):
grid[r][c] = 0
nr, nc = len(grid), len(grid[0])
for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
self.dfs(grid, x, y)
# dfs
def numIslands2(self, grid: List[List[str]]) -> int:
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
num_islands += 1
self.dfs(grid, r, c)
return num_islands
# bfs
def numIslands(self, grid: List[List[str]]) -> int:
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
num_islands += 1
grid[r][c] = "0"
neighbors = collections.deque([(r, c)])
while neighbors:
row, col = neighbors.popleft()
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
neighbors.append((x, y))
grid[x][y] = "0"
return num_islands
cpp 解法, 执行用时: 32 ms, 内存消耗: 12.4 MB, 提交时间: 2023-09-28 15:02:59
class Solution {
private:
void dfs(vector<vector<char>>& grid, int r, int c) {
int nr = grid.size();
int nc = grid[0].size();
grid[r][c] = '0';
if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
}
public:
// dfs
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size();
if (!nr) return 0;
int nc = grid[0].size();
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}
return num_islands;
}
// bfs
int numIslands2(vector<vector<char>>& grid) {
int nr = grid.size();
if (!nr) return 0;
int nc = grid[0].size();
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
grid[r][c] = '0';
queue<pair<int, int>> neighbors;
neighbors.push({r, c});
while (!neighbors.empty()) {
auto rc = neighbors.front();
neighbors.pop();
int row = rc.first, col = rc.second;
if (row - 1 >= 0 && grid[row-1][col] == '1') {
neighbors.push({row-1, col});
grid[row-1][col] = '0';
}
if (row + 1 < nr && grid[row+1][col] == '1') {
neighbors.push({row+1, col});
grid[row+1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col-1] == '1') {
neighbors.push({row, col-1});
grid[row][col-1] = '0';
}
if (col + 1 < nc && grid[row][col+1] == '1') {
neighbors.push({row, col+1});
grid[row][col+1] = '0';
}
}
}
}
}
return num_islands;
}
};
cpp 解法, 执行用时: 32 ms, 内存消耗: 15.7 MB, 提交时间: 2023-09-28 15:01:32
class UnionFind {
public:
UnionFind(vector<vector<char>>& grid) {
count = 0;
int m = grid.size();
int n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
parent.push_back(i * n + j);
++count;
}
else {
parent.push_back(-1);
}
rank.push_back(0);
}
}
}
int find(int i) {
if (parent[i] != i) {
parent[i] = find(parent[i]);
}
return parent[i];
}
void unite(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
if (rank[rootx] < rank[rooty]) {
swap(rootx, rooty);
}
parent[rooty] = rootx;
if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
--count;
}
}
int getCount() const {
return count;
}
private:
vector<int> parent;
vector<int> rank;
int count;
};
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size();
if (!nr) return 0;
int nc = grid[0].size();
UnionFind uf(grid);
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
grid[r][c] = '0';
if (r - 1 >= 0 && grid[r-1][c] == '1') uf.unite(r * nc + c, (r-1) * nc + c);
if (r + 1 < nr && grid[r+1][c] == '1') uf.unite(r * nc + c, (r+1) * nc + c);
if (c - 1 >= 0 && grid[r][c-1] == '1') uf.unite(r * nc + c, r * nc + c - 1);
if (c + 1 < nc && grid[r][c+1] == '1') uf.unite(r * nc + c, r * nc + c + 1);
}
}
}
return uf.getCount();
}
};
java 解法, 执行用时: 10 ms, 内存消耗: 46.4 MB, 提交时间: 2023-09-28 15:01:14
class Solution {
class UnionFind {
int count;
int[] parent;
int[] rank;
public UnionFind(char[][] grid) {
count = 0;
int m = grid.length;
int n = grid[0].length;
parent = new int[m * n];
rank = new int[m * n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
parent[i * n + j] = i * n + j;
++count;
}
rank[i * n + j] = 0;
}
}
}
public int find(int i) {
if (parent[i] != i) parent[i] = find(parent[i]);
return parent[i];
}
public void union(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
if (rank[rootx] > rank[rooty]) {
parent[rooty] = rootx;
} else if (rank[rootx] < rank[rooty]) {
parent[rootx] = rooty;
} else {
parent[rooty] = rootx;
rank[rootx] += 1;
}
--count;
}
}
public int getCount() {
return count;
}
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
UnionFind uf = new UnionFind(grid);
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
grid[r][c] = '0';
if (r - 1 >= 0 && grid[r-1][c] == '1') {
uf.union(r * nc + c, (r-1) * nc + c);
}
if (r + 1 < nr && grid[r+1][c] == '1') {
uf.union(r * nc + c, (r+1) * nc + c);
}
if (c - 1 >= 0 && grid[r][c-1] == '1') {
uf.union(r * nc + c, r * nc + c - 1);
}
if (c + 1 < nc && grid[r][c+1] == '1') {
uf.union(r * nc + c, r * nc + c + 1);
}
}
}
}
return uf.getCount();
}
}
java 解法, 执行用时: 2 ms, 内存消耗: 46.3 MB, 提交时间: 2023-09-28 15:00:55
class Solution {
void dfs(char[][] grid, int r, int c) {
int nr = grid.length;
int nc = grid[0].length;
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
// dfs
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}
return num_islands;
}
// bfs
public int numIslands2(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
grid[r][c] = '0';
Queue<Integer> neighbors = new LinkedList<>();
neighbors.add(r * nc + c);
while (!neighbors.isEmpty()) {
int id = neighbors.remove();
int row = id / nc;
int col = id % nc;
if (row - 1 >= 0 && grid[row-1][col] == '1') {
neighbors.add((row-1) * nc + col);
grid[row-1][col] = '0';
}
if (row + 1 < nr && grid[row+1][col] == '1') {
neighbors.add((row+1) * nc + col);
grid[row+1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col-1] == '1') {
neighbors.add(row * nc + col-1);
grid[row][col-1] = '0';
}
if (col + 1 < nc && grid[row][col+1] == '1') {
neighbors.add(row * nc + col+1);
grid[row][col+1] = '0';
}
}
}
}
}
return num_islands;
}
}
python3 解法, 执行用时: 120 ms, 内存消耗: 23.6 MB, 提交时间: 2022-07-20 10:28:28
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
nr, nc = len(grid), len(grid[0])
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
num_islands += 1
grid[r][c] = "0"
neighbors = deque([(r, c)])
while neighbors:
row, col = neighbors.popleft()
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
neighbors.append((x, y))
grid[x][y] = "0"
return num_islands