Snapchat电面

刚结束电面，之前承诺地里一位分享面经的同

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

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

cache.祝大家好运！

1. public class Solution {
   
2.     private int[] dx = {-1, 1, 0, 0};
   
3.     private int[] dy = {0, 0, -1, 1};
   
4.     public int longestIncreasingPath(int[][] matrix) {
   
5.         if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
   
6.             return 0;
   
7.         }
   
8.         int max = 0;
   
9.         int[][] dp = new int[matrix.length][matrix[0].length];
   
10.         for(int i = 0; i < matrix.length; i++) {
    
11.             for(int j = 0; j < matrix[0].length; j++) {
    
12.                 max = Math.max(max, dfs(matrix, i, j, dp));
    
13.             }
    
14.         }
    
15.         return max;
    
16.     }
    
17.     private int dfs(int[][] matrix, int i, int j, int[][] dp) {
    
18.         if(dp[i][j] != 0) {
    
19.             return dp[i][j];
    
20.         }
    
21.         for(int k = 0; k < 4; k++) {
    
22.             int x = i + dx[k];
    
23.             int y = j + dy[k];
    
24.             if(x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length && matrix[i][j] < matrix[x][y]) {
    
25.                 dp[i][j] = Math.max(dp[i][j], dfs(matrix, x, y, dp));
    
26.             }
    
27.         }
    
28.         return ++dp[i][j];
    
29.     }
    
30. }

复制代码

FTD2014 发表于 2016-11-8 10:27

1. if(x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length && matrix[i][j] < matrix[x][y]) {
   
2.                 dp[i][j] = Math.max(dp[i][j], dfs(matrix, x, y, dp));
   
3.             }

复制代码

感觉这里用不着max比一下，直接 dp[i][j] = dfs();

补充内容 (2016-11-14 08:59):
我的我的 要比一下的 比一下知道四个方向最长可以得到几~

wwtwxlwjh 发表于 2016-11-2 09:25
楼主能不能详细说说cache的做法。。看到好多面经说优化用cache。。。咋用啊。。。谢谢楼主！！

找到从某个点出发的最长路径之后，把它保存起来，这样下次访问到这个点的时候可以直接返回之前存好的结果而避免重复计算~

楼主能不能详细说说cache的做法。。看到好多面经说优化用cache。。。咋用啊。。。谢谢楼主！！

luofeidream 发表于 2016-11-2 09:33
找到从某个点出发的最长路径之后，把它保存起来，这样下次访问到这个点的时候可以直接返回之前存好的结果 ...

对的，我就是这样做的

luofeidream 发表于 2016-11-2 09:33
找到从某个点出发的最长路径之后，把它保存起来，这样下次访问到这个点的时候可以直接返回之前存好的结果 ...

哦哦 谢谢！

jwl2006 发表于 2016-11-2 09:41
对的，我就是这样做的

楼主，这题不优化的话，时间复杂度怎么达？ 4^k？

这题用topo sort可以不..?感觉也可以试试？

小A要当码农 发表于 2016-11-3 08:23
楼主，这题不优化的话，时间复杂度怎么达？ 4^k？

时间复杂度是N*M*3^(N*M),这个时间复杂度好难。。。。我也没答对

flashpacker 发表于 2016-11-3 08:37
这题用topo sort可以不..?感觉也可以试试？

拓普怎么存路径？

jwl2006 发表于 2016-11-3 11:08
时间复杂度是N*M*3^(N*M),这个时间复杂度好难。。。。我也没答对

嗯。 前半部分N＊M是算上打印路径的时间了么？ 楼主优化了以后应该就是O（NM）了吧