示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文围绕 doocs/leetcode 仓库中 LCP 80「生物进化录」题解 展开讲解如何把一棵树形演化结构翻译成01记录串并通过DFS 递归构造 子树记录串字典序排序的贪心策略在n ≤ 10^4的规模下求得字典序最小的复刻串。读完你将掌握这道树 字符串 贪心综合题的完整推导、正确性论证以及 Python3 / Java / C / Go 四种语言实现的关键差异与运行细节。一、题目背景把一棵树说出来永恒之森中的生物进化录以树形结构记载所有生物的演化过程。输入数组parents描述了这棵树parents[i]表示编号i节点的父节点编号根节点的父节点为-1。炼金术师提出一种方法用01字符串将演化过程完整复刻下来规则如下字符语义指针行为0在当前节点下添加一个子节点指针移动到新添加的子节点1回退指针回到当前节点的父节点初始时指针位于唯一的根节点演化的起点随后依次读取01串中的字符执行上述操作。要求返回能够完整复刻演化过程的字符串中字典序最小的01串。注意节点指针最终可以停在任何节点上不一定要回到根节点。数据范围提示1 parents.length 10^4-1 parents[i] i即父节点编号严格小于子节点编号一个容易被忽略、但直接影响解法的推论是由于parents[i] i编号0必然是根节点且建图时父节点总是先于子节点出现因此只需要从i 1开始依次把每个节点挂到parents[i]名下即可无需额外判断合法性。二、问题转化一次带回溯标记的先序遍历把记录规则映射到树的遍历上可以得到一个关键等价关系指针从根出发根节点本身就是起点不需要任何0来进入根每访问一条父 → 子的边写一个0下潜进入子节点每从子节点回到父节点写一个1上升回溯因而任意一个完整记录串本质上就是一棵树上的先序遍历序列其中0表示进入子节点、1表示回到父节点。生物进化录记录过程的动画演示.gif)这样一来问题就变成在保持先序访问 回溯约束的前提下如何安排遍历顺序使产生的01串字典序最小。全局的自由度只有两个同一父节点下各子树子节点的访问顺序——这直接影响拼接结果的字典序末尾是否省略回溯的1——因为指针不必回到根末尾的回溯符可以被裁掉。题目文档的思考块也明确指出了这一点见 README.md 的thinking段落记录规则对应一次先序遍历进入子节点写0回溯写1。同一父节点下子树的记录顺序影响整串字典序且指针最终不必回到根末尾的回溯可以省略。三、示例精讲从暴力枚举到模式验证示例 1parents [-1, 0, 0, 2]→ 输出00110树结构为根0有两个子节点1、2而2又有一个子节点3。共有 2 种完整记录方案方案 10(记录编号 1 的节点) →1(回退至节点 0) →0(记录编号 2 的节点) →0(记录编号 3 的节点)得到0100指针最终停在节点 3方案 20(记录编号 2 的节点) →0(记录编号 3 的节点) →1(回退至节点 2) →1(回退至节点 0) →0(记录编号 1 的节点)得到00110指针最终停在节点 1。逐位比较00110与0100首位相同都是0第二位0 1因此返回字典序更小的00110。用题解的 DFS 递归验证一遍叶子节点1、3的记录串均为01节点2的记录串为0 01 1 0011根节点对两个子树串[01, 0011]排序后得0011 01于是dfs(0) 0 0011 01 1 00011011去掉首字符得0011011再裁掉末尾连续的1恰好得到00110。示例 2parents [-1, 0, 0, 1, 2, 2]→ 输出00101100逐层构造3、4、5为叶子记录串01节点1的记录串为0 01 1 0011节点2有两个叶子子节点记录串为0 01 01 1 001011根节点对[0011, 001011]排序001011 0011后拼接得dfs(0) 0 001011 0011 1 000101100111。去掉首字符得00101100111再裁掉末尾的1得到00101100与题目输出一致。四、核心解法DFS 递归构造 子树串字典序排序题目文档给出的标准解法是方法一DFSSolution.pyclass Solution: def evolutionaryRecord(self, parents: List[int]) - str: def dfs(i: int) - str: t sorted(dfs(j) for j in g[i]) return 0 .join(t) 1 n len(parents) g [[] for _ in range(n)] for i in range(1, n): g[parents[i]].append(i) return dfs(0)[1:].rstrip(1)整个算法只有三步但每一步都对应一个不容置疑的结论建图用邻接表g[i]保存节点i的所有子节点。得益于parents[i] i从i 1遍历即可完成建图。递归构造dfs(i)返回从节点i出发、完整记录其整个子树并回到i的记录串即0 各子树记录串按字典序排序后拼接 1。这里的0表示进入i末尾的1表示访问完i的子树后回到父节点。两端裁剪dfs(0)[1:]去掉根节点多余的首字符0根是起点不需要进入.rstrip(1)去掉末尾连续的1指针不必回到根末尾回溯符全部省略。为什么排序后拼接就是字典序最小这里需要一个经典的交换论证。设某个节点下有两个子树记录串A、B且字典序满足A B。如果保持其他部分的顺序不变只交换A、B的位置得到的两种拼接分别为A B与B A。要证明排序后拼接最小关键在于合法子树记录串的一个结构性不变量任意合法子树记录串都以0开头、以1结尾若把0视为1、1视为-1则记录串的前缀和除末位外恒为正末尾的1才把前缀和归零。由这个不变量可以推断任意两个合法子树记录串互不为对方的真前缀——因为若一个合法串是另一个合法串的前缀后者在前缀结束的位置前缀和必然为0而合法串内部不允许前缀和归零矛盾。而一旦两个字符串互不为真前缀A B字典序就意味着两者在某个位置首次出现字符差异且该处A的字符更小这个差异同样决定了A B B A。于是对每个节点把子树的记录串按字典序排序再拼接任何相邻交换都不会使结果变大局部即达到最优自底向上归纳整棵树的记录串达到全局字典序最小。为什么去首0、去尾1合法且必要去首0dfs(0)为统一递归格式而在根节点前也加了0但根本身就是起点这个进入根的0根本不存在必须删掉去尾1末尾的1只做回溯、不记录任何新节点删去后记录串依然完整复刻了整棵树且裁剪后的串是原串的前缀字典序严格更小所以能省则省恰好给出最小串。顺带一提边界情形当parents [-1]只有根节点时dfs(0) 01裁剪后返回空串语义上无演化可记录同样自洽。五、正确性论证框架把上面的推导整理成可复盘的论证链条合法性双射任一01记录串与树上的进入/回溯先序访问序列一一对应dfs(i)构造出的串按定义完整覆盖子树i的全部节点无前缀性结构性不变量合法子树记录串内部前缀和恒正、仅末位归零故任意两个合法子树串互不为真前缀局部最优交换论证互不为前缀的两串A B蕴含A B B A因此按字典序排序拼接即得该节点下的最小拼接全局归纳假设每个子树的记录串已是最小则根节点在最小子串集合上做字典序排序拼接所得整串就是全局最小裁剪最优首字符0必须删不存在的操作末尾1删尽后串最短且仍合法前缀关系保证其字典序最小。四条语言版本的代码实现完全遵循这套论证只是去首去尾的写法不同见下文。六、复杂度分析建图O(n)一次遍历parents即可递归每个节点恰好执行一次dfs子问题规模为子树大小排序每个节点对其子节点记录串排序。整棵树的子树串数量与边数同阶若按字符串比较成本摊还计算排序部分可推断为O(n log n)量级空间O(n)包含结果串长度与递归栈深度递归深度与树高相关最坏为链状树下的O(n)。两个实现层面的注意事项基于仓库代码可以推断字符串拼接成本Python3 的.join(t)、Go 的strings.Join(t, )是线性拼接而 Java、C 中不可变字符串的反复拼接在链状退化树每个节点只有一个子节点下会产生最坏O(n²)的字符拷贝量。好在n ≤ 10^4该开销仍在可接受范围内Python 递归深度当树退化为长链时递归深度可达10^4超过 Python 默认递归限制约 1000。在本地复现时若遇RecursionError可考虑提高递归上限或改为显式栈的迭代写法。七、多语言实现对照题目文档以 tabs 形式给出了四种语言的完整实现对应仓库中的 Solution.py、Solution.java、Solution.cpp、Solution.go核心逻辑完全一致差异只在去首去尾的惯用法上。Python3class Solution: def evolutionaryRecord(self, parents: List[int]) - str: def dfs(i: int) - str: t sorted(dfs(j) for j in g[i]) return 0 .join(t) 1 n len(parents) g [[] for _ in range(n)] for i in range(1, n): g[parents[i]].append(i) return dfs(0)[1:].rstrip(1)要点sorted直接按字典序排序生成器结果rstrip(1)删除末尾全部1。若在本地直接运行需要from typing import List在线评测环境通常已内置。Javaclass Solution { private ListInteger[] g; public String evolutionaryRecord(int[] parents) { int n parents.length; g new List[n]; Arrays.setAll(g, k - new ArrayList()); for (int i 1; i n; i) { g[parents[i]].add(i); } return dfs(0).substring(1).replaceAll(1$, ); } private String dfs(int i) { ListString t new ArrayList(); for (int j : g[i]) { t.add(dfs(j)); } Collections.sort(t); return 0 String.join(, t) 1; } }要点substring(1)去首正则1$匹配末尾连续的1并替换为空串等价于rstrip(1)。Cclass Solution { public: string evolutionaryRecord(vectorint parents) { int n parents.size(); vectorvectorint g(n); for (int i 1; i n; i) { g[parents[i]].push_back(i); } functionstring(int) dfs - string { vectorstring t; for (int j : g[i]) { t.push_back(dfs(j)); } sort(t.begin(), t.end()); string res 0; for (const string s : t) { res s; } res 1; return res; }; string ans dfs(0); return ans.substr(1, ans.find_last_not_of(1)); } };要点ans.substr(1, ans.find_last_not_of(1))一步完成去首 裁到最后一个非1字符两件事。Gofunc evolutionaryRecord(parents []int) string { n : len(parents) g : make([][]int, n) for i : 1; i n; i { g[parents[i]] append(g[parents[i]], i) } var dfs func(int) string dfs func(i int) string { var t []string for _, j : range g[i] { t append(t, dfs(j)) } sort.Strings(t) return 0 strings.Join(t, ) 1 } ans : dfs(0)[1:] return strings.TrimRight(ans, 1) }要点sort.Strings按字节字典序排序strings.TrimRight(ans, 1)裁掉末尾所有1语义与 Python 的rstrip(1)一致。语言排序子串去首字符去末尾1Python3sorted(...)切片[1:]rstrip(1)JavaCollections.sort(t)substring(1)replaceAll(1$, )Csort(t.begin(), t.end())substr(1, ...)find_last_not_of(1)Gosort.Strings(t)切片[1:]TrimRight(ans, 1)八、仓库组织与扩展阅读该题解位于仓库的 LCP 系列目录下文件组织非常规整题目与题解文档lcp/LCP 80. 生物进化录/README.md包含题目描述、示例、提示、解法思路与多语言代码题解源码同目录下的Solution.py、Solution.java、Solution.cpp、Solution.go与文档中的代码完全一致可直接复制到本地或在线评测环境运行配图资源同目录images/下存放了示例 1 的树形结构图与记录过程动画分别用于解释输入与规则系列索引lcp/README.md 汇总了全部 LCP 题目可用Control/Command F按题号快速检索。仓库中每个题解目录都遵循README 文档 多语言 Solution 源码的同一模式便于对照学习不同语言对同一算法的惯用写法。若想在本地复现本题只需将对应语言的Solution代码粘贴到支持的环境如在线评测平台或本地解释器中传入题目给定的parents数组即可无需额外依赖。九、小结与延伸思考LCP 80「生物进化录」的解法可以提炼为一套可迁移的解题框架把结构翻译成事件序列树上的进入0/ 回溯1天然对应一次带括号语义的先序遍历先把规则转成遍历问题识别自由度本题的自由度只有同一父节点下子树的访问顺序与末尾是否省略回溯这是贪心可以介入的入口交换论证 结构性不变量通过合法子树串互不为前缀这一前缀和不变量证明按字典序排序拼接即最优两端裁剪根的首0与末尾可省略的1必须裁掉裁剪后的串最短且字典序更小。这种用字符串复刻树/图结构并求字典序最小的思路与树的序列化如括号表示法、欧拉序一脉相承——把结构编码成序列、再对序列做最小化是树相关字符串问题中非常值得复用的思考方式。遇到同类题目时不妨先问自己三个问题事件序列如何定义自由度在哪里裁剪规则是否合法且必要赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐codeforces-go 题解根据 LCP 矩阵构造字典序最小字符串LeetCode 3031 Find the String with LCPcodeforces go 题解根据 LCP 矩阵构造字典序最小字符串LeetCode 3031 Find the String with LCP 本篇技科学计算doocs/leetcode 题解精讲LCP 40「心算挑战」——贪心 排序求最大偶数和doocs/leetcode 题解精讲LCP 40「心算挑战」——贪心 排序求最大偶数和 导读 「心算挑战」是力扣 LCPLeetCode CUP系列示例工程codeforces-go 题解精读LeetCode 2434「使用机器人打印字典序最小的字符串」——栈 剩余最小字母贪心算法codeforces go 题解精读LeetCode 2434「使用机器人打印字典序最小的字符串」——栈 剩余最小字母贪心算法 本篇题解来自算法竞赛模板库科学计算上一篇gh_mirrors/trl/trl中的训练可视化3D PCA投影下一篇从混乱到统一DVA模型如何优雅适配多源数据创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/10/16 1:55:20 · 阅读 1.2k doocs/leetcode 题解精读：LCP 80「生物进化录」——DFS 贪心构造字典序最小的 01 演化记录串
示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文围绕 doocs/leetcode 仓库中 LCP 80「生物进化录」题解 展开讲解如何把一棵树形演化结构翻译成01记录串并通过DFS 递归构造 子树记录串字典序排序的贪心策略在n ≤ 10^4的规模下求得字典序最小的复刻串。读完你将掌握这道树 字符串 贪心综合题的完整推导、正确性论证以及 Python3 / Java / C / Go 四种语言实现的关键差异与运行细节。一、题目背景把一棵树说出来永恒之森中的生物进化录以树形结构记载所有生物的演化过程。输入数组parents描述了这棵树parents[i]表示编号i节点的父节点编号根节点的父节点为-1。炼金术师提出一种方法用01字符串将演化过程完整复刻下来规则如下字符语义指针行为0在当前节点下添加一个子节点指针移动到新添加的子节点1回退指针回到当前节点的父节点初始时指针位于唯一的根节点演化的起点随后依次读取01串中的字符执行上述操作。要求返回能够完整复刻演化过程的字符串中字典序最小的01串。注意节点指针最终可以停在任何节点上不一定要回到根节点。数据范围提示1 parents.length 10^4-1 parents[i] i即父节点编号严格小于子节点编号一个容易被忽略、但直接影响解法的推论是由于parents[i] i编号0必然是根节点且建图时父节点总是先于子节点出现因此只需要从i 1开始依次把每个节点挂到parents[i]名下即可无需额外判断合法性。二、问题转化一次带回溯标记的先序遍历把记录规则映射到树的遍历上可以得到一个关键等价关系指针从根出发根节点本身就是起点不需要任何0来进入根每访问一条父 → 子的边写一个0下潜进入子节点每从子节点回到父节点写一个1上升回溯因而任意一个完整记录串本质上就是一棵树上的先序遍历序列其中0表示进入子节点、1表示回到父节点。生物进化录记录过程的动画演示.gif)这样一来问题就变成在保持先序访问 回溯约束的前提下如何安排遍历顺序使产生的01串字典序最小。全局的自由度只有两个同一父节点下各子树子节点的访问顺序——这直接影响拼接结果的字典序末尾是否省略回溯的1——因为指针不必回到根末尾的回溯符可以被裁掉。题目文档的思考块也明确指出了这一点见 README.md 的thinking段落记录规则对应一次先序遍历进入子节点写0回溯写1。同一父节点下子树的记录顺序影响整串字典序且指针最终不必回到根末尾的回溯可以省略。三、示例精讲从暴力枚举到模式验证示例 1parents [-1, 0, 0, 2]→ 输出00110树结构为根0有两个子节点1、2而2又有一个子节点3。共有 2 种完整记录方案方案 10(记录编号 1 的节点) →1(回退至节点 0) →0(记录编号 2 的节点) →0(记录编号 3 的节点)得到0100指针最终停在节点 3方案 20(记录编号 2 的节点) →0(记录编号 3 的节点) →1(回退至节点 2) →1(回退至节点 0) →0(记录编号 1 的节点)得到00110指针最终停在节点 1。逐位比较00110与0100首位相同都是0第二位0 1因此返回字典序更小的00110。用题解的 DFS 递归验证一遍叶子节点1、3的记录串均为01节点2的记录串为0 01 1 0011根节点对两个子树串[01, 0011]排序后得0011 01于是dfs(0) 0 0011 01 1 00011011去掉首字符得0011011再裁掉末尾连续的1恰好得到00110。示例 2parents [-1, 0, 0, 1, 2, 2]→ 输出00101100逐层构造3、4、5为叶子记录串01节点1的记录串为0 01 1 0011节点2有两个叶子子节点记录串为0 01 01 1 001011根节点对[0011, 001011]排序001011 0011后拼接得dfs(0) 0 001011 0011 1 000101100111。去掉首字符得00101100111再裁掉末尾的1得到00101100与题目输出一致。四、核心解法DFS 递归构造 子树串字典序排序题目文档给出的标准解法是方法一DFSSolution.pyclass Solution: def evolutionaryRecord(self, parents: List[int]) - str: def dfs(i: int) - str: t sorted(dfs(j) for j in g[i]) return 0 .join(t) 1 n len(parents) g [[] for _ in range(n)] for i in range(1, n): g[parents[i]].append(i) return dfs(0)[1:].rstrip(1)整个算法只有三步但每一步都对应一个不容置疑的结论建图用邻接表g[i]保存节点i的所有子节点。得益于parents[i] i从i 1遍历即可完成建图。递归构造dfs(i)返回从节点i出发、完整记录其整个子树并回到i的记录串即0 各子树记录串按字典序排序后拼接 1。这里的0表示进入i末尾的1表示访问完i的子树后回到父节点。两端裁剪dfs(0)[1:]去掉根节点多余的首字符0根是起点不需要进入.rstrip(1)去掉末尾连续的1指针不必回到根末尾回溯符全部省略。为什么排序后拼接就是字典序最小这里需要一个经典的交换论证。设某个节点下有两个子树记录串A、B且字典序满足A B。如果保持其他部分的顺序不变只交换A、B的位置得到的两种拼接分别为A B与B A。要证明排序后拼接最小关键在于合法子树记录串的一个结构性不变量任意合法子树记录串都以0开头、以1结尾若把0视为1、1视为-1则记录串的前缀和除末位外恒为正末尾的1才把前缀和归零。由这个不变量可以推断任意两个合法子树记录串互不为对方的真前缀——因为若一个合法串是另一个合法串的前缀后者在前缀结束的位置前缀和必然为0而合法串内部不允许前缀和归零矛盾。而一旦两个字符串互不为真前缀A B字典序就意味着两者在某个位置首次出现字符差异且该处A的字符更小这个差异同样决定了A B B A。于是对每个节点把子树的记录串按字典序排序再拼接任何相邻交换都不会使结果变大局部即达到最优自底向上归纳整棵树的记录串达到全局字典序最小。为什么去首0、去尾1合法且必要去首0dfs(0)为统一递归格式而在根节点前也加了0但根本身就是起点这个进入根的0根本不存在必须删掉去尾1末尾的1只做回溯、不记录任何新节点删去后记录串依然完整复刻了整棵树且裁剪后的串是原串的前缀字典序严格更小所以能省则省恰好给出最小串。顺带一提边界情形当parents [-1]只有根节点时dfs(0) 01裁剪后返回空串语义上无演化可记录同样自洽。五、正确性论证框架把上面的推导整理成可复盘的论证链条合法性双射任一01记录串与树上的进入/回溯先序访问序列一一对应dfs(i)构造出的串按定义完整覆盖子树i的全部节点无前缀性结构性不变量合法子树记录串内部前缀和恒正、仅末位归零故任意两个合法子树串互不为真前缀局部最优交换论证互不为前缀的两串A B蕴含A B B A因此按字典序排序拼接即得该节点下的最小拼接全局归纳假设每个子树的记录串已是最小则根节点在最小子串集合上做字典序排序拼接所得整串就是全局最小裁剪最优首字符0必须删不存在的操作末尾1删尽后串最短且仍合法前缀关系保证其字典序最小。四条语言版本的代码实现完全遵循这套论证只是去首去尾的写法不同见下文。六、复杂度分析建图O(n)一次遍历parents即可递归每个节点恰好执行一次dfs子问题规模为子树大小排序每个节点对其子节点记录串排序。整棵树的子树串数量与边数同阶若按字符串比较成本摊还计算排序部分可推断为O(n log n)量级空间O(n)包含结果串长度与递归栈深度递归深度与树高相关最坏为链状树下的O(n)。两个实现层面的注意事项基于仓库代码可以推断字符串拼接成本Python3 的.join(t)、Go 的strings.Join(t, )是线性拼接而 Java、C 中不可变字符串的反复拼接在链状退化树每个节点只有一个子节点下会产生最坏O(n²)的字符拷贝量。好在n ≤ 10^4该开销仍在可接受范围内Python 递归深度当树退化为长链时递归深度可达10^4超过 Python 默认递归限制约 1000。在本地复现时若遇RecursionError可考虑提高递归上限或改为显式栈的迭代写法。七、多语言实现对照题目文档以 tabs 形式给出了四种语言的完整实现对应仓库中的 Solution.py、Solution.java、Solution.cpp、Solution.go核心逻辑完全一致差异只在去首去尾的惯用法上。Python3class Solution: def evolutionaryRecord(self, parents: List[int]) - str: def dfs(i: int) - str: t sorted(dfs(j) for j in g[i]) return 0 .join(t) 1 n len(parents) g [[] for _ in range(n)] for i in range(1, n): g[parents[i]].append(i) return dfs(0)[1:].rstrip(1)要点sorted直接按字典序排序生成器结果rstrip(1)删除末尾全部1。若在本地直接运行需要from typing import List在线评测环境通常已内置。Javaclass Solution { private ListInteger[] g; public String evolutionaryRecord(int[] parents) { int n parents.length; g new List[n]; Arrays.setAll(g, k - new ArrayList()); for (int i 1; i n; i) { g[parents[i]].add(i); } return dfs(0).substring(1).replaceAll(1$, ); } private String dfs(int i) { ListString t new ArrayList(); for (int j : g[i]) { t.add(dfs(j)); } Collections.sort(t); return 0 String.join(, t) 1; } }要点substring(1)去首正则1$匹配末尾连续的1并替换为空串等价于rstrip(1)。Cclass Solution { public: string evolutionaryRecord(vectorint parents) { int n parents.size(); vectorvectorint g(n); for (int i 1; i n; i) { g[parents[i]].push_back(i); } functionstring(int) dfs - string { vectorstring t; for (int j : g[i]) { t.push_back(dfs(j)); } sort(t.begin(), t.end()); string res 0; for (const string s : t) { res s; } res 1; return res; }; string ans dfs(0); return ans.substr(1, ans.find_last_not_of(1)); } };要点ans.substr(1, ans.find_last_not_of(1))一步完成去首 裁到最后一个非1字符两件事。Gofunc evolutionaryRecord(parents []int) string { n : len(parents) g : make([][]int, n) for i : 1; i n; i { g[parents[i]] append(g[parents[i]], i) } var dfs func(int) string dfs func(i int) string { var t []string for _, j : range g[i] { t append(t, dfs(j)) } sort.Strings(t) return 0 strings.Join(t, ) 1 } ans : dfs(0)[1:] return strings.TrimRight(ans, 1) }要点sort.Strings按字节字典序排序strings.TrimRight(ans, 1)裁掉末尾所有1语义与 Python 的rstrip(1)一致。语言排序子串去首字符去末尾1Python3sorted(...)切片[1:]rstrip(1)JavaCollections.sort(t)substring(1)replaceAll(1$, )Csort(t.begin(), t.end())substr(1, ...)find_last_not_of(1)Gosort.Strings(t)切片[1:]TrimRight(ans, 1)八、仓库组织与扩展阅读该题解位于仓库的 LCP 系列目录下文件组织非常规整题目与题解文档lcp/LCP 80. 生物进化录/README.md包含题目描述、示例、提示、解法思路与多语言代码题解源码同目录下的Solution.py、Solution.java、Solution.cpp、Solution.go与文档中的代码完全一致可直接复制到本地或在线评测环境运行配图资源同目录images/下存放了示例 1 的树形结构图与记录过程动画分别用于解释输入与规则系列索引lcp/README.md 汇总了全部 LCP 题目可用Control/Command F按题号快速检索。仓库中每个题解目录都遵循README 文档 多语言 Solution 源码的同一模式便于对照学习不同语言对同一算法的惯用写法。若想在本地复现本题只需将对应语言的Solution代码粘贴到支持的环境如在线评测平台或本地解释器中传入题目给定的parents数组即可无需额外依赖。九、小结与延伸思考LCP 80「生物进化录」的解法可以提炼为一套可迁移的解题框架把结构翻译成事件序列树上的进入0/ 回溯1天然对应一次带括号语义的先序遍历先把规则转成遍历问题识别自由度本题的自由度只有同一父节点下子树的访问顺序与末尾是否省略回溯这是贪心可以介入的入口交换论证 结构性不变量通过合法子树串互不为前缀这一前缀和不变量证明按字典序排序拼接即最优两端裁剪根的首0与末尾可省略的1必须裁掉裁剪后的串最短且字典序更小。这种用字符串复刻树/图结构并求字典序最小的思路与树的序列化如括号表示法、欧拉序一脉相承——把结构编码成序列、再对序列做最小化是树相关字符串问题中非常值得复用的思考方式。遇到同类题目时不妨先问自己三个问题事件序列如何定义自由度在哪里裁剪规则是否合法且必要赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐codeforces-go 题解根据 LCP 矩阵构造字典序最小字符串LeetCode 3031 Find the String with LCPcodeforces go 题解根据 LCP 矩阵构造字典序最小字符串LeetCode 3031 Find the String with LCP 本篇技科学计算doocs/leetcode 题解精讲LCP 40「心算挑战」——贪心 排序求最大偶数和doocs/leetcode 题解精讲LCP 40「心算挑战」——贪心 排序求最大偶数和 导读 「心算挑战」是力扣 LCPLeetCode CUP系列示例工程codeforces-go 题解精读LeetCode 2434「使用机器人打印字典序最小的字符串」——栈 剩余最小字母贪心算法codeforces go 题解精读LeetCode 2434「使用机器人打印字典序最小的字符串」——栈 剩余最小字母贪心算法 本篇题解来自算法竞赛模板库科学计算上一篇gh_mirrors/trl/trl中的训练可视化3D PCA投影下一篇从混乱到统一DVA模型如何优雅适配多源数据创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考