Kimi LeetCode 3425. 最长特殊路径 Python3实现

📅 2026/6/30 22:44:28 👁️ 次浏览

以下是 LeetCode 3425. 最长特殊路径的 Python3 实现。---解题思路这道题的核心是 DFS 滑动窗口树上的双指针时间复杂度 O(n)空间复杂度 O(n)。关键观察1. 特殊路径的定义路径上所有节点的值互不相同。这等价于无重复元素的最长子数组问题在树上的扩展。2. 为什么用滑动窗口从根节点出发 DFS维护当前路径上的节点值集合。当遇到重复值时需要收缩左边界直到没有重复值为止。这和数组上的无重复元素最长子数组问题本质相同。3. 具体实现- prefix 数组记录从根到当前节点的路径长度前缀和prefix[i] 表示深度为 i 的节点到根的路径长度- lastSeenDepth字典记录每个节点值最后出现的深度- leftBoundary当前窗口的左边界深度确保 [leftBoundary, currentDepth] 内无重复值4. 路径长度计算length prefix[currentDepth] - prefix[leftBoundary]节点数 currentDepth - leftBoundary---Python3 完整代码pythonfrom typing import Listclass Solution:def longestSpecialPath(self, edges: List[List[int]], nums: List[int]) - List[int]:n len(nums)# 建图邻接表存储 (邻居节点, 边权)graph [[] for _ in range(n)]for u, v, w in edges:graph[u].append((v, w))graph[v].append((u, w))# 答案变量maxLength 0minNodes 1# prefix[i] 从根节点到深度为 i 的节点的路径长度prefix [0]# lastSeenDepth[val] 节点值 val 最后出现的深度lastSeenDepth {}def dfs(u: int, prev: int, leftBoundary: int) - None:nonlocal maxLength, minNodes# 记录当前节点值之前出现的深度prevDepth lastSeenDepth.get(nums[u], 0)# 更新当前节点值的最后出现深度lastSeenDepth[nums[u]] len(prefix)# 收缩左边界确保 [leftBoundary, currentDepth] 内无重复值leftBoundary max(leftBoundary, prevDepth)# 计算当前路径的长度和节点数length prefix[-1] - prefix[leftBoundary]nodes len(prefix) - leftBoundary# 更新答案优先更长路径长度相同时更少节点数if length maxLength or (length maxLength and nodes minNodes):maxLength lengthminNodes nodes# 遍历所有子节点for v, w in graph[u]:if v prev:continue# 将子节点加入路径prefix.append(prefix[-1] w)dfs(v, u, leftBoundary)prefix.pop() # 回溯# 回溯恢复当前节点值的最后出现深度lastSeenDepth[nums[u]] prevDepth# DFS 从根节点 0 开始dfs(0, -1, 0)return [maxLength, minNodes]---测试验证输入输出说明edges[[0,1,2],[1,2,3],[1,3,5],[1,4,4],[2,5,6]], nums[2,1,2,1,3,1] [6, 2] 最长路径 2→5长度62个节点和 0→1→4长度63个节点取最少节点数 2edges[[1,0,8]], nums[2,2] [0, 1] 两节点值相同只能选单个节点edges[], nums[5] [0, 1] 单节点edges[[0,1,1],[1,2,1],[2,3,1]], nums[1,2,3,4] [3, 4] 链状树无重复值edges[[0,1,1],[0,2,1],[1,3,1],[1,4,1]], nums[1,2,1,3,4] [2, 3] 有重复值需要收缩窗口下载完整代码[leetcode_3425.py](sandbox:///mnt/agents/output/leetcode_3425.py)

相关新闻