狗去onsite

bdhmwz 发表于 2018-4-27 17:39
第三题应该是在bfs基础上加状态，就是到达当前位置且更改次数为0或者1的情况下的最短路径。这个思想可以扩 ...

可是你怎么知道修改哪一个是最短路径

ruiwanbing 发表于 2018-4-28 05:10
按照分隔符分割。

default的分隔符是？还是说要处理多种分隔符的情况？需要做如下假设么：
user_id1: contents
user_id2: contents
这样打开文件之后，可以读出每行，然后选：前的做user id，count user id，然后做top k
这道题考点是top k还是字符串的处理阿~不知道字符串处理不熟的话，可不可以现场问面试官换成其他type的数据求top k呢。

第三题的follow up感觉就是先bfs一次，记录下最短路径，然后看1里面有没有一个1被3个属于最短路径的0包围，如果是，这个1就可以被设为0从而缩短最短路径，没有则还是原来的长度，不知道对不对

#2. 先按时间sort一遍。用dict记录每个candidate的vote.然后从中找出top

有更好的方法吗？

ruiwanbing 发表于 2018-4-28 05:11
可是你怎么知道修改哪一个是最短路径

在队列里面放node，node包含当前坐标，修改次数和已走距离，第一次走到target的时候就是找到了最短路。当然还需要一个visited[x][y][count]，表示每个位置修改count次是否已经走过就可以了。

woderegou 发表于 2018-4-28 05:35
第三题的follow up感觉就是先bfs一次，记录下最短路径，然后看1里面有没有一个1被3个属于最短路径的0包围， ...

我的想法是，先找出最短路径，然后对于最短路径上的每一个墙，看我们能不能打通它来穿墙而过。这种case就是墙的厚度是1，然后墙两边都是最短路径

比如最短路径是

00000
11110
00000

那打掉第二行第一个1就可以了。我们的目标就是找出被最短路径夹住的墙，然后去掉每一个看是否是路径缩短

其他case貌似缩短不了，不知道我是不是少想了case

比如墙的厚度是2，那没法减少，如果墙没有被最短路径夹住，比如

0000000
1111110
0000010
1111110
0000000

那打通任意一个都没办法是路径缩短

补充内容 (2018-4-28 14:41):
我给的例子是从左上角走到左下角的最短路径

第四题是用PriorityQueue和HashMap 吗？

bdhmwz 发表于 2018-4-27 17:39
第三题应该是在bfs基础上加状态，就是到达当前位置且更改次数为0或者1的情况下的最短路径。这个思想可以扩 ...

有无经典算法，我感觉所有跟"0"相连的"1"都要查看一遍 复杂度是n^3log(n)

kevinxw 发表于 2018-4-28 14:40
我的想法是，先找出最短路径，然后对于最短路径上的每一个墙，看我们能不能打通它来穿墙而过。这种case就 ...

看了你这个例子我就知道我的行不通了，然后我觉得你这个好像也不行，比如这个例子：
00000000
11100110
11111110
11100110
00000000
这个该打掉的地方就没有被最短路径包住

bdhmwz 发表于 2018-4-28 13:55
在队列里面放node，node包含当前坐标，修改次数和已走距离，第一次走到target的时候就是找到了最短路。当 ...

对哦，这个方法好像可以，就是加了个变量，来记录能穿墙的次数，如果次数大于0，可以选择穿墙或者不穿来遍历，但是感觉这样好像dfs写起来更容易吧，不知道理解对了没