Python程式：如何找到最長可能的棍子的長度？

假設我們有一個整數列表sticks。列表中的每個元素代表一根有兩個端點的棍子，這些值在1到6之間。它們表示每個端點。如果兩根棍子的任何一個端點相同，我們就可以將它們連線在一起。生成的棍子的端點將是剩餘的端點，並且長度會增加。我們必須找到最長可能的棍子的長度。

所以，如果輸入類似於sticks = [ [2, 3], [2, 4], [3, 5], [6, 6] ]，則輸出將是3，因為我們可以將[2, 3]和[2, 4]連線起來得到[3, 4]，然後我們可以將其與[3, 5]連線起來得到[4, 5]。

為了解決這個問題，我們將遵循以下步驟

  • 定義一個函式dfs()。它將接收節點、邊索引和一個集合visited作為引數。

  • 如果edge_idx不為空，則

    • 如果edge_idx已被訪問，則

      • 返回0

    • 標記edge_idx為已訪問

    • res := 0

    • 對於g[node]中的每個e_idx，執行以下操作：

      • 當sticks[e_idx, 1]與node相同時，n_node := sticks[e_idx, 0]，否則n_node := sticks[e_idx, 1]

      • res := res和1 + dfs(n_node, e_idx, visited)中的最大值

    • 如果edge_idx不為零，則

      • 從visited中刪除edge_idx

    • 返回res

  • 從主方法執行以下操作

  • sticks := 所有s in sticks (s[0], s[1])的列表

  • vertices := 一個新的集合

  • g := 一個空對映

  • 對於每個索引i和sticks中的邊，執行以下操作：

    • 將i插入到g[edge[0]]中

    • 將i插入到g[edge[1]]中

    • 將edge[0]和edge[1]插入到vertices中

  • res := 0

  • 對於vertices中的每個v，執行以下操作：

    • res := res和dfs(v, null, 和空集合)中的最大值

  • 返回res - 1

讓我們檢視以下實現以獲得更好的理解

示例

 即時演示

from collections import defaultdict

class Solution:
   def solve(self, sticks):
      def dfs(node, edge_idx, visited):
         if edge_idx is not None:
            if edge_idx in visited:
               return 0
            visited.add(edge_idx)
         res = 0
         for e_idx in g[node]:
            n_node = sticks[e_idx][0] if sticks[e_idx][1] == node else sticks[e_idx][1]
            res = max(res, 1 + dfs(n_node, e_idx, visited))
         if edge_idx:
            visited.remove(edge_idx)
         return res

      sticks = [(s[0], s[1]) for s in sticks]
      vertices = set()
      g = defaultdict(set)
      for i, edge in enumerate(sticks):
         g[edge[0]].add(i)
         g[edge[1]].add(i)
         vertices.add(edge[0])
         vertices.add(edge[1])
      res = 0
      for v in vertices:
         res = max(res, dfs(v, None, set()))
      return res - 1

ob = Solution()
sticks = [
   [2, 3],
   [2, 4],
   [3, 5],
   [6, 6]
]
print(ob.solve(sticks))

輸入

sticks = [ [2, 3], [2, 4], [3, 5], [6, 6] ]

輸出

3

更新於: 2020年11月10日

209 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告