Google Onsite 11.23

第二轮，可以用字典逆向构建tre，例如google，就在tre里面存入elgoog。
stream来的时候，从当前开始，向前查找是否存在以目前字符开始向前的substring就好了。

aiwojiujiu 发表于 2016-1-19 13:43
请问楼主 第一题 是只能走两步还是可以走两步也可以走一步？ follow up有要求写出来吗 还是只探讨思路？

只能走n步。
就是每个格子的步长不一样。
比如到A格子，步长是三步。在B格子，步长是两步。
只探讨思路哈

aiwojiujiu 发表于 2016-1-19 13:53
第二轮，可以用字典逆向构建tre，例如google，就在tre里面存入elgoog。
stream来的时候，从当前开始，向前 ...

这个思路好！赞！

pigmightfly 发表于 2016-1-19 18:28
只能走n步。
就是每个格子的步长不一样。
比如到A格子，步长是三步。在B格子，步长是两步。

原来如此 多谢楼主耐心解答 祝你在google 工作顺利！

pigmightfly 发表于 2016-1-19 18:28
只能走n步。
就是每个格子的步长不一样。
比如到A格子，步长是三步。在B格子，步长是两步。

楼主 按照你的描述 我的理解是：从一个格子，如果想走到其他周围四个格子的任意一个，需要走过的路程都是不同的，例如向左走一步需要2step，向上走一步需要3step等等。
如果我上述理解无误，那么我觉得可以通过Dijkstra方法解答。
BFS一般用于解决edge长度为1的最短路径问题，而Dijkstra用于解决一般性的edge非负的情况。
数据结构可以使用HashSet 和 indexed heap解决。复杂度是nlogn
楼主说的“空间树”的解法一般用来处理NP-hard问题，就是传说中的暴力解法。例如TSP问题，一般可以通过
此法解决。不过最短路径依然需要在空间树中通过BFS解决。例如经典的水桶倒水问题。优化一般用A*。

补充内容 (2016-1-20 09:43):
算法复杂度中的 n 指的是 矩阵中的 边或点 的数量。

aiwojiujiu 发表于 2016-1-20 09:41
楼主 按照你的描述 我的理解是：从一个格子，如果想走到其他周围四个格子的任意一个，需要走过的路程都是 ...

不不不，步长为3就是说可以走三个格子。或者你就理解为在不同的格子上单位时间内走的格子步数不一样

pigmightfly 发表于 2016-1-20 09:50
不不不，步长为3就是说可以走三个格子。或者你就理解为在不同的格子上单位时间内走的格子步数不一样

喔喔 那楼主的做法就是对每一个起始点开始，采用空间树的做法，枚举每一种下一时间的状况，看看最快到何时可以到某个G点吗？

aiwojiujiu 发表于 2016-1-20 09:57
喔喔 那楼主的做法就是对每一个起始点开始，采用空间树的做法，枚举每一种下一时间的状况，看看最快到何 ...

我觉得楼主应该依然是按照从G点开始的BFS策略吧？ 枚举下一层的所有情况，将加一层的所有能到的点的距离＋1

aiwojiujiu 发表于 2016-1-20 09:59
我觉得楼主应该依然是按照从G点开始的BFS策略吧？ 枚举下一层的所有情况，将加一层的所有能到的点的距离 ...

对对，是这样

pigmightfly 发表于 2015-12-9 12:00
map1 还是记录source string的char的位置
a: 0
b: 1

这个的前提应该是没有重复吧？