Python 中的岛屿数量
pythonserver side programmingprogramming更新于 2025/11/22 21:00:17
假设我们有一个网格，里面有少量的 0 和 1。我们必须计算岛屿的数量。岛屿是被水包围的地方，由水平或垂直连接相邻的陆地形成。我们可以假设网格的四个边都被水包围。
假设网格是这样的−
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 |
有三个岛屿。
为了解决这个问题，我们将遵循以下步骤 −
- 将有两种方法，一种方法用于计算岛屿数量，称为 numIslands() 和 makeWater()。makeWater() 将类似于 −
- 如果网格中的行数为 0，则返回 0
- n = 行数和 m := 列数，并且 ans := 0
- 对于 i 在 0 到 n 范围内 – 1
- 对于 j 在 0 到 m 范围内
- 如果 grid[i, j] = 1，则 ans := ans + 1
- makeWater(i, j, n, m, grid)
- 对于 j 在 0 到 m 范围内
- makeWater() 将采用索引 i、j、行数和列数 n 和 m 以及 grid
- 如果 i <0 或 j < 0 或 i >= n 或 j >= m，则从此方法返回
- 如果 grid[i, j] = 0，则返回，否则使 grid[i, j] := 0
- call makeWater(i + 1, j, n, m, grid)
- call makeWater(i, j + 1, n, m, grid)
让我们看看下面的实现以便更好地理解 −
示例
class Solution(object): def numIslands(self, grid): if len(grid) == 0: return 0 n= len(grid) m = len(grid[0]) ans = 0 for i in range(n): for j in range(m): if grid[i][j] == "1": ans+=1 self.make_water(i,j,n,m,grid) return ans def make_water(self,i,j,n,m,grid): if i<0 or j<0 or i>=n or j>=m: return if grid[i][j] == "0": return else: grid[i][j]="0" self.make_water(i+1,j,n,m,grid) self.make_water(i,j+1,n,m,grid) self.make_water(i-1,j,n,m,grid) self.make_water(i,j-1,n,m,grid) ob1 = Solution() print(ob1.numIslands([["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"], ["0","0","0","1","1"]]))
输入
[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
输出
3
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
