資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python 程式：計算沒有捕食者的動物的最小數量
假設我們有一個名為 nums 的數字列表，其中 nums[i] 表示第 i 個動物的捕食者，如果沒有捕食者，則它將包含 -1。我們需要找到動物組的最小數量，使得任何動物都不與其直接或間接的捕食者在同一組中。
因此，如果輸入類似於 nums = [1, 2, -1, 4, 5, -1]，則輸出將為 3，因為我們可以有如下分組：[0, 3]，[1, 4]，[2, 5]。
為了解決這個問題，我們將遵循以下步驟 -
如果 A 為空，則
返回 0
adj := 一個空對映
vis := 一個新的集合
roots := 一個新的列表
對於 A 中的每個索引 i 和值 a，執行以下操作
如果 a 等於 -1，則
將 i 插入到 roots 的末尾
將 a 插入到 adj[i] 的末尾
將 i 插入到 adj[a] 的末尾
best := -infinity
對於 roots 中的每個根，執行以下操作
stk := 一個棧，並將 [root, 1] 插入其中
當 stk 不為空時，執行以下操作
(node, d) := stk 彈出的元素
如果 node 在 vis 中或 node 等於 -1，則
退出迴圈
best := best 和 d 的最大值
將 node 插入到 vis 中
對於 adj[node] 中的每個 u，執行以下操作
將 (u, d + 1) 推入 stk
返回 best
讓我們看看下面的實現，以便更好地理解 -
示例
from collections import defaultdict
class Solution:
def solve(self, A):
if not A:
return 0
adj = defaultdict(list)
vis = set()
roots = []
for i, a in enumerate(A):
if a == -1:
roots.append(i)
adj[i].append(a)
adj[a].append(i)
best = −float("inf")
for root in roots:
stk = [(root, 1)]
while stk:
node, d = stk.pop()
if node in vis or node == −1:
continue
best = max(best, d)
vis.add(node)
for u in adj[node]:
stk.append((u, d + 1))
return best
ob = Solution()
nums = [1, 2, −1, 4, 5, −1]
print(ob.solve(nums))輸入
[1, 2, −1, 4, 5, −1]
輸出
3
更新於: 2020-10-21
868 次檢視
廣告