狗家新鲜面经

lucifer77 发表于 2021-04-14 19:40:08
请问第四题是lc的幺儿齐齐吗？

是的 楼上有人说了 可惜我没做过（捂脸

匿名者 发表于 2021-4-15 10:41
是的 楼上有人说了 可惜我没做过（捂脸

不好意思 页面打开后没刷新 没看到前面有人问过了hhh 谢谢楼主！请问第三题有什么限制条件吗？比如必须4个player分的一样多？followup是会指定哪两个相邻的要分给同一个人还是随便有一个就行？非常感谢！

匿名者 发表于 2021-4-15 10:38
第五题是有向图

第三题非followup我用的是random.choice，followup没做出来（捂脸 如果有人有思路的话求 ...

第三题followup感觉的确没什么思路。。。 不过一题没答出来应该问题不大。

第五题lz用什么做的？ DFS吗？

多谢。

bigboss789 发表于 2021-04-14 19:52:49
第三题followup感觉的确没什么思路。。。 不过一题没答出来应该问题不大。

第五题lz用什么做的？ DFS吗？

我用的是BFS，因为BFS第一个找到的cycle就是最短的（忘了说 一定是包含特定某个node的cycle

lucifer77 发表于 2021-04-14 19:48:17
不好意思 页面打开后没刷新 没看到前面有人问过了hhh 谢谢楼主！请问第三题有什么限制条件吗？比如必须4个player分的一样多？followup是会指定哪两个相邻的要分给同一个人还是随便有一个就行？

是的 限制条件就是一样多 uniform distribution
followup是上下左右随便其中一个就行

匿名者 发表于 2021-4-15 10:54
我用的是BFS，因为BFS第一个找到的cycle就是最短的（忘了说 一定是包含特定某个node的cycle

哦， 就是说题目指定比如说是从node 1出发，找最短的cycle吗？ 因为如果是有向图， 用BFS找cycle可能会出问题。 如果一个node有两个indegree， BFS可能会误认为是cycle。

如果第三题的followup上下左右随便。那把64ge格子看成32个，每两个同行相邻的grid都分配给一个player。这样不知道行不行。。。 感觉这样也太简单了。。。 估计不对

bigboss789 发表于 2021-04-14 20:03:53
哦， 就是说题目指定比如说是从node 1出发，找最短的cycle吗？ 因为如果是有向图， 用BFS找cycle可能会出问题。 如果一个node有两个indegree， BFS可能会误认为是cycle

第三题这样不可以的，因为要randomly assign，如果看作一个的话那都是相同的方向了

第三题可以用dfs + 堆栈吧

赞一个  非常有用的信息

想问下lz第一题和一衣衣零具体有哪里不一样呀