列表

详情


LCP 80. 生物进化录

在永恒之森中,存在着一本生物进化录,以 一个树形结构 记载了所有生物的演化过程。经过观察并整理了各节点间的关系,parents[i] 表示编号 i 节点的父节点编号(根节点的父节点为 -1)。

为了探索和记录其中的演化规律,队伍中的炼金术师提出了一种方法,可以以字符串的形式将其复刻下来,规则如下:

现在需要应用上述的记录方法,复刻下它的演化过程。请返回能够复刻演化过程的字符串中, 字典序最小01 字符串。

注意:

示例 1:

输入:parents = [-1,0,0,2]

输出:"00110"

解释:树结构如下图所示,共存在 2 种记录方案: 第 1 种方案为:0(记录编号 1 的节点) -> 1(回退至节点 0) -> 0(记录编号 2 的节点) -> 0((记录编号 3 的节点)) 第 2 种方案为:0(记录编号 2 的节点) -> 0(记录编号 3 的节点) -> 1(回退至节点 2) -> 1(回退至节点 0) -> 0(记录编号 1 的节点) 返回字典序更小的 "00110" image.png{:width=120px}进化 (3).gif{:width=320px}

示例 2:

输入:parents = [-1,0,0,1,2,2]

输出:"00101100"

提示:

原站题解

去查看

上次编辑到这里,代码来自缓存 点击恢复默认模板
class Solution { public: string evolutionaryRecord(vector<int>& parents) { } };

golang 解法, 执行用时: 268 ms, 内存消耗: 10 MB, 提交时间: 2023-05-08 10:16:51

func evolutionaryRecord(parents []int) string {
	n := len(parents)
	g := make([][]int, n)
	for w := 1; w < n; w++ {
		p := parents[w]
		g[p] = append(g[p], w) // 建树
	}

	var dfs func(int) string
	dfs = func(v int) string {
		a := make([]string, len(g[v]))
		for i, w := range g[v] {
			a[i] = dfs(w)
		}
		sort.Strings(a)
		return "0" + strings.Join(a, "") + "1"
	}
	return strings.TrimRight(dfs(0)[1:], "1") // 去掉根节点以及返回根节点的路径
}

python3 解法, 执行用时: 300 ms, 内存消耗: 33.2 MB, 提交时间: 2023-05-08 10:16:37

class Solution:
    def evolutionaryRecord(self, parents: List[int]) -> str:
        n = len(parents)
        g = [[] for _ in range(n)]
        for i in range(1, n):
            g[parents[i]].append(i)  # 建树

        def dfs(x: int) -> str:
            a = sorted(dfs(y) for y in g[x])
            return "0" + ''.join(a) + "1"
        return dfs(0)[1:].rstrip('1')  # 去掉根节点以及返回根节点的路径

上一题