Tiktok视频一面

谢谢楼主分享，不过这道题的震荡数组是不是应该是{3, 4, 2, 3, 1, 2, 1, 6, 5}, 符合条件的最大长度是9才对？

lightstarbury 发表于 2020-7-21 04:52
谢谢楼主分享，不过这道题的震荡数组是不是应该是{3, 4, 2, 3, 1, 2, 1, 6, 5}, 符合条件的最大长度是9才对 ...

是的 我只是举例要符合一大一小哈 这题就是要求尽量长的长度

匿名者 发表于 2020-7-21 21:29
是的 我只是举例要符合一大一小哈 这题就是要求尽量长的长度

谢谢楼主哈，已加米～

用dfs是对的，用dfs+memorization反而会漏掉其他可能。

1.    
   
2. private static int longestWiggleSeq(int[][] matrix){
   
3.         if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
   
4.             return 0;
   
5.         }
   
6. 
   
7.         int m = matrix.length, n = matrix[0].length, res = 0;
   
8.         boolean[][] visited = new boolean[m][n];
   
9.         for(int i = 0; i < m; i++){
   
10.             for(int j = 0; j < n; j++){
    
11.                 res = Math.max(res, helper(matrix, i, j, true, visited));
    
12.             }
    
13.         }
    
14. 
    
15.         return res;
    
16.     }
    
17. 
    
18.     private static int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    
19.     private static int helper(int[][] matrix, int i, int j, boolean smaller, boolean[][] visited){
    
20.         // System.out.println(i+"-"+j+"="+matrix[i][j]);
    
21.         visited[i][j] = true;
    
22.         int ans = 1;
    
23.         for(int[] dir : dirs){
    
24.             int nx = i + dir[0];
    
25.             int ny = j + dir[1];
    
26.             if(nx >= 0 && nx < matrix.length && ny >= 0
    
27.                && ny < matrix[0].length && !visited[nx][ny]){
    
28.                 if(smaller && matrix[i][j] < matrix[nx][ny]){
    
29.                     ans = Math.max(ans, 1 + helper(matrix, nx, ny, !smaller, visited));
    
30.                 }
    
31.                 if(!smaller && matrix[i][j] > matrix[nx][ny]){
    
32.                     ans = Math.max(ans, 1 + helper(matrix, nx, ny, !smaller, visited));
    
33.                 }
    
34.             }
    
35.         }
    
36. 
    
37.         visited[i][j] = false;
    
38.         return ans;
    
39.     }
    

复制代码

pennyhwung 发表于 2020-7-29 02:42
用dfs是对的，用dfs+memorization反而会漏掉其他可能。

[mw_shl_code=java,true]   

Code写得很好，赞

hjy 发表于 2020-7-15 05:45
感觉是不是也可以用dfs with memorization 做呢？ 用一个m x n x 2的数组记录matrix[j]作为序列开头且分别 ...

感觉可以 你看下这个: https://leetcode.com/problems/lo ... g-path-in-a-matrix/

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

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

第一感觉是topo 不知道对不对

谢谢楼主的分享。