Uber暑假实习电面

ryanyan1010 发表于 2019-4-6 05:36
我也不是很确定 我没有理解你的峰值和谷值的意思 可以加我微信 我们详细讨论一下 349643111

就是极大值和极小值呀。。。

分享一个 Dp 的算法：

1. class Main{
   
2.         public static void main(String[] args) {
   
3.                 System.out.println(findLongest(new int[]{1, 5, 3, 13, 14, 17, 18, 4}));
   
4.         }
   
5. 
   
6.         public static int findLongest(int[] x){
   
7.                 // Going Up at this Point; like 2 in 1,2
   
8.                 int[] dpUp = new int[x.length];
   
9.                 // Goint down at this point;like 1 in 2,1
   
10.                 int[] dpDown = new int[x.length];
    
11. 
    
12.                 //Example: 1 5 3 13 14 17 18 4
    
13.                 //dpUp:    1 2 2 4 4 4 4 4
    
14.                 //dpDown:  1 1 3 1 1 1 1 5
    
15.                 //Max --> max Number between dpUp and dpDown
    
16.                 dpUp[0] = 1;   
    
17.                 dpDown[0] = 1;
    
18.                 int max = 0;
    
19.                 for(int i = 1; i < x.length; i++){
    
20.                         dpUp[i] = 1;
    
21.                         dpDown[i] = 1;
    
22. 
    
23.                         for(int j = i - 1; j >=0 ; j--){
    
24.                                 if(x[i] > x[j]){
    
25.                                         dpUp[i] = Math.max(dpDown[j] + 1, dpUp[i] );
    
26.                                 }
    
27.                                 if(x[i] < x[j]){
    
28.                                         dpDown[i] = Math.max(dpUp[j] + 1, dpDown[i]);
    
29.                                 }
    
30.                         }
    
31.                         max = max > Math.max(dpUp[i],dpDown[i]) ? max : Math.max(dpUp[i],dpDown[i]);
    
32.                 }
    
33.                 printFunction(dpUp);
    
34.                 printFunction(dpDown);
    
35.                 return max;
    
36.         }
    
37. 
    
38.         private static void printFunction(int[] x){
    
39.                 for(int i = 0; i < x.length; i++){
    
40.                         System.out.print(x[i]);
    
41.                         System.out.print(" ");
    
42.                 }
    
43.                 System.out.println();
    
44.         }
    
45. }

复制代码

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

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

ryanyan1010 发表于 2019-4-9 13:30
你好，我觉得你可能有点误解了我说的题目意思，就是按照这两个pattern走，怎么会出现1，2，2，4，4，4，4 ...

那两个不是结果，只是用的两个Dp 的里面放的值.....
你要不跑一下吧....

LIYUJIE 发表于 2019-4-9 13:50
那两个不是结果，只是用的两个Dp 的里面放的值.....
你要不跑一下吧....

是不是只要一维dp就可以了吧

jy_121 发表于 2019-4-10 13:01
是不是只要一维dp就可以了吧

一维dp 是指的一个Array 还是 维度是一维的? 我用了两个一维的Array

LIYUJIE 发表于 2019-4-10 14:43
一维dp 是指的一个Array 还是 维度是一维的? 我用了两个一维的Array

没有表达清楚，一维dp的话一层for循环就够了吧

楼主请问下是本科还是研究生呢。。。想问问学校的档次

uber这种一定要找内推吗，还是自己投也一样的

LIYUJIE 发表于 2019-4-10 14:43
一维dp 是指的一个Array 还是 维度是一维的? 我用了两个一维的Array

我不知道哇。要不你写写看？

zzh372024750 发表于 2019/04/10 23:07:13
楼主请问下是本科还是研究生呢。。。想问问学校的档次

uber这种一定要找内推吗，还是自己投也一样的

我就是自己海投的诶 学校也是一般般五十多名左右的 研究生