比赛review帖

vtiaocao 发表于 2018-7-9 00:39
这次竞赛我鸽了。。

话说之前也见过一次这种的。。就是比较大的直接跳了。

看见香肠嘴十元我就害怕 再遇不见这么好看的了。。

肥宅快乐水 发表于 2018-7-8 12:34
https://leetcode.com/contest/weekly-contest-92

[868 | pass]

我看了一下，第865题是一个寻路问题，标准算法应该是 A*（启发式搜索）
https://en.wikipedia.org/wiki/A*_search_algorithm

Discuss里提到了memo和heap，所以基本就是A*的实现了

magicsets 发表于 2018-7-9 02:38
我看了一下，第865题是一个寻路问题，标准算法应该是 A*（启发式搜索）
https://en.wikipedia.org/wiki/ ...

865我看很多人就直接BFS，就是加了一个限定条件，对于一个节点，如果访问过且拥有的key一样就不再访问，如果拥有的key变多了就可以再次访问。不知道这个限定条件怎么想出来的/证明出来的。。。比赛就卡在这个地方了。。

CYCY 发表于 2018-7-9 09:41
865我看很多人就直接BFS，就是加了一个限定条件，对于一个节点，如果访问过且拥有的key一样就不再访问， ...

Key+位置就是“状态”，我们的目标是找到从起始状态（0把key，初始位置）到达某个终止状态的最短路径（全部key，任意位置）。

然后想像一下你有一个巨大的状态图，两个状态之间存在一条边当且仅当两个状态的位置相邻，且满足key持有情况以及可开lock的约束。

要在这个状态图上寻找一条最短路径，可以用暴力BFS，也可以在选择下一步状态时使用某种“聪明”的优先级策略，这一优先级策略方法即为 A*

此外这个问题是有实用价值的，叫做Inventory-Aware Path Finding，做游戏AI时应该会使用，可以看看下面两个链接：
https://gamedev.stackexchange.co ... g-with-lock-and-key
https://www.gamasutra.com/blogs/ ... are_Pathfinding.php

楼主要不要组织打比赛呀

magicsets 发表于 2018-7-9 10:28
Key+位置就是“状态”，我们的目标是找到从起始状态（0把key，初始位置）到达某个终止状态的最短路径（全 ...

6666 你这么一说清晰多了。我以前想的是可以重复经过的BFS，所以总是没想明白。所以应该吧(key + position)当作一个节点，而不是把(position)当作节点，emm，这样明白多了。

kate8528577 发表于 2018-7-9 10:40
楼主要不要组织打比赛呀

giao起来啊 o(*^＠^*)o

每周都只能做三道题。。看到大神们一下就秒杀完了，感到了绝望。。

miugel 发表于 2018-7-10 01:49
每周都只能做三道题。。看到大神们一下就秒杀完了，感到了绝望。。

加油加油, 做三道就比没做的强喇.

三道基本上都是前100的水平, 没毛病

miugel 发表于 2018-7-9 09:49
每周都只能做三道题。。看到大神们一下就秒杀完了，感到了绝望。。

跪拜前一百大佬。。。