狗家油管上门面经

如果广告是好几个数量级的其实只要关注单位时间收益就可以了。因为你默认可以找到无缝连接的广告。即便找不到，你也有了dfs的优先序列，而不是全局load完。说白了就是凑零件，当你零件几乎无限多的时候你总能找到match，这时候就要求每个部位都是最高质量的零件就可以了。

hlckl123456 发表于 2018-9-16 09:12
union find所以子，都是和父距离1的
你和trie搞混了吧？

啊我知道find平均是O(1)，不过你建立起union find的数据结构得O(n)吧。你的意思是如果数据结构建好了之后查一次是O(1)？

sxhexe 发表于 2018-9-16 12:35
啊我知道find平均是O(1)，不过你建立起union find的数据结构得O(n)吧。你的意思是如果数据结构建好了之后 ...

对的..  这道题的核心点就在考find
初始化 union find 和 bfs时间复杂是一样的。
空间复杂度union find 是O(n) 而bfs 最差能到O(n^2)

find 操作 union find 只要O(1)  bfs 最差能到O(n)

hlckl123456 发表于 2018-9-17 00:33
对的..  这道题的核心点就在考find
初始化 union find 和 bfs时间复杂是一样的。
空间复杂度union find ...

我突然想到，这题union find好像不行？
因为这个family tree是有方向性的，但是union find只看连通性。比如A的爸爸和妈妈是连通的(通过A)，但是他们就没有共同的祖先。

sxhexe 发表于 2018-9-17 00:55
我突然想到，这题union find好像不行？
因为这个family tree是有方向性的，但是union find只看连通性。 ...

你说的对哈，那就只能用楼主那个方法了。

hlckl123456 发表于 2018-9-8 13:54
第三题应该是union find，union find 找祖先的时间复杂是O（1）

第四题

你这样的话重复的字符怎么处理？会映射到不同的数字。

liweiheng 发表于 2018-9-17 08:11
你这样的话重复的字符怎么处理？会映射到不同的数字。

嗯嗯，这确实是要考虑的一个问题。
我感觉具体做法就是
单词：ABBBC -> CBBBA
位置：12345 ->  52341
将字母的所有位置都存入map
比如: {A : [1]} {B:[2, 3, 4]}
映射的是根据前一个字母的位置，在对应的map选择相应的位置加上去
比如 这里 C的位置是5  5>B的最大位置，也就是4
所以B就从2开始，  然后第二个B 根据前面的的位置2，在[2,3,4]里查找，发现3可以
所以映射就变成
单词：ABBBC -> CBBBA
位置：12345 ->  52341