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 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告