狗家高频面经求解

看到这题很多次： 从第一行任意一个位置到最后一行

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

讲解dp的思路..

niananiananian 发表于 2021-6-16 21:19
感觉是maintain 3个bp数组，分别是从上/左/右进入本格的最大。

补充内容 (2021-06-16 23:21 +8:00):

这上面有人说了，感觉就应该是这样做，我改成了Java代码三个数组应该是分别代表从最上面entry行到当前位置的最长距离，对于每一行，往左右方向更新数组，然后往下走应该选择左右2个方向最大的

1. 
   
2. public int maxDistance(String[] grid) {
   
3.         int m = grid.length;
   
4.         int n = grid[0].length();
   
5.         int[] dp = new int[n];
   
6.         int[] dpLeft = new int[n];
   
7.         int[] dpRight = new int[n];
   
8. 
   
9.         for (int i = 0; i < m; i++) {
   
10.             //calculate left
    
11.             dpLeft[0] = (grid[i].charAt(0) == '#') ? Integer.MIN_VALUE : dp[0] + 1;
    
12.             for (int j = 1; j < n; j++) {
    
13.                 dpLeft[j] = (grid[i].charAt(j) == '#') ? Integer.MIN_VALUE : Math.max(dp[j] + 1, dpLeft[j - 1] + 1);
    
14.             }
    
15.             //calculate right
    
16.             dpRight[n - 1] = (grid[i].charAt(n - 1) == '#') ? Integer.MIN_VALUE : dp[n - 1] + 1;
    
17.             for (int j = n - 2; j >= 0; j--) {
    
18.                 dpRight[j] = (grid[i].charAt(j) == '#') ? Integer.MIN_VALUE : Math.max(dp[j] + 1, dpRight[j + 1] + 1);
    
19.             }
    
20.             //go down
    
21.             for (int j = 0; j < n; j++) {
    
22.                 dp[j] = Math.max(dpLeft[j], dpRight[j]);
    
23.             }
    
24.         }
    
25. 
    
26.         int ans = Integer.MIN_VALUE;
    
27.         for (int j = 0; j < n; j++) {
    
28.             ans = Math.max(ans, dp[j]);
    
29.         }
    
30.         return ans;
    
31.     }
    
32. 
    
33. String[] maze =
    
34.                 {"#.#..#",
    
35.                 "#.#..#",
    
36.                 "#.##.#",
    
37.                 "#..#.#",
    
38.                 "#..#.#",
    
39.                 "#..#.#"};
    
40.         System.out.println(test.maxDistance(maze));
    

复制代码

1. int n = ch.length;
   
2.             int m = ch[0].length;
   
3.             int[][] dp = new int[n][m];
   
4.             for (int i = 0; i < n; i++) {
   
5.                 for (int j = 0; j < ch[i].length; j++) {
   
6.                     if (ch[i][j] == '.') {
   
7.                         int k = j + 1;
   
8.                         int num = 1;
   
9.                         while (k < m && ch[i][k] == '.') {
   
10.                             k++;
    
11.                             num++;
    
12.                         }
    
13.                         while (j < k) {
    
14.                             dp[i][j] = num;
    
15.                             j++;
    
16.                         }
    
17.                     }
    
18.                 }
    
19.             }
    
20.             for (int i = 1; i < n; i++) {
    
21.                 for (int j = 0; j < m; j++) {
    
22.                     if (ch[i][j] == '.') {
    
23.                         if (ch[i - 1][j] == '.') {
    
24.                             dp[i][j] = dp[i - 1][j] + dp[i][j];
    
25.                         } else {
    
26.                             if (j >= 1)
    
27.                                 dp[i][j] = Math.max(dp[i][j - 1], 0);
    
28.                             else
    
29.                                 dp[i][j] = 0;
    
30.                         }
    
31.                     }
    
32.                 }
    
33.             }

复制代码

[i][i][i][i][i][i][i][i][i]
我这样试了一下，大家看下对吗。
最后在dp最后一行筛选最大返回[/i][/i][/i][/i][/i][/i][/i][/i][/i]

关注一下～

感觉是maintain 3个bp数组，分别是从上/左/右进入本格的最大。

补充内容 (2021-06-16 23:21 +8:00):
想了一下，2个就可以了，一个是从左到右的逐行扫描的最大值，每个cell比较上和左的值。另一个是从右到左逐行扫描的最大值，每个cell比较上和右的值

感谢！！！！！

狗 电面就是遇到的这道题 相见恨晚

dijkstra可以不可以实现这个算法呢？每个点的长度作为weight？

https://leetcode.com/playground/m6qdqp94

Falldawn 发表于 2021-6-17 06:13
这上面有人说了，感觉就应该是这样做，我改成了Java代码三个数组应该是分别代表从最上面entry行到当前位 ...

按照我的理解可以节省空间而不需要建立一个(m, n)的数组, 因为每次只需要关注连着的两行, 可以节省空间到O(n)