本命年感恩节前挂经

第一题除了用拓扑排序，感觉上也可以用标准的tree来做，继承顺序就是preoder traverse
然后用一个hash<name,(node,parent_node)>存储对应名字的人的tree node以及其parent的tree node
birth就是接child
death就是把对应node的child接上去去

试着做了一下第一题，不知道思路对不对，楼主可以查看一下和题意是否对应。

另外对于第四题：如果目标字符串是 abcde, 我猜的是 amcne，应该返回3吧，如果我猜的是acemn是不是应该返回1，也即只有位置和字符同时对应了才是猜对了一个字符。这题好像有点儿难。谢谢！

你这四道题有点儿太难了，都这么难的话去面试也没啥意义了

请问楼主，第二题给一个有向图返回所有从起点到起点的环组成的图，输入只有一个起点，能讲一下思路吗，不是很明白怎么做，谢谢

第三题是 利扣 刘漆留

第三题是 利扣 刘漆留

补充内容 (2018-1-20 06:54):
不好意思以为网页没反应点了两次发重了

能问一下第二题是考Johnson's Algorithm 么，不是太明白题目的意思，也就是最终的环肯定是包含题目输入的起点么？
还有楼主说用Topographic sorting，我没明白这有什么关联，正常DFS不就可以么

问下第四轮猜单词的思路是什么？谢谢

第二题我解释的不太清楚。其实这个图就是一个链表，只不过链表中每个节点可以指向多个节点，这样给了起点就可以遍历整个图，每个点可以有一个值（这个值好像是不会重复的），要求是找出这个链表是否存在一个包含起点的环。意思是可以包括环，但环不能包括起点。还是比较简单的，DFS做也可以，但是如果每个点的值可以重复就非常复杂了

MoeMoeee 发表于 2018-1-17 08:04
第一题除了用拓扑排序，感觉上也可以用标准的tree来做，继承顺序就是preoder traverse
然后用一个hash存储 ...

bingo~我是用的preorder，但是具体实现不太一样