狗家自行车题超级无敌加强版

KenZhuJMHK 发表于 2018-10-10 06:53
我的想法是从每辆车出发，做BFS，每层BFS都把所有车做了。当任何一辆车找到一个人的时候，把车和人都拿掉， ...

obstacle不太有意义，要仔细算距离的话O(1)应该没问题，不过面试官要求用的BFS做第一问。我觉得面试官想考察的是先提出criteria，然后在这个criteria下解决抢车的问题

kwang75 发表于 2018-10-10 06:54
这个我觉得你得先跟面试官clarify清楚吧？我当时上来就问，你是想让我optimize某一个人还是所有人。他说 ...

嗯当时确实问了要怎么optimize，他说你随意，自己提一个优化目标，我说那就全局距离和最小，他说这个不好你再说一个……

我面的是求最远的最小值  我直接用的DFS 暴力解 估计时间是 O(n^m) 然后稍微 剪枝 了一下 也不知道 面试官满不满意 感觉没用到他之前要我写的函数

个人建议可以和hr联系说明面试官有一定的过失，但态度要非常好。这样如果你本来就过了，也不会有什么影响，如果本来没过，就存在给你重新安排一轮的可能性。有希望就不要放弃啊！

很简单的DFS题啊，

n个人和n辆车的坐标都有了，存到array或list里都可以，

距离就用 |x1 - x2| + |y1 - y2| 来得到，

第一个人有n种选择，第二个人有n-1中选择 ，第三个人有n-2中选择，... ，直接dfs求出最小的res

复杂度O(n!)，

放在leetcode里撑死了medium难度。

匿名者 发表于 2018-10-10 13:53
很简单的DFS题啊，

n个人和n辆车的坐标都有了，存到array或list里都可以，

有obstacle的老哥，距离不能这么算

KenZhuJMHK 发表于 2018-10-10 06:53
我的想法是从每辆车出发，做BFS，每层BFS都把所有车做了。当任何一辆车找到一个人的时候，把车和人都拿掉， ...

如果有两辆车到一个人的距离相同怎么办

我觉得这题目出的有问题，按照出题人的思路那就是拿所有距离放heap里pop，这是贪心，显然不是全局最优，也谈不上什么criteria（因为无法定义出criteria），要是全局最优（所有人拿车总距离最小）那就是brute force，O(n)。

补充内容 (2018-12-3 02:59):
O(n!)

感觉面试官希望你用queue + bfs方法做。

queue用来存储所有人的位置，如果找到一辆车说明找到这个人匹配的车，如果找到多辆车就放回queue，后面再处理，这样解可以使得最大距离最小，面试官好像在往这个方向引导你。

这道题其实挺简单的，LC上现在有一模一样的题了。一个TreeMap和memorized array就解决了。