資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學在 Python 中查詢二維矩陣中不同島嶼的數量
假設我們有一個二進位制矩陣。我們必須計算其中的島嶼數量。島嶼是指被水包圍且透過水平或垂直連線相鄰陸地形成的地方。我們可以假設網格的所有四個邊緣都被水包圍。
假設網格如下：
| 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)
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): """ :type grid: List[List[str]] :rtype: int """ 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)
輸入
[["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"]]
輸出
3
更新於：2020年8月27日
455 次檢視
廣告