Python程序：查找构成最长链的盒子数量？

假设我们有一组盒子，每个条目都有两个值 [起始，结束] (起始 < 结束)。如果一个盒子的结束值等于另一个盒子的起始值，则可以连接这两个盒子。我们必须找到最长盒子链的长度。

因此，如果输入类似于 blocks = [ [4, 5], [5, 6], [4, 8], [1, 2], [2, 4] ]，则输出为 4，因为我们可以形成链： [1, 2], [2, 4], [4, 5], [5, 6]

为了解决这个问题，我们将遵循以下步骤

• 如果盒子为空，则

  • 返回 0

• 对盒子列表进行排序

• dic := 一个空映射

• 对于 boxes 中的每个起始值 s 和结束值 e，执行以下操作：

  • dic[e] := dic[e] 和 dic[s] + 1 的最大值

• 返回 dic 所有值的列表的最大值

让我们看看下面的实现，以便更好地理解

示例

 在线演示

import collections

class Solution:
   def solve(self, boxes):
      if not boxes:
         return 0
      boxes.sort()
      dic = collections.defaultdict(int)
      for s, e in boxes:
         dic[e] = max(dic[e], dic[s] + 1)
      return max(dic.values())

ob = Solution()
boxes = [
   [4, 5],
   [5, 6],
   [4, 8],
   [1, 2],
   [2, 4]
]
print(ob.solve(boxes))

输入

[[4, 5],
[5, 6],
[4, 8],
[1, 2],
[2, 4] ]

输出

4

Arnab Chakraborty

更新于：2020年11月10日

170 次浏览

启动你的职业生涯

完成课程获得认证

开始学习