Google MTV 面经

kwang75 发表于 2018-8-15 14:09
讲真，不懂bfs怎么做。。。
首先这题lc365是找两两之间的gcd然后拿target去模这个gcd
那很明显拓展到n ...

bfs就是枚举所有的操作 然后没遍历过的进队。。可以是清空任意，从水池进水把任意，两两之间互相倒

lajalex 发表于 2018-8-16 21:44
bfs就是枚举所有的操作 然后没遍历过的进队。。可以是清空任意，从水池进水把任意，两两之间互相倒

我理解的你的想法是，把所有"操作"遍历。但是我不懂为什么要用队？
如果要枚举，为什么不用dfs呢?
我的理解是，bfs是一层一层遍历的。也就是存在一些关系，让每个点(这里是杯子)在每一层只能遍历一次。这题我觉得不存在这种关系。你完全可以无限倒入一个杯子再倒入另一个，或者两两互倒。当然这只是我的想法啊

这个系统设计怎么做好呢？

最后一轮，可不可以直接用 vol % gcd(v1,v2,..,vn) == 0 来判断？

这个杯子装水的问题是不是就是一个N-ary tree的问题，root是0，N个child，每个child又有N／2N个child （加水或者倒水），然后搜里面的path sum， BFS做，加一个visited
queue里面放的是量到的水。

最后一轮参考利口的话应该是道数学题。要找所有杯子的GCD. 可以两两相找取最小的。然后看看是否可以被target整除。不过三姐出这道还真是不想让人过的节奏。

补充内容 (2018-9-24 05:02):
找GCD应该是这个方法：https://www.geeksforgeeks.org/gcd-two-array-numbers/

楼主好人
能否问一下第二轮简单的矩阵题目，小哥都问了哪些follow up？