程序查找在Python中形成最长链的盒子数量？

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个盒子列表，这里每个条目都有两个值[start，end]（start <end）。如果一个盒子的结尾等于另一个盒子的开头，我们可以将两个盒子连接起来。我们必须找到最长的盒子链的长度。

因此，如果输入就像块= [[4，5]，[5，6]，[4，8]，[1、2]，[2，4]]，那么输出将是4，因为我们可以形成链：[1、2]，[2、4]，[4、5]，[5、6]

为了解决这个问题，我们将按照以下步骤操作：

• 如果盒子是空的，那么

• 返回0

• 排序列表框

• dic：=一个空的映射

• 对于框中的每个开始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

以上是 程序查找在Python中形成最长链的盒子数量？ 的全部内容， 来源链接： utcz.com/z/326424.html