狗昂赛2.14

给一堆点，求距离最小的k对，这怎么做的呢？能不能多说点呢？

兔纸那题有菱形会有什么影响吗？感觉似乎还是一样的。

月下一只喵 发表于 2017-2-18 06:14
给一堆点，求距离最小的k对，这怎么做的呢？能不能多说点呢？

http://www.geeksforgeeks.org/closest-pair-of-points/

或者是sweep line algorithm

第四题可以用O(n^2) time么?

兔子的题没有那么复杂吧？就是两个一起BFS，然后用两个set记录各自所有的祖先，一边BFS一边检查是不是当前的这个兔子，出现在对方的祖先里？

而且所谓的兔子 其实就是binary tree吧

吃啥才算成熟 发表于 2017-2-19 06:31
兔子的题没有那么复杂吧？就是两个一起BFS，然后用两个set记录各自所有的祖先，一边BFS一边检查是不是当前 ...

事后看确实不复杂，可不是tree，因为可能是有环的

Loh_zhang 发表于 2017-2-19 06:33
事后看确实不复杂，可不是tree，因为可能是有环的

哦哦哦！原来近亲结婚的catch在这里~
考虑环的话，只要加上一步，check自己的set里面包含过了当前这个兔子了，就不再从这个兔子继续BFS了就好吧

LRU和linkedHashMap不一样吧？？？LinkedHashMap里面的顺序是insert的顺序吧，直接一个linkedlist和map就行了。LRU里面，每次put和get都会改变顺序，涉及手动改变linkedlist，更复杂吧。

吃啥才算成熟 发表于 2017-2-19 07:08
LRU和linkedHashMap不一样吧？？？LinkedHashMap里面的顺序是insert的顺序吧，直接一个linkedlist和map就行 ...

LinkedHashMap你把需要update的entry先remove后加进去不就可以了

关于兔子这题，我在想，如果兔子的节点里面不止包含父母的节点，还包含所有它的孩子的节点，那不是直接就能用无向图的DFS或者BFS做了么？

1. struct Rabbit {
   
2.     // related could be parents and children
   
3.     vector<Rabbit*> related;
   
4. };

复制代码