資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python中的島嶼數量
假設我們有一個網格，其中有一些0和一些1。我們需要計算島嶼的數量。島嶼是指被水包圍並透過水平或垂直連線相鄰陸地形成的地方。我們可以假設網格的所有四個邊緣都被水包圍。
假設網格如下：
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 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和網格
- 如果i < 0 或 j < 0 或 i >= n 或 j >= m，則從此方法返回
- 如果grid[i, j] = 0，則返回；否則，將grid[i, j]設定為0
- 呼叫makeWater(i + 1, j, n, m, grid)
- 呼叫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
更新於：2020年5月4日
2K+ 次瀏覽
廣告