数据结构
网络
关系数据库管理系统 (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 次浏览
