CMU MSIT-SE 2015的青蛙题 FrogPond，求解

albusshin 发表于 2015-7-2 09:31
但是好像没有必要往后跳吧

也对啊，如果你已经能到更远的地方，那么往回跳肯定不如从当前位置直接往前跳。

stellari 发表于 2015-7-1 21:37
这题其实和Leetcode上的"Maximum Gap"很像。比如考虑X = 8, D = 3的情况，一开始pond是这样的：

1 0 0 0 ...

你好！你的方法很好， 是不是可以简化下

我们是不是可以把你所说的range 换成两个 数组， 一个存最大值，一个存最小值。 每次叶子落下的时候， 我们直接更新即可。 这样代码量少了很多。

欢迎指正！

今天做LiveRamp就是这道题。。。我用的并查级，但是感觉不是O(n)啊

georgmaster 发表于 2015-7-1 23:37
请问用union find可以吗？
public int solution(){
                for(int i = 0; i < N; i++){

如果再设置一个标志数组的话，是不是就不满足空间复杂度O(n)的要求了？

昨天和同学一起做LiveRamp的时候碰到这道题了。开始也想不到O(n)的做法，后来查了一下，发现就是先用一个array存每一个leaf落下的时间，然后就是leetcode的sliding window maximum原题。不过把maximum换成minimum，然后答案就是minimum的maximum。

满城尽带黄金甲 发表于 2015-7-1 22:32
用你的例子好了， boolean[] bridge = new boolean[X];
第0秒，叶子降落在位置1， 那么bridge[0]~bridge ...

每一秒，都要将A[i]-D~A[i]+D置为true，这个时间复杂度应该是O(N*2D)吗？

zhuli19901106 发表于 2015-7-1 22:41
等你的代码咯，咱们毕竟不是在辩论。

为什么贪心不行

P=青蛙能够到达的最远距离

初始化
P=D

循环
For i=1~N
  if A[i]<=P+D&&A[i]>P//青蛙能够到达A[i]且A[i]比青蛙现在的位置更远
    P=A[i]
  if P>=X
    return i

感谢@stellari 的思路，这是我写出来的类似的代码， 大家可以批评指正

1. import java.util.Arrays;
   
2. 
   
3. class Solution {
   
4.   public int solution(int[] A, int N, int X, int D) {
   
5.     if (X <= D) {
   
6.       return 0;
   
7.     }
   
8.     int N_buck = (int)Math.ceil((double)X / D);
   
9.     int[] minBuck = new int[N_buck];
   
10.     int[] maxBuck = new int[N_buck];
    
11.     // a bucket is connected if this bucket is not empty and if there is previous bucket, the previous bucket is already connected
    
12.     boolean[] connected = new boolean[N_buck];
    
13.     Arrays.fill(minBuck, Integer.MAX_VALUE);
    
14.     Arrays.fill(maxBuck, Integer.MIN_VALUE);
    
15.     minBuck[0] = 0;
    
16.     maxBuck[0] = 0;
    
17.     minBuck[N_buck - 1] = X;
    
18.     maxBuck[N_buck - 1] = X;
    
19.     int count = 1;
    
20.     connected[0] = true;
    
21.     int i= 0;
    
22.     while (count != N_buck && i < N) {
    
23.       int idx = A[i] / D;
    
24.       minBuck[idx] = Math.min(minBuck[idx], A[i]);
    
25.       maxBuck[idx] = Math.max(maxBuck[idx], A[i]);
    
26.       // check before
    
27.       if (!connected[idx] && idx - 1 >= 0) {
    
28.         // if not empty
    
29.         if (minBuck[idx - 1] != Integer.MAX_VALUE || maxBuck[idx - 1] != Integer.MIN_VALUE) {
    
30.           if (minBuck[idx] - maxBuck[idx - 1] <= D) {
    
31.             connected[idx] = true;
    
32.             count++;
    
33.           }
    
34.         }
    
35.       }
    
36.       // check after
    
37.       if (idx + 1 < N_buck && !connected[idx + 1]) {
    
38.         // if not empty
    
39.         if (minBuck[idx + 1] != Integer.MAX_VALUE || maxBuck[idx + 1] != Integer.MIN_VALUE) {
    
40.           if (minBuck[idx + 1] - maxBuck[idx] <= D) {
    
41.             connected[idx + 1] = true;
    
42.             count++;
    
43.           }
    
44.         }
    
45.       }
    
46.       i++;
    
47.     }
    
48.     if (count == N_buck) {
    
49.       return i - 1;
    
50.     }
    
51.     return -1;
    
52.   }
    
53. }

复制代码