用 Python 编写程序来查找最长的木棍的长度?
假设我们有一个整数木棍列表。列表中的每个元素代表一根有两个端点的木棍，这些值介于 1 到 6 之间。它们代表每个端点。如果任何一端相同，我们可以将两根木棍连接在一起。最终木棍的端点将是剩余的端点，并且其长度会增加。我们必须找到最长的棍子的长度。
因此，如果输入为 sticks = [ [2, 3], [2, 4], [3, 5], [6, 6] ]，则输出将为 3，因为我们可以连接 [2, 3] 和 [2, 4] 得到 [3, 4]，我们可以将其与 [3, 5] 连接得到 [4, 5]。
为了解决这个问题，我们将遵循以下步骤:
定义一个函数 dfs() 。这将获取节点、edge_idx 和已访问的集合
如果 edge_idx 不为空，则
如果 edge_idx 已访问，则
返回 0
将 edge_idx 标记为已访问
res := 0
对于 g[node] 中的每个 e_idx，执行
当 sticks[e_idx, 1] 与节点相同时，n_node := sticks[e_idx, 0]，否则 sticks[e_idx, 1]
res := res 和 1 + dfs(n_node, e_idx,访问过)
如果 edge_idx 非零，则
从访问中删除 edge_idx
返回 res
从主方法执行以下操作:
sticks := 包含 sticks 中所有 s 的列表(s[0], s[1])
vertices := 一个新集合
g := 一个空映射
对于 sticks 中的每个索引 i 和边，执行
将 i 插入 g[edge[0]]
将 i 插入g[edge[1]]
将 edge[0] 和 edge[1] 插入到顶点中
res := 0
对于顶点中的每个 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
