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

Arnab Chakraborty

更新于: 2020年11月10日

209 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习