資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：逐塊新增方塊到網格中，計算島嶼數量
假設我們有一個無限大的水域網格。我們可以逐個向該網格新增陸地塊。我們有一個座標列表，稱為land_requests，其中每個座標都採用[r, c]的形式，其中r代表行，c代表列。我們必須找到一個列表，其中每個元素代表在新增land_requests中的每個陸地塊後存在的島嶼數量。
因此，如果輸入類似於land_requests = [[1, 1],[2, 4],[1, 2],[1, 4],[1, 3]]，則輸出將為[1, 2, 2, 2, 1]，原因如下：
為了解決這個問題，我們將遵循以下步驟：
d := 方向列表，例如[(−1, 0) ,(0, 1) ,(1, 0) ,(0, −1) ]
idx := 0
mp := 新建地圖
p := 新建列表
size := 新建列表
comp := 0
ans := 新建列表
定義函式 search()。它將接收 u
如果 u 等於 p[u]，則
返回 u
p[u] := search(p[u])
返回 p[u]
定義函式 connect()。它將接收 u, v
pu := search(u), pv := search(v)
如果 pu 等於 pv，則
返回
comp := comp − 1
如果 size[pu] >= size[pv]，則
p[pv] := pu
size[pu] := size[pu] + size[pv]
否則，
p[pu] := pv
size[pv] := size[pv] + size[pu]
在主方法中執行以下操作：
對於 land_requests 中的每個請求，執行以下操作：
(i, j) := request
mp[i, j] := idx
將 idx 插入 p 的末尾
將 1 插入 size 的末尾
idx := idx + 1
comp := comp + 1
對於 d 中的每個 k，執行以下操作：
ni := i + k[1]
nj := j + k[0]
如果 (ni, nj) 存在於 mp 中，則
connect(mp[(i, j)], mp[(ni, nj)])
將 comp 插入 ans 的末尾
返回 ans
讓我們來看下面的實現，以便更好地理解：
示例
d = [(−1, 0), (0, 1), (1, 0), (0, −1)] class Solution: def search(self, u): if u == self.p[u]: return u self.p[u] = self.search(self.p[u]) return self.p[u] def connect(self, u, v): pu = self.search(u) pv = self.search(v) if pu == pv: return self.comp −= 1 if self.size[pu] >= self.size[pv]: self.p[pv] = pu self.size[pu] += self.size[pv] else: self.p[pu] = pv self.size[pv] += self.size[pu] def solve(self, land_requests): self.idx = 0 self.mp = dict() self.p = [] self.size = [] self.comp = 0 ans = [] for request in land_requests: i, j = request self.mp[(i, j)] = self.idx self.p.append(self.idx) self.size.append(1) self.idx += 1 self.comp += 1 for k in d: ni = i + k[1] nj = j + k[0] if (ni, nj) in self.mp: self.connect(self.mp[(i, j)], self.mp[(ni, nj)]) ans.append(self.comp) return ans ob = Solution() land_requests = [[1, 1],[2, 4],[1, 2],[1, 4],[1, 3]] print(ob.solve(land_requests))
輸入
[[1, 1],[2, 4],[1, 2],[1, 4],[1, 3]]
輸出
[1, 2, 2, 2, 1]
122 次瀏覽
