题目描述
一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点,这个家庭里有人出生也有人死亡。
这个王国有一个明确规定的王位继承顺序,第一继承人总是国王自己。我们定义递归函数 Successor(x, curOrder)
,给定一个人 x
和当前的继承顺序,该函数返回 x
的下一继承人。
Successor(x, curOrder):
如果 x 没有孩子或者所有 x 的孩子都在 curOrder 中:
如果 x 是国王,那么返回 null
否则,返回 Successor(x 的父亲, curOrder)
否则,返回 x 不在 curOrder 中最年长的孩子
比方说,假设王国由国王,他的孩子 Alice 和 Bob (Alice 比 Bob 年长)和 Alice 的孩子 Jack 组成。
- 一开始,
curOrder
为["king"]
. - 调用
Successor(king, curOrder)
,返回 Alice ,所以我们将 Alice 放入curOrder
中,得到["king", "Alice"]
。 - 调用
Successor(Alice, curOrder)
,返回 Jack ,所以我们将 Jack 放入curOrder
中,得到["king", "Alice", "Jack"]
。 - 调用
Successor(Jack, curOrder)
,返回 Bob ,所以我们将 Bob 放入curOrder
中,得到["king", "Alice", "Jack", "Bob"]
。 - 调用
Successor(Bob, curOrder)
,返回null
。最终得到继承顺序为["king", "Alice", "Jack", "Bob"]
。
通过以上的函数,我们总是能得到一个唯一的继承顺序。
请你实现 ThroneInheritance
类:
ThroneInheritance(string kingName)
初始化一个ThroneInheritance
类的对象。国王的名字作为构造函数的参数传入。void birth(string parentName, string childName)
表示parentName
新拥有了一个名为childName
的孩子。void death(string name)
表示名为name
的人死亡。一个人的死亡不会影响Successor
函数,也不会影响当前的继承顺序。你可以只将这个人标记为死亡状态。string[] getInheritanceOrder()
返回 除去 死亡人员的当前继承顺序列表。
思路
init
是初始化国王,也就是根节点;birth
是 xx 生了 yy;death
是某个人挂了;getInheritanceOrder
返回继承人序列。
那么问题就在于用什么样的结构去存储这样的树。对于 Python 来说,我倾向于用哈希表模拟树。哈希表的格式为:
{
"name": [child1, child2, ...]
}
这样可以解决生育的先后顺序问题。
那么某个人挂了怎么办?感觉可以放一个哈希集合记录;
怎样返回继承人序列?因为嫡长子继承制,因此可以实现一个函数去递归获取它的孩子。
最终代码:
想得太多
defaultdict
是来自于 collections
的,它是工厂函数。应该是符合工厂方法模式 的数据结构。
例如这里使用的 defaultdict(list)
,在访问一个不存在的 key 时,它会使用预设的工厂函数创建默认值(这里是 list)并返回,可以实现更简洁、高效的代码逻辑。
而如果使用默认的 dict
,如果通过 dict[key]
去寻找一个不存在的值则会抛出 KeyError
。