本文主要是介绍多叉树题目:王位继承顺序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 题目
- 标题和出处
- 难度
- 题目描述
- 要求
- 示例
- 数据范围
- 解法
- 思路和算法
- 代码
- 复杂度分析
题目
标题和出处
标题:王位继承顺序
出处:1600. 王位继承顺序
难度
5 级
题目描述
要求
一个王国里住着国王、他的子辈们、他的孙辈们等等。每一个时间点,这个家庭里有人出生也有人死亡。
这个王国有一个明确规定的王位继承顺序,第一继承人总是国王自己。定义递归函数 Successor(x, curOrder) \texttt{Successor(x, curOrder)} Successor(x, curOrder),该函数给定一个人 x \texttt{x} x 和当前的继承顺序,返回 x \texttt{x} x 的下一继承人。
Successor(x, curOrder):如果 x 没有孩子或者所有 x 的孩子都在 curOrder 中:如果 x 是国王,那么返回 null否则,返回 Successor(x 的父亲, curOrder)否则,返回 x 不在 curOrder 中最年长的孩子
例如,假设王国由国王、他的孩子 Alice 和 Bob(Alice 比 Bob 年长)和 Alice 的孩子 Jack 组成。
- 初始时, curOrder \texttt{curOrder} curOrder 为 ["king"] \texttt{["king"]} ["king"]。
- 调用 Successor(king, curOrder) \texttt{Successor(king, curOrder)} Successor(king, curOrder),返回 Alice,所以将 Alice 放入 curOrder \texttt{curOrder} curOrder 中,得到 ["king", "Alice"] \texttt{["king", "Alice"]} ["king", "Alice"]。
- 调用 Successor(Alice, curOrder) \texttt{Successor(Alice, curOrder)} Successor(Alice, curOrder),返回 Jack,所以将 Jack 放入 curOrder \texttt{curOrder} curOrder 中,得到 ["king", "Alice", "Jack"] \texttt{["king", "Alice", "Jack"]} ["king", "Alice", "Jack"]。
- 调用 Successor(Jack, curOrder) \texttt{Successor(Jack, curOrder)} Successor(Jack, curOrder),返回 Bob,所以将 Bob 放入 curOrder \texttt{curOrder} curOrder 中,得到 ["king", "Alice", "Jack", "Bob"] \texttt{["king", "Alice", "Jack", "Bob"]} ["king", "Alice", "Jack", "Bob"]。
- 调用 Successor(Bob, curOrder) \texttt{Successor(Bob, curOrder)} Successor(Bob, curOrder),返回 null \texttt{null} null。最终得到继承顺序为 ["king", "Alice", "Jack", "Bob"] \texttt{["king", "Alice", "Jack", "Bob"]} ["king", "Alice", "Jack", "Bob"]。
使用以上的函数,总是能得到一个唯一的继承顺序。
实现 ThroneInheritance \texttt{ThroneInheritance} ThroneInheritance 类:
- ThroneInheritance(string kingName) \texttt{ThroneInheritance(string kingName)} ThroneInheritance(string kingName) 初始化一个 ThroneInheritance \texttt{ThroneInheritance} ThroneInheritance 类的对象。国王的名字作为构造函数的参数传入。
- void birth(string parentName, string childName) \texttt{void birth(string parentName, string childName)} void birth(string parentName, string childName) 表示 parentName \texttt{parentName} parentName 新拥有了一个名为 childName \texttt{childName} childName 的孩子。
- void death(string name) \texttt{void death(string name)} void death(string name) 表示名为 name \texttt{name} name 的人死亡。一个人的死亡不会影响 Successor \texttt{Successor} Successor 函数,也不会影响当前的继承顺序。可以只将这个人标记为死亡状态。
- string[] getInheritanceOrder() \texttt{string[] getInheritanceOrder()} string[] getInheritanceOrder() 返回除去死亡人员的当前继承顺序列表。
示例
示例 1:
输入:
["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"] \texttt{["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"]} ["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"]
[["king"], ["king", "andy"], ["king", "bob"], ["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"], [null], ["bob"], [null]] \texttt{[["king"], ["king", "andy"], ["king", "bob"], ["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"], [null], ["bob"], [null]]} [["king"], ["king", "andy"], ["king", "bob"], ["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"], [null], ["bob"], [null]]
输出:
[null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]] \texttt{[null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]]} [null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]]
解释:
ThroneInheritance t = new ThroneInheritance("king"); \texttt{ThroneInheritance t = new ThroneInheritance("king");} ThroneInheritance t = new ThroneInheritance("king"); // 继承顺序: king \texttt{king} king
t.birth("king", "andy"); \texttt{t.birth("king", "andy");} t.birth("king", "andy"); // 继承顺序: king > andy \texttt{king} > \texttt{andy} king>andy
t.birth("king", "bob"); \texttt{t.birth("king", "bob");} t.birth("king", "bob"); // 继承顺序: king > andy > bob \texttt{king} > \texttt{andy} > \texttt{bob} king>andy>bob
t.birth("king", "catherine"); \texttt{t.birth("king", "catherine");} t.birth("king", "catherine"); // 继承顺序: king > andy > bob > catherine \texttt{king} > \texttt{andy} > \texttt{bob} > \texttt{catherine} king>andy>bob>catherine
t.birth("andy", "matthew"); \texttt{t.birth("andy", "matthew");} t.birth("andy", "matthew"); // 继承顺序: king > andy > matthew > bob > catherine \texttt{king} > \texttt{andy} > \texttt{matthew} > \texttt{bob} > \texttt{catherine} king>andy>matthew>bob>catherine
t.birth("bob", "alex"); \texttt{t.birth("bob", "alex");} t.birth("bob", "alex"); // 继承顺序: king > andy > matthew > bob > alex > catherine \texttt{king} > \texttt{andy} > \texttt{matthew} > \texttt{bob} > \texttt{alex} > \texttt{catherine} king>andy>matthew>bob>alex>catherine
t.birth("bob", "asha"); \texttt{t.birth("bob", "asha");} t.birth("bob", "asha"); // 继承顺序: king > andy > matthew > bob > alex > asha > catherine \texttt{king} > \texttt{andy} > \texttt{matthew} > \texttt{bob} > \texttt{alex} > \texttt{asha} > \texttt{catherine} king>andy>matthew>bob>alex>asha>catherine
t.getInheritanceOrder(); \texttt{t.getInheritanceOrder();} t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"] \texttt{["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]} ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]
t.death("bob"); \texttt{t.death("bob");} t.death("bob"); // 继承顺序: king > andy > matthew > bob (已经去世) > alex > asha > catherine \texttt{king} > \texttt{andy} > \texttt{matthew} > \texttt{bob}(已经去世)> \texttt{alex} > \texttt{asha} > \texttt{catherine} king>andy>matthew>bob(已经去世)>alex>asha>catherine
t.getInheritanceOrder(); \texttt{t.getInheritanceOrder();} t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "alex", "asha", "catherine"] \texttt{["king", "andy", "matthew", "alex", "asha", "catherine"]} ["king", "andy", "matthew", "alex", "asha", "catherine"]
数据范围
- 1 ≤ kingName.length, parentName.length, childName.length, name.length ≤ 15 \texttt{1} \le \texttt{kingName.length, parentName.length, childName.length, name.length} \le \texttt{15} 1≤kingName.length, parentName.length, childName.length, name.length≤15
- kingName \texttt{kingName} kingName, parentName \texttt{parentName} parentName, childName \texttt{childName} childName 和 name \texttt{name} name 仅包含小写英语字母
- 所有的参数 childName \texttt{childName} childName 和 kingName \texttt{kingName} kingName 互不相同
- 所有传给 death \texttt{death} death 函数的参数 name \texttt{name} name 都会首先传给构造方法或者 birth \texttt{birth} birth 函数中的 childName \texttt{childName} childName 参数
- 每次调用 birth(parentName, childName) \texttt{birth(parentName, childName)} birth(parentName, childName) 时,保证 parentName \texttt{parentName} parentName 对应的人员是活着的
- 最多调用 10 5 \texttt{10}^\texttt{5} 105 次 birth \texttt{birth} birth 和 death \texttt{death} death
- 最多调用 10 \texttt{10} 10 次 getInheritanceOrder \texttt{getInheritanceOrder} getInheritanceOrder
解法
思路和算法
将王国中的所有人分别看成结点,则王国中的所有人组成一个多叉树,根结点是国王,相邻结点之间的父结点和子结点关系表示父辈和子辈的关系。
调用 Successor \texttt{Successor} Successor 函数时,优先考虑当前结点的第一个尚未访问的子结点,如果当前结点没有子结点或者当前结点的子结点都访问结束,则回到当前结点的父结点继续操作,直到所有结点都访问过。
根据上述流程可知, Successor \texttt{Successor} Successor 函数的实质是多叉树的前序遍历,因此需要维护表示王国的多叉树,并支持出生、死亡和获得继承顺序列表的操作。
维护多叉树的方法有多种。一种方法是使用哈希表存储每个人名和所有孩子表示树结构,使用哈希集合存储活着的人名或者死亡的人名(哈希表存储其中的一类人名,根据哈希表中是否存在人名判断人员是活着还是死亡);另一种方法是创建多叉树结点类,使用哈希表存储每个人名对应的结点。此处使用后一种方法,具体而言,每个结点存储人名、生死状态以及子结点,每个结点创建时状态默认为活着。
构造方法中,使用 kingName \textit{kingName} kingName 创建国王结点,将 kingName \textit{kingName} kingName 和国王结点存入哈希表中。国王结点为多叉树的根结点。
对于 birth \textit{birth} birth 操作,从哈希表中获得 parentName \textit{parentName} parentName 对应的父辈结点,使用 childName \textit{childName} childName 创建子辈结点,将子辈结点加入父辈结点的子结点中,将 childName \textit{childName} childName 和子辈结点存入哈希表中。
对于 death \textit{death} death 操作,从哈希表中获得 name \textit{name} name 对应的结点,将该结点的状态设为死亡。
对于 getInheritanceOrder \textit{getInheritanceOrder} getInheritanceOrder 操作,从国王结点开始前序遍历多叉树。遍历过程中需要访问所有的结点,但是只将状态为活着的结点的名字加入继承顺序列表中。
代码
class ThroneInheritance {private class Node {private String name;private boolean alive;private List<Node> children;public Node(String name) {this.name = name;this.alive = true;this.children = new ArrayList<Node>();}public String getName() {return name;}public boolean isAlive() {return alive;}public void death() {alive = false;}public List<Node> getChildren() {return children;}public Node birth(String name) {Node child = new Node(name);children.add(child);return child;}}private Node king;private Map<String, Node> nodeMap;public ThroneInheritance(String kingName) {king = new Node(kingName);nodeMap = new HashMap<String, Node>();nodeMap.put(kingName, king);}public void birth(String parentName, String childName) {Node parent = nodeMap.get(parentName);Node child = parent.birth(childName);nodeMap.put(childName, child);}public void death(String name) {Node node = nodeMap.get(name);node.death();}public List<String> getInheritanceOrder() {List<String> inheritanceOrder = new ArrayList<String>();preorder(king, inheritanceOrder);return inheritanceOrder;}private void preorder(Node node, List<String> inheritanceOrder) {if (node.isAlive()) {inheritanceOrder.add(node.getName());}List<Node> children = node.getChildren();for (Node child : children) {preorder(child, inheritanceOrder);}}
}
复杂度分析
-
时间复杂度:构造方法的时间复杂度是 O ( 1 ) O(1) O(1),方法 birth \textit{birth} birth 的时间复杂度是 O ( 1 ) O(1) O(1),方法 death \textit{death} death 的时间复杂度是 O ( 1 ) O(1) O(1),方法 getInheritanceOrder \textit{getInheritanceOrder} getInheritanceOrder 的时间复杂度是 O ( n ) O(n) O(n),其中 n n n 是王国中的人数。构造方法、方法 birth \textit{birth} birth 和方法 death \textit{death} death 都是常数时间的操作,方法 getInheritanceOrder \textit{getInheritanceOrder} getInheritanceOrder 需要 O ( n ) O(n) O(n) 的时间前序遍历多叉树。这里将字符串操作的时间视为 O ( 1 ) O(1) O(1)。
-
空间复杂度: O ( n ) O(n) O(n),其中 n n n 是王国中的人数。存储多叉树和哈希表都需要 O ( n ) O(n) O(n) 的空间。这里将字符串占用的空间视为 O ( 1 ) O(1) O(1)。
这篇关于多叉树题目:王位继承顺序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!