Google8.6 热滚滚的面经

hj867955629 发表于 2015-8-27 00:46
豆瓣这个解法有没有问题啊？这个递归似乎没有初始值啊？第一个值代进去什么时候停止？

不好意思，豆瓣是随口一说。请尽量看专业点的解法。

alucardzhou 发表于 2015-8-30 03:26
不好意思，豆瓣是随口一说。请尽量看专业点的解法。

我自己写了

用TreeMap行吗？ 帮我看看呗：

1. public static int longestPath(int[][] array){
   
2.         if(array == null || array.length == 0 || array[0].length == 0) return 0;
   
3.         TreeMap<Integer, Integer> tree = new TreeMap<Integer, Integer>();   // <current, next>
   
4.         for(int i = 0; i < array.length; i++){
   
5.             for(int j = 0; j < array[0].length; j++){
   
6.                 int cur = array[i][j];
   
7.                 if(hasNext(array, i, j)){
   
8.                     tree.put(cur, cur + 1); // pair current and next
   
9.                 }else{
   
10.                     tree.put(cur, cur); // no path
    
11.                 }
    
12.             }
    
13.         }
    
14.         int result = 0;
    
15.         int sum = 0;    // number of path, not dot
    
16.         while(!tree.isEmpty()){
    
17.             int curKey = tree.firstKey();
    
18.             int curVal = tree.get(curKey);
    
19.             if(curKey + 1 == curVal){   // has one path
    
20.                 sum++;
    
21.                 result = Math.max(result, sum);
    
22.                 tree.remove(curKey);
    
23.                 if(!tree.isEmpty()){    // may have further path
    
24.                     int nextKey = tree.firstKey();
    
25.                     if(curVal != nextKey){  // actually not
    
26.                         sum = 0;
    
27.                     }
    
28.                 }
    
29.             }else{
    
30.                 tree.remove(curKey);
    
31.             }
    
32.         }
    
33.         return result + 1;  // number of node == path + 1
    
34.     }
    
35. 
    
36.     private static boolean hasNext(int[][] array, int row, int col){
    
37.         int cur = array[row][col];
    
38.         if(row > 0 && array[row - 1][col] == cur + 1) return true;
    
39.         if(col > 0 && array[row][col - 1] == cur + 1) return true;
    
40.         if(row < array.length - 1 && array[row + 1][col] == cur + 1) return true;
    
41.         if(col < array[0].length - 1 && array[row][col + 1] == cur + 1) return true;
    
42.         return false;
    
43.     }

复制代码

时间复杂度是O(n^2)吧？

handsomecool 发表于 2015-8-17 14:22
过了好久，我也记得不是很清楚了。
用楼主发的例子吧，当时给我的好像也是这个例子：
7  8  6

感谢LZ 说明   没错我就是打算这么做   交流交流还是好的~~

有个思路供参考，递增递减分别dp一次取最大值。 dp[i][j] 表示到当前位置的最长路径。 路径只能往左下走。

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

1. public static int sequence(int[][] matrix) {
   
2.         int res  = 0;
   
3.         int[][] dp =new int[matrix.length][matrix.length];
   
4.         for (int i = 0; i < matrix.length; i++) {
   
5.             for (int j = 0; j < matrix.length; j++) {
   
6.                 if (dp[i][j] == 0) {
   
7.                     res = Math.max(res, dfs(matrix, dp, i, j));
   
8.                 }
   
9.             }
   
10.         }
    
11.         return res;
    
12.     }
    
13. 
    
14.     private static int dfs(int[][] a, int[][] store, int i, int j) {
    
15.         if (store[i][j] != 0) {
    
16.             return store[i][j];
    
17.         }
    
18.         int left = 0, right = 0, up = 0, down = 0;
    
19.         if (j + 1 < a[0].length && a[i][j+1] == a[i][j] + 1) {
    
20.             right = dfs(a, store, i, j+1);
    
21.         }
    
22.         if (j > 0 && a[i][j-1] == a[i][j] + 1) {
    
23.             left = dfs(a, store, i, j-1);
    
24.         }
    
25.         if (i + 1 < a.length && a[i+1][j] == a[i][j] + 1) {
    
26.             down = dfs(a, store, i+1, j);
    
27.         }
    
28.         if (i > 0 && a[i-1][j] == a[i][j] + 1) {
    
29.             up = dfs(a, store, i-1, j);
    
30.         }
    
31.         store[i][j] = Math.max(Math.max(up, down), Math.max(left, right)) + 1;
    
32.         return store[i][j];
    
33.     }

复制代码

大家看看这个代码可以么～

楼主。。。。这题最长长度是6吧，2,3,4,5,6,8

M_Jason 发表于 2015-9-18 11:35
楼主。。。。这题最长长度是6吧，2,3,4,5,6,8

要求连续吧，和lintcode那题不完全一样

坐看云起 发表于 2015-9-19 03:15
要求连续吧，和lintcode那题不完全一样

哦哦，没注意到那个连续的意思。恩，不过也好改，两个代码差不多。

top down dynamic programming = recursion + memorization