Tiktok视频一面

6月下旬申请的tiktok，昨天刚面完, 今天早上就收到下一轮邮件啦～

第一轮视频面试，是国人小哥，但是英文面的。

input是一个int[][]二维数组，从任意点

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

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

后再backtrack删除最后一个数，期间判断list是否符合输出震荡数组的要求，记录length

不太明白为什么最大长度不是9呢？一条龙遍历整个矩阵也满足条件呀

用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.     }
    

复制代码

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

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

请问楼主是面什么组呢？前段还是后端呀

没看懂这个序列的要求？

queque 发表于 2020-7-14 23:51
请问楼主是面什么组呢？前段还是后端呀

后端～ Ads platform

xin2v 发表于 2020-7-15 00:48
没看懂这个序列的要求？

就是第一个数小于第二个数、第二个数大于第三个数、第三个数小于第四个数……

感觉是不是也可以用dfs with memorization 做呢？ 用一个m x n x 2的数组记录matrix[i][j]作为序列开头且分别为波峰和波谷的最大长度

楼主投的是校招还是社招呀？

一定要从右下角开始？长度一定要是5？还是有其他要求？多谢

erichuan2020 发表于 2020-7-15 07:01
一定要从右下角开始？长度一定要是5？还是有其他要求？多谢

不是的 任意点都可以 长度也是要找最长的就行