当前位置: 首页> 教育> 高考 > 广西建设网站_宁波网络设计有限公司有哪些_重庆seo技术教程博客_啥是网络推广

广西建设网站_宁波网络设计有限公司有哪些_重庆seo技术教程博客_啥是网络推广

时间:2025/7/11 20:04:26来源:https://blog.csdn.net/m0_46808930/article/details/147118874 浏览次数:0次
广西建设网站_宁波网络设计有限公司有哪些_重庆seo技术教程博客_啥是网络推广

目录

  • 题目内容
  • 样例1
  • 样例2
  • 思考思路
  • 算法思路
  • 实现代码(封装Class中)

题目内容

在这里插入图片描述

样例1

在这里插入图片描述
在这里插入图片描述

样例2

在这里插入图片描述
在这里插入图片描述

思考思路

题目让我们找出所有迭代次数最多的补丁版本,并且按字典序排列输出。迭代次数指的是从该版本到根节点的路径长度,而根节点的迭代次数是0,子节点是父节点次数+1。比如,样例1中的CN0010,它的父节点是BF0001,而BF0001的父节点是AZ0001,所以迭代次数是2次,是最大的。

首先,需要构建每个节点的深度。这里的数据结构是树,每个节点可能有多个子节点,但每个节点的父节点最多只有一个,因为题目中说过前序版本的个数<=1,且不会有环。所以可以建立一个父节点的映射,然后通过递归或者迭代的方式计算每个节点的深度

其次,计算每个节点的深度时,需要考虑父节点的存在与否。具体来说:
1、如果一个节点的父节点是NA,那么它的迭代次数是0。
2、如果父节点存在,则迭代次数是父节点的迭代次数 +1。
3、如果父节点不存在于父节点字典中(即父节点未被记录过),那么该节点的迭代次数是1。比如某个节点的父节点是某个不在输入中的版本,即输入中有X的父节点是Y,但Y没有出现在任何行中的当前版本或者父版本的位置,那么Y不在字典中,此时X的迭代次数是1。

所以,正确的处理步骤可能是:
1、建立父节点字典:每个当前版本的父节点被记录下来。例如,parent_map[current] = predecessor.
例如,对于输入中的每一行,current和predecessor。所以,parent_map[current] = predecessor.
2、对于每个节点(即parent_map中的所有键),计算它的迭代次数(深度)。同时,对于父节点不在parent_map中的情况,也需要处理。例如,当predecessor不是NA,并且不在parent_map中时,该predecessor的父节点视为NA,所以其迭代次数是0,当前节点的次数是1。
3、如果current的父节点是NA → 深度是0.
否则,父节点是p:
如果p的父节点存在(在parent_map中),则当前深度是p的深度 +1.
如果p的父节点不存在(即p不在parent_map中),则p的父节点是NA → p的深度是0 → current的深度是0+1=1.
这样,可以用一个字典depth_cache来保存各个节点的深度,避免重复计算。

紧接着,建立父节点字典的步骤如下:
1、收集所有非NA的字符串,包括current和predecessor。
2、建立parent_map,其中对于每个current,parent_map[current] = predecessor(以current当前版本为键,predecessor前序版本为值)。predecessor可能为NA或其他字符串。
3、对于所有补丁版本中的节点,如果不在parent_map的键中,则将其父节点设置为NA,并添加到parent_map中。

然后,可以用一个字典depth来保存每个节点的深度。然后,对于每个节点s,我们遍历其父链,直到找到NA,并记录路径长度。
不过,对于树结构来说,递归或迭代都可以。但为了避免递归可能导致的栈溢出(比如树深度很大),迭代方式更安全。
所以,可以采用
迭代方式
,或者使用带记忆化的递归

例如,记忆化递归:

depth_cache = {}def get_depth(node):if node == 'NA':return 0if node not in depth_cache:# 版本树映射关系,键到值的映射赋值给predecessorpredecessor = parent_map.get(node, 'NA')  # 但根据之前的处理,parent_map已经包含了所有补丁版本,所以不需要处理这种情况.if predecessor == 'NA':depth_cache[node] = 0else:depth_cache[node] = get_depth(predecessor) + 1return depth_cache[node]

然后,对于每个补丁版本s in S:

depth = get_depth(s)

记录最大深度,并收集所有具有该深度的节点。

最后,排序后输出。

这样,可以正确计算每个节点的深度。

现在,将所有步骤综合起来,编写代码:

# 读取输入:n = int(input())	 # 接下来读取的版本行数
lines = [input().strip() for _ in range(n)]# 收集补丁版本:s = set()		# 所有版本的集合
parent_map = {}for line in lines:current, predecessor = line.strip().split()s.add(current)if predecessor != 'NA':s.add(predecessor)parent_map[current] = predecessor

处理所有补丁版本,设置不在parent_map中的节点的父节点为NA:

for node in s:if node not in parent_map:parent_map[node] = 'NA'# 计算每个节点的深度:
depth_cache = {}
max_depth = -1
result = []for node in s:d = get_depth(node)if d > max_depth:max_depth = dresult = [node]elif d == max_depth:result.append(node)# 排序结果:
result.sort()
print(' '.join(result))

其中,get_depth函数如前所述。

算法思路

​​1、收集所有补丁版本​​:包括输入中的所有当前版本和前序版本(除去NA)。
2、​​建立父节点映射​​字典:记录每个当前版本的父节点,若父节点未在输入中出现,则其父节点设为NA。
​​3、计算每个节点的深度​​:使用递归和记忆化技术来高效计算每个节点的深度。
4、​​找出最大深度节点​​:遍历所有节点,找到深度最大的节点并排序输出。

实现代码(封装Class中)

class Solution:from typing import Listdef find_max_depth_versions(self, lines: List[str]) -> List[str]:# 收集所有非NA的版本号versions = set()parent_map = {}for line in lines:current, predecessor = line.strip().split()versions.add(current)if predecessor != 'NA':versions.add(predecessor)parent_map[current] = predecessor# 处理未在parent_map中的版本,设置其父节点为NAfor version in versions:if version not in parent_map:parent_map[version] = 'NA'# 计算每个版本的深度depth_cache = {}def get_depth(node):if node == 'NA':return 0if node not in depth_cache:predecessor = parent_map[node]depth_cache[node] = get_depth(predecessor) + 1 if predecessor != 'NA' else 0return depth_cache[node]max_depth = -1result = []for version in versions:current_depth = get_depth(version)if current_depth > max_depth:max_depth = current_depthresult = [version]elif current_depth == max_depth:result.append(version)# 按字典序排序result.sort()return result# 示例输入
def main():print("输入:")# 读取输入数据n = int(sys.stdin.readline())lines = [sys.stdin.readline().strip() for _ in range(n)]# 调用算法逻辑sol = Solution()result = sol.find_max_depth_versions(lines)# 输出结果print(f"输出:{' '.join(result)}")if __name__ == "__main__":import sysmain()

代码解释:
​​1、收集版本和建立父节点映射​​:遍历输入行,收集所有非NA的版本号,并建立每个当前版本到其前序版本的映射。
​​2、处理未记录的版本​​:对于出现在前序版本但未出现在当前版本的节点,设置其父节点为NA。
3、​​计算深度​​:使用递归和记忆化缓存来高效计算每个节点的深度。若父节点是NA,深度为0;否则递归计算父节点深度并加1。
​​4、找出最大深度节点​​:遍历所有版本,记录深度最大的节点,最后按字典序排序输出结果。

关键字:广西建设网站_宁波网络设计有限公司有哪些_重庆seo技术教程博客_啥是网络推广

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: