Google 四月初上门

umialpha 发表于 2019/04/04 16:16:16
第二轮 无限大棋盘，楼主用A*算法了么？如果没有用，bfs的时候是怎么样定义行走的规则呢？

我翻到去年一个一样的题，是被当场要求写bidirectional BFS，也是挺壮烈的

第五题的Followup 可不可以这样做，原题得知删除前K%的平均就也知道total是多少
F(K) 表示删除前K%大的总额，那F(H)-F(L) 就是H%到L%之间的总额了，直接维护两个原题的class这样

kaipeng21 发表于 2019/04/05 02:39:30


我翻到去年一个一样的题，是被当场要求写bidirectional BFS，也是挺壮烈的

求一个链接

Hushleo 发表于 2019-4-5 01:18
请问一个从头一个从尾不是反着的吗，要match的部分都得正着来，还是我没理解意思？

刷题网上我理解的是求最大overlap，所以我认为是求前缀和后缀的最长匹配，你说的这个例子（一个包含另一个），刷题网上说了不考虑。我也不知道是不是我理解错了....举个例子来说abcde, cdefg, 那么superstring应该是abcdefg？

昨天翻到的不过没标记现在找不到那个帖子了，倒是看到有人po了一个连结感觉应该是解答，我还没看就是（着墨猫捉老鼠题中．．．）
https://blog.csdn.net/a120705230/article/details/41822575

补充内容 (2019-4-5 14:34):
Oops 不小心按错回覆了

umialpha 发表于 2019-4-5 14:06
刷题网上我理解的是求最大overlap，所以我认为是求前缀和后缀的最长匹配，你说的这个例子（一个包含另一 ...

昨天翻到的不过没标记现在找不到那个帖子了，倒是看到有人po了一个连结感觉应该是解答，我还没看就是（着墨猫捉老鼠题中．．．）
https://blog.csdn.net/a120705230/article/details/41822575

kaipeng21 发表于 2019-4-5 14:33
昨天翻到的不过没标记现在找不到那个帖子了，倒是看到有人po了一个连结感觉应该是解答，我还没看就是（着 ...

猫和老鼠你用的是官方solution么

umialpha 发表于 2019/04/05 15:31:14


猫和老鼠你用的是官方solution么

好像dfs都有case 是错的，只能看官方，不过我觉得这题要考出来写到完全bug free基本上是不太可能的

Hushleo 发表于 2019-4-5 01:13
是不是有个corner case需要考虑下：String a = "abcdefg", String b = "cde"

说的对。

kaipeng21 发表于 2019-4-5 14:33
昨天翻到的不过没标记现在找不到那个帖子了，倒是看到有人po了一个连结感觉应该是解答，我还没看就是（着 ...

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