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

更新於：2020年11月10日

170 次瀏覽

啟動你的職業生涯

完成課程獲得認證

開始學習
廣告