热乎乎的狗家电面

fx_xj 发表于 2018-3-10 04:50
对，我第一反应也是union find。。再过十五分钟面谷歌

Good luck!

haifengc 发表于 2018-3-10 08:44
我的疑问是给的是半开区间[0,1)，怎么成全闭的,y inclusive

比如让你生成[10, 100]之间的随机数，那么

double y = 91 * x + 10，最后对y向下取整就好了。

nicemayi 发表于 2018-3-10 09:05
比如让你生成[10, 100]之间的随机数，那么

double y = 91 * x + 10，最后对y向下取整就好了。

谢谢你，
这样挺好的，
就是感觉最后不是uniform

nicemayi 发表于 2018-3-10 04:49
这道题是union find应该。

得问清楚有没有transitive，没有的话可以出的非常难。

XericZephyr 发表于 2018-3-10 11:26
得问清楚有没有transitive，没有的话可以出的非常难。

transitive是什么？

nicemayi 发表于 2018-3-10 11:56
transitive是什么？

假设 a ~ b, b ~ c， 需要问清楚  a 和 c 是否similar。如果是，就是这个关系有transitive，相当于undirected graph，可以用union find找connected component，  如果不，此题不能用union find。

XericZephyr 发表于 2018-3-10 12:00
假设 a ~ b, b ~ c， 需要问清楚  a 和 c 是否similar。如果是，就是这个关系有transitive，相当于undire ...

按照楼主的说法，这道题应该是无向图。

fx_xj 发表于 2018-3-10 04:46
感觉这个题和399区别还是挺大的吧。。。。

这个题目我觉得union find可以写的 399的方法也是可以的 其实就是考察图的连通块问题嘛

stingray 发表于 2018-3-10 04:49
第一题什么思路呢？ 一遇到rand的题就很懵。。。。

这个题的思路是rand() * (y - x + 1) + x

XericZephyr 发表于 2018-3-10 12:00
假设 a ~ b, b ~ c， 需要问清楚  a 和 c 是否similar。如果是，就是这个关系有transitive，相当于undire ...

其实没有告诉用什么数据结构 主要还是看你怎么建图的
我的建图方式是无向图