多叉树题目:王位继承顺序

2024-04-11 21:12

本文主要是介绍多叉树题目:王位继承顺序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:王位继承顺序

出处: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 组成。

  1. 初始时, curOrder \texttt{curOrder} curOrder ["king"] \texttt{["king"]} ["king"]
  2. 调用 Successor(king, curOrder) \texttt{Successor(king, curOrder)} Successor(king, curOrder),返回 Alice,所以将 Alice 放入 curOrder \texttt{curOrder} curOrder 中,得到 ["king", "Alice"] \texttt{["king", "Alice"]} ["king", "Alice"]
  3. 调用 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"]
  4. 调用 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"]
  5. 调用 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} 1kingName.length, parentName.length, childName.length, name.length15
  • 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)

这篇关于多叉树题目:王位继承顺序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/895195

相关文章

顺序表之创建,判满,插入,输出

文章目录 🍊自我介绍🍊创建一个空的顺序表,为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了,满了返回值1,否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~ 🍊自我介绍   Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾”

题目1254:N皇后问题

题目1254:N皇后问题 时间限制:1 秒 内存限制:128 兆 特殊判题:否 题目描述: N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。 你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

web群集--nginx配置文件location匹配符的优先级顺序详解及验证

文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配(Exact Match)2. 正则表达式匹配(Regex Match)3. 前缀匹配(Prefix Match) 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中,location 指令用于定义如何处理特定的请求 URI。由于网站往往需要不同的处理方式来适应各种请求,NGINX 提供了多种匹

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

码蹄集部分题目(2024OJ赛9.4-9.8;线段树+树状数组)

1🐋🐋配对最小值(王者;树状数组) 时间限制:1秒 占用内存:64M 🐟题目思路 MT3065 配对最小值_哔哩哔哩_bilibili 🐟代码 #include<bits/stdc++.h> using namespace std;const int N=1e5+7;int a[N],b[N],c[N],n,q;struct QUERY{int l,r,id;}que

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表,允许插入的一端叫做队尾(rear),允许删除的一端叫做队首(front)。 队列具有FIFO的性质 队列的存储表示也有两种方式:基于数组的,基于列表的。基于数组的叫做顺序队列,基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示:只提供了接口和显式的默认构造函数和析构函数,在派生类中调用。 #i

[数据结构]栈之顺序栈的类模板实现

栈的数组实现形式,采用动态分配数组,不够时可以调整栈的大小。 Stack.h文件:主要定义栈的抽象基类,提供公共的接口函数。 #ifndef STACK#define STACK//栈的抽象基类template<class T>class Stack{public:Stack(){}~Stack(){}virtual void Push(const T& x)=0;virt

C++中类的构造函数调用顺序

当建立一个对象时,首先调用基类的构造函数,然后调用下一个派生类的 构造函数,依次类推,直至到达派生类次数最多的派生次数最多的类的构造函数为止。 简而言之,对象是由“底层向上”开始构造的。因为,构造函数一开始构造时,总是 要调用它的基类的构造函数,然后才开始执行其构造函数体,调用直接基类构造函数时, 如果无专门说明,就调用直接基类的默认构造函数。在对象析构时,其顺序正好相反。

七、Maven继承和聚合关系、及Maven的仓库及查找顺序

1.继承   2.聚合   3.Maven的仓库及查找顺序