Snapchat电面

jwl2006 发表于 2016-11-4 06:33
问的是长度，你的方案可行

有了每个点开始的路径长度 可以很容易用 O(mn) 的复杂度重建路径吧

楼主拿到onsite了吗

有点没看懂题目 是要返回从高到底排序的所有路径长度？

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):
我的我的 要比一下的 比一下知道四个方向最长可以得到几~