Google8.6 热滚滚的面经

楼主已经毕业了嘛？

我觉得这题跟滑雪不太一样，这个要求的是连续路径,可以根据DP继续优化。这样的话根据矩阵里面每个点的值和它的坐标建一个hashmap。比如（0， 0）是7，且只有一个7，那么使得7为key，value为一个list，里面只有一个element就是1。
然后从数值最小的开始，此图中是1，然后找到1对应的list of coordinates，接下来再往下找2对应的list，如果中间有点和parent point只隔1，那么证明有路径过去，可以继续进行dfs，直到它的周围没有点可以比此点恰好大1.然后backtrace的时候标记child都遍历过了的点为visited以及从此点开始最长的长度，以后再碰到这个点的时候直接加上这个点至终点的长度。有个全局变量记录所有点得到过的最长路径，最后返回即可
最坏情况下路径经过每个点，这样复杂度是O(n^2).另外它还排除了周围没有比它恰好小1的点（这块儿的时间复杂度我也不知道怎么描述了），另外可以进行剪枝。如果max value - current value < current max 就没有必要再继续往大了搜了。

嗯，记忆化搜索。就是POJ滑雪那题。

我半年前电面也是这题，我是简单的dfs, follow up 提速就加个hashmap

确实和滑雪有一丝丝差别。
需要把四周核查从
if(oriMatrix[i][j] > oriMatrix[i][j-1]) （四边之一）
变为
if(oriMatrix[i][j] == 1 + oriMatrix[i][j-1])

这样才是连续的。 滑雪是可以断开的，只要有落差就行。

woshiee123 发表于 2015-8-6 19:48
哪里有这道题的解法呢？谢谢

google 一下 “poj 1088“ 不就有了
http://www.cppblog.com/abilitytao/archive/2009/02/19/74271.aspx
http://my.oschina.net/Alexanderzhou/blog/203111
连豆瓣上都有： http://www.douban.com/note/209925117/

对，这题楼上的童鞋们已经提到了，用记忆化搜索能够很快的解决，需要用到dfs和HashMap。

弱弱的问一下请问DFS 怎么用hashMap 加速? 如果2维array没有重复的element 用一个2维来mark visited 因该就可以了? 有用hashMap的必要吗?

say543 发表于 2015-8-17 08:10
弱弱的问一下请问DFS 怎么用hashMap 加速? 如果2维array没有重复的element 用一个2维来mark visited 因该就 ...

过了好久，我也记得不是很清楚了。
用楼主发的例子吧，当时给我的好像也是这个例子：
7  8  6
9  4  5
2  3  1
我好像就只找递增的序列，比如当我找完前两排的时候，存在hashmap里面就是7->8, 8->8, 6->6, 9->9, 4->6，5->6等。 这时我找第三排的2然后找到3再找到4，发现4已经在map里了，就可以直接得出终点在6，从而在map里存入3->6, 2->6。同时每次存的时候我也记录一下max distance。存了2->6还要存3->6是为了保证每个数字只visit一遍。其实不用hashmap, 直接用个新的2d array存每个数字的终点也可以。
至于你说的只存一个visited的bool, 我猜你是同时搜从当前位置的递增和递减序列然后加起来长度对吧？ 感觉没啥问题还更省空间呢！厉害！

alucardzhou 发表于 2015-8-16 07:18
google 一下 “poj 1088“ 不就有了
http://www.cppblog.com/abilitytao/archive/2009/02/19/74271.aspx ...

豆瓣这个解法有没有问题啊？这个递归似乎没有初始值啊？第一个值代进去什么时候停止？