facebook 电话＋onsite

b01501085 发表于 2017-10-21 11:22
樓主第一題可以在細講一下嗎？看不太懂L走法

一共三步，可以分陪在左右方向或者上下方向，配比是1+2

左或者右2步 －》上或者下一步
上或者下2步 －》左或者右一步

第一题
L型走法转换成坐标变换数组的话就是1，2这样的8种变换可能 dfs或者bfs计数就行了 但是可能有重复子问题 所以可以优化成动规保存子问题吗？

Alvin_Bao 发表于 2017-10-23 14:58
第一题
L型走法转换成坐标变换数组的话就是1，2这样的8种变换可能 dfs或者bfs计数就行了 但是可能有重复子 ...

搞错了，是不同的路径数没办法用动规优化

lausteven 发表于 2017-10-23 12:00
从右到左linear search会更快， O(m+n)

请问这个这个linear search具体是怎么操作呢？
可不可以每行search，每次search到的最most left的点 + 1 作为下行开始的right点

楼主，走L那题，除了普通BFS，DFS之外，可以用hashmap保存计算结果来避免重复计算吗？

ONSITE第一题先OR起来， 然后找最左边1的位置， 再一行一行找那个位置有1的？

JohnnyHuo 发表于 2017-10-24 10:57
楼主，走L那题，除了普通BFS，DFS之外，可以用hashmap保存计算结果来避免重复计算吗？

应该也可以可以，我用的dp做的

hxiang-bjtu 发表于 2017-10-24 03:18
请问这个这个linear search具体是怎么操作呢？
可不可以每行search，每次search到的最most left的点 +  ...

就是这样做，而且起步是0的话可以直接跳过

Alvin_Bao 发表于 2017-10-23 14:58
第一题
L型走法转换成坐标变换数组的话就是1，2这样的8种变换可能 dfs或者bfs计数就行了 但是可能有重复子 ...

我用的是dp，面试官的意思是cache也可以

lausteven 发表于 2017-10-24 16:14
应该也可以可以，我用的dp做的

可以讲一下DP的思路吗？ DFS+cache还好理解， 但是DP的话，状态方程是什么样的呢