王位继承

写了一个double linked list的方案， listnode里多一个指针指向最后一个孩子节点。但是这样做birth不再是O(1)， 而是O(h) h是树（假象）的高度， 并且death的时候不能删除listnode，因为如果该节点是lastnode,删除的话就无法确定队尾了。因此在get_order()时，还是需要遍历一遍list... ，

1. class ListNode:
   
2. 
   
3.     def __init__(self, name):
   
4.         self.name = name
   
5.         self.lastkid = None
   
6.         self.next = None
   
7.         self.pre = None
   
8.         self.dead = False
   
9. 
   
10.     def __repr__(self):
    
11.         return 'ListNode %s' % self.name
    
12. 
    
13. # 要求 getOrder O(1)
    
14. class ThroneInherit1:
    
15. 
    
16.     def __init__(self, rootname='king'):
    
17.         self.head = ListNode(rootname)
    
18.         self.names = {rootname: self.head}
    
19.         
    
20. 
    
21. 
    
22.     def get_order(self):
    
23.         ans = []
    
24.         node = self.head.next
    
25.         while node:
    
26.             if not node.dead:
    
27.                 ans.append(node.name)
    
28.             node = node.next
    
29.         return ans
    
30. 
    
31. 
    
32.     def birth(self, parent, name):
    
33.         pnode = self.names.get(parent, None)
    
34.         if not pnode:
    
35.             return False
    
36.         if name in self.names:
    
37.             return False
    
38. 
    
39.         cnode = ListNode(name)
    
40.         self.names[name] = cnode
    
41.         tail = pnode
    
42.         while tail.lastkid:
    
43.             tail = tail.lastkid
    
44.         tailnext = tail.next
    
45.         tail.next = cnode
    
46.         cnode.pre = tailnext
    
47.         if tailnext:
    
48.             cnode.next = tailnext
    
49.             tailnext.pre = cnode
    
50.         pnode.lastkid = cnode
    
51. 
    
52. 
    
53.         return True
    
54. 
    
55.     def death(self, name):
    
56.         if name not in self.names:
    
57.             return False
    
58.         node = self.names[name]
    
59.         del self.names[name]
    
60.         node.dead = True

复制代码

贴一个我的C++实现，请大家指正

* 利用Hashmap实现常数级的检索
* 需要维护lastChild指针以便于在Birth的时候知道在哪儿插入新的节点
* 子到父的关系的维持使用了字符串记录父亲的名字，相比使用指针而言，这样的好处在于当父亲去世后不用更新其在每一个孩子中的链接，而只需要删除父在Hashmap中的记录即可
* 这个实现有个缺陷在于在父亲去世后，不能够再有属于他的儿子出生，虽然理论上是有可能的

1. 
   
2. typedef list<string>::const_iterator LSI;
   
3. 
   
4. struct Person {
   
5.     LSI self, lastChild;
   
6.     string name, parentName;
   
7.     Person(string name, string parentName, LSI self)
   
8.     : name(name), parentName(parentName), self(self), lastChild(self){};
   
9. };
   
10. 
    
11. class Solution {
    
12. private:
    
13.     unordered_map<string, Person> dict;
    
14.     list<string> inherientQueue;
    
15. public:
    
16.     void Birth(string father, string son) {
    
17.         if (dict.count(father)) {
    
18.             LSI it = inherientQueue.insert(next(dict[father].lastChild), son);
    
19.             dict[father].lastChild = it;
    
20.             dict[son] = Person(son, father, it);
    
21.         }
    
22.     }
    
23.     void Death(string name){
    
24.         if (dict.count(name)) {
    
25.             string father = dict[name].parentName;
    
26.             if (dict.count(father) && dict[father].lastChild == dict[name].self)
    
27.                 dict[father].lastChild = prev(dict[name].self);
    
28.             dict.erase(name);
    
29.             inherientQueue.erase(dict[name].self);
    
30.         }
    
31.     }
    
32.     list<string> GetInherientSequence(){
    
33.         return inherientQueue;
    
34.     }
    
35. };
    

复制代码

抛砖引玉
觉得写double linked list在面试时实在太难bug-free了
求更精简思路更清晰更适合面试的写法!!

写了一个birth和death都是O(1)
并且death同时会执行删除的实现
get_order为了把tree转list要O(N), 不需要的话则可O(1)

概念是
4个pointers: 最近的兄, 最近的弟, 最大的孩子, 最小的孩子
死了就把最大的孩子接在最近的兄后面
并把最小的孩子接在最近的弟前面

以下是code

您好！
本帖隐藏的内容需要积分高于 130 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 130 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

写了一个python的code，欢迎大家讨论指正
用linkedlist和map
birth的话，找到parent的last child O(1), 加一个childNode, O(1)
death的话，找到人的Node，把名字改成特殊符号。。。O(1)
getOrder的话，走一遍，遇到特殊符号不打印。。。

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2019-4-9 05:02):
Person那里不用prev的。。。一开始准备用double linked list，后来没用忘删了。。。

summernight 发表于 2019-4-1 10:23
贴一个我的C++实现，请大家指正

* 利用Hashmap实现常数级的检索

不太熟C++可能是我没看懂
发现一个问题是death时用prev会指向前一个brother的last child
然后这个brother有新的child时会产生问题
原本的parent的birth会出错

1.     def test_special_cases(self):
   
2.         self._throne.birth('king', 'a')
   
3.         self._throne.birth('king', 'b')
   
4.         self._throne.birth('a', 'aa')
   
5.         self._throne.death('b')
   
6.         self._throne.birth('a', 'ab')
   
7.         self._throne.birth('king', 'c')
   
8.         self.assertListEqual(list(self._throne.get_order()),
   
9.                              ['king', 'a', 'aa', 'ab', 'c'])

复制代码

兄弟们有没有人能给个java的啊。感激不尽！

Lunluen 发表于 2019-4-9 17:22
不太熟C++可能是我没看懂
发现一个问题是death时用prev会指向前一个brother的last child
然后这个broth ...

我觉得你说的是对的，光维护LastChild不够，问题在于最小儿子A的儿子B出生后，如果父亲C又有了一个新儿子D，就会排列为C ... A D B，应该是C...A B D。

这里可以更改已经发帖的内容么？

14417335 发表于 2019-3-13 22:26
**** 本内容被作者隐藏 ****

楼主请问follow up的时候，你提到的方法实现了吗？还是说只讲思路就可以？多谢

jscw 发表于 2019-3-14 01:50
insert a node just before its younger brother. O(1)

但是你还是需要从链表头部开始找要yonger brother的位置啊，怎么会是O(1)呢？

umialpha 发表于 2019-3-27 19:50
写了一个double linked list的方案， listnode里多一个指针指向最后一个孩子节点。但是这样做birth不再是O( ...

有个问题，42， 43行，为什么要用while循环？会不会导致本来是王的最后一个儿子变成最后一个皇子的最后一个儿子。