Google 四月初上门

umialpha 发表于 2019/04/05 16:26:20


帖子里最后用了一个枚举法也太魔幻了吧。我感觉是不是bfs就够了...

不晓得，我只觉得楼主运气很背拿到的题都是我觉得近期看到最难的几个

猫捉老鼠升级版频率x2，看到二维数组+起司猫鼠的时候我就心凉了

Hushleo 发表于 2019-4-5 01:08
首先不带障碍的BFS肯定没问题，因为马理论是可以到达棋盘的任何位置的。至于带障碍的follow up没让写code ...

“马理论”，楼主准备的好充分。请问一下，需要向面试官证明，这个理论吗？我一直有疑问，如果棋盘没有边界，则BFS的queue，有可能一直不会为空，则bfs会一直下去。

只身回马枪 发表于 2019-4-15 06:44
“马理论”，楼主准备的好充分。请问一下，需要向面试官证明，这个理论吗？我一直有疑问，如果棋盘没有边 ...

层主这么名字这么diao来问我“马理论”好怕怕。。。其实我想说的是 “马，理论上” 。。。这个如果你下过棋的话应该很好证明，从某个位置起，三步之内可以到它外面一圈的八个点，那么归纳法就知道可以到无限大边界上的所有点。难点其实还是有障碍的时候不能到的情况确认，不过也只是follow up，理论能说服面试官就还行。

Hushleo 发表于 2019-4-15 08:11
层主这么名字这么diao来问我“马理论”好怕怕。。。其实我想说的是 “马，理论上” 。。。这个如果你下过 ...

所以，楼主采用的方法是，BFS的时候，人为的加入一个“边界”？（比如，然后，判断当前点向下一层扩散时，是否出界吗）
举例：起点【0，0】，终点【100，100】，则，我人为的设计一个边界（bottom-left【-200， -200】， top-left【-200， 200】，bottom-right【200， -200】，top-right【200， 200】），在这个边界条件内复用第一问的代码。（200这个边界是拍脑门定下的，只要保证终点在边界内，并且不是紧挨着的）
这样理解对吗？

只身回马枪 发表于 2019-4-15 23:37
所以，楼主采用的方法是，BFS的时候，人为的加入一个“边界”？（比如，然后，判断当前点向下一层扩散时 ...

是的，我是这个意思。我觉得这样应该是没问题的。一个不严格的证明：
假设在无限大平面内存在一条从起始S到终点D的路径path。
    如果这条路径根本不需要进入外面加这个框，我们定义的BFS显然可以找到这条路径；
    否则的话对于该路径path，从两头S和D分别出发，一定分别有第一次进入我们定义的外框的点A和B，那么很容易证明仅利用外框我们就可以找到从A到B的马步跳法。从而我们找到了一条在我们自定义边界内的路径path1，而且这条path1一定可以被我们的BFS找到。Over

感谢楼主非常详细并且清晰的解释。

楼主的题感觉地狱难度。。。

Hushleo 发表于 2019-4-5 00:51
第一轮补充：老鼠先走，双方轮流，每次步数走

他们能选择走0步吗？

考猫和老鼠这种题的面试官，要么是他真的是竞赛精英级别的牛人，觉得这种题都不如他法眼； 要么就是故意耍坏根本不想让人过。
话说楼主的题目真的绝了，基本每一个都是典型的难题。哪怕第三轮一经简化不要求用旅行商算法来求解了，但这种状况下就得考虑KMP来快速匹配了。