标签:
难度: Hard
标签:
难度: Hard
运行时间: 204 ms
内存: 25.1 MB
from typing import List from collections import defaultdict, deque class Solution: def evolutionaryRecord(self, parents: List[int]) -> str: """ :param parents: :return: """ m1 = defaultdict(list) for k, v in enumerate(parents): m1[v].append(k) def build_str(start): clist = m1.get(start, []) if len(clist) == 0: return "" anslist = ["0"+build_str(i)+'1' for i in clist] anslist.sort() return "".join(anslist) ret = build_str(m1.get(-1)[0]) return ret[:ret.rfind('0')+1]
题解采用深度优先搜索(DFS)的方法来构建演化序列。首先,使用一个字典 `m1` 来存储每个节点及其对应的子节点列表。这是通过遍历 `parents` 数组得到的,其中每个元素的索引表示节点,值表示其父节点。对于根节点(其父节点为 `-1`),启动DFS过程。在DFS函数 `build_str` 中,对于每个节点,首先获取其所有子节点,并对每个子节点递归调用 `build_str`。每次递归返回的字符串表示该子节点及其所有后代的演化过程。对这些字符串进行排序,确保按字典序最小方式合并。每个子节点序列前后分别添加 '0' 和 '1',以模拟在该节点下添加新子节点和回退到父节点的操作。最后,返回构建的字符串,保留到最后一个 '0' 以确保不会多余地回退到根节点之外。
时间复杂度: O(n log n)
空间复杂度: O(n)
from typing import List from collections import defaultdict, deque class Solution: def evolutionaryRecord(self, parents: List[int]) -> str: # 创建一个字典来存储每个节点的子节点列表 m1 = defaultdict(list) for k, v in enumerate(parents): m1[v].append(k) # DFS函数,用于构建符合条件的字符串 def build_str(start): # 获取当前节点的所有子节点 clist = m1.get(start, []) # 如果没有子节点,返回空字符串 if len(clist) == 0: return "" # 递归构建所有子节点的演化序列,并排序 anslist = ["0"+build_str(i)+"1" for i in clist] anslist.sort() return "".join(anslist) # 从根节点开始构建序列 ret = build_str(m1.get(-1)[0]) # 返回序列,确保不包含多余的回退操作 return ret[:ret.rfind('0')+1]
在构建字符串时,使用'0'和'1'来标记每个子节点的开始和结束,这种表示方法类似于括号表达式中的左括号和右括号,用于明确定义每个子节点及其后代的边界。这样的设计有助于在递归过程中清晰地识别和构造每一个节点的演化序列,并在合并或者回退到父节点时保持结构的完整性。'0'的添加意味着进入一个新的子节点的演化序列,而'1'的添加则标志着该序列的结束并回退到当前节点,确保构建的字符串可以正确反映整个演化树的结构。
在DFS函数中对子节点序列进行排序是为了确保无论输入节点的顺序如何,最终构建的演化序列都是按照字典序最小排列的。这种排序确保当有多个子节点时,它们的演化序列以最优的顺序合并,从而达到全局的字典序最小。这是关键的,因为不同的合并顺序会产生不同的结果,而排序保证了无论节点如何展开,其结果始终是最小可能的字典序。因此,排序对于达到最终的字典序最小结果具有决定性影响。
题解中使用ret.rfind('0')+1是为了找到演化序列中最后一个'0'的位置,并据此确定返回字符串的长度,确保不包含对根节点之外的多余回退操作。在DFS构建过程中,每个节点的结束都会添加一个'1',表示回退到父节点。因此,整个演化序列的末尾通常会有多余的'1',这些'1'如果没有对应的'0'进行平衡,就意味着这些回退操作是多余的,可能会回退到根节点之外。通过裁剪到最后一个'0',我们确保所有的回退操作都是有效且必要的,符合演化树的结构逻辑,避免了生成无效或错误的演化路径。