讨论一下liveramp的过河问题

liveramp的OA里面有道过河问题，这个过河问题还有两个版本，一个是青蛙，一个是猴子。
题目看连接



首先说一下两个题目不同点就是A[k]的表示，
青蛙的是 A[k] represent the position where a leaf will fall at time k.
猴子的是 A[k] represent a time when the stone at positio

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

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

2]!=-1, ... , B[i-D] !=-1
      =  -1 if A[i]= -1 or B[i-1] until B[i-D] = -1


代码如下：

1.         public static int solution(int[] A, int D) {
   
2.       if (A == null || A.length == 0)
   
3.            return -1;
   
4.                 if (D > A.length)
   
5.                         return 0;
   
6.                 int B[] = new int[A.length + 1];
   
7.                 for (int i = 0; i < D; i++) {
   
8.                         B[i] = A[i];
   
9.                 }
   
10.                 for (int i = D; i < A.length; i++) {
    
11.                         if (A[i] == -1) {
    
12.                                 B[i] = -1;
    
13.                         } else {
    
14.                                 int temp = Integer.MAX_VALUE;
    
15.                                 int count = 0;
    
16.                                 for (int j = 1; j <= D; j++) {
    
17.                                         if (B[i - j] == -1) {
    
18.                                                 count++;
    
19.                                                 continue;
    
20.                                         }
    
21.                                         temp = Math.min(temp, B[i - j]);
    
22.                                 }
    
23.                                 B[i] = count == D ? -1 : Math.max(temp, A[i]);
    
24.                         }
    
25.                 }
    
26.                 int res = Integer.MAX_VALUE;
    
27.                 int count = 0;
    
28.                 for (int j = 1; j <= D; j++) {
    
29.                         if (B[A.length - j] == -1) {
    
30.                                 count++;
    
31.                                 continue;
    
32.                         }
    
33.                         res = Math.min(res, B[A.length - j]);
    
34. }
    
35.                 return res = count == D ? -1 : res;
    
36.         }

复制代码

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

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

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

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

gaohannk 发表于 2016-5-30 07:33
time O(D*N)

补充内容 (2016-5-30 07:35):

被什么老师丢字符呢？ 算了大家自己体会一下吧。

能问一下楼主为什么这行是取B和A的max嘛？谢谢！B = max(min(B[i-1],B[i-2], ... , B[i-D]),A)

garygao1993 发表于 2016-9-20 16:00
不知道我这个解法有没有问题？

补充内容 (2016-9-20 16:07):

该代码似乎并没有工作。

garygao1993 发表于 2016-9-29 05:59
楼上是烙印？...惊了...『似乎并没有工作』... seems not working?

输入为A=[-1], D=1，会报错了，楼考虑了D=N？