liveramp oa 面经

Liveramp codlity OA
一道算法题，一个问为什么感兴趣我们公司

算法题：青蛙过河。

输入一个Array, X，D，最早可以跳过X的时刻。

1 有只青蛙要过河，起始位置position 0，一路跳到 X，每次跳得距离 在1 ~ D，一秒可以跳很多次的样子只要有叶子可以停。。。
2 每秒都会落下一片叶子，青蛙可以停在上面（叶子不会消失）
3 给了一个Array, Array[k] 表示，k秒落下叶子的位置

详细得跟这个帖子一样：

思

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

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

  if(leaf[i]<=res[i-k]) res[i]=min(res[i],res[i-k]);
                else res[i]=min(res[i],leaf[i]);
            }
        }
    }
    return res[X];
}

个人觉得这个解法应该是没问题的，并且要简单很多；也麻烦lz和大家一起看看思路就是在每次做D步更新，然后这这个范围内不断更新最大范围，并判断是否能在当前位置跳到；如果可以就返回当前位置，否则更新当前能到达的最大范围

1. 
   
2. 
   
3. 
   
4. 
   
5. 
   
6. 
   
7. 
   
8. 
   
9. <p class="p1"><span class="Apple-tab-span">        </span><span class="s1">public</span> <span class="s1">static</span> <span class="s1">int</span> frogJump(<span class="s1">int</span>[] <span class="s2">arr</span>, <span class="s1">int</span> <span class="s2">X</span>, <span class="s1">int</span> <span class="s2">D</span>) {</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">if</span> (<span class="s2">arr</span> == <span class="s1">null</span> || <span class="s2">arr</span>.<span class="s3">length</span> == 0 || <span class="s2">X</span> <= <span class="s2">D</span>)</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">return</span> 0;</p><p class="p2">
   
10. </p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">int</span> <span class="s2">left</span> = 0;</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">int</span> <span class="s2">right</span> = <span class="s2">D</span>;</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">int</span> <span class="s2">maxRange</span> = 0;</p><p class="p2">
    
11. </p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">while</span> (<span class="s2">left</span> < <span class="s2">right</span>) {</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s2">maxRange</span> = Math.max(<span class="s2">maxRange</span>, <span class="s2">arr</span>[<span class="s2">left</span>] + <span class="s2">D</span>);</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">if</span> (<span class="s2">maxRange</span> >= <span class="s2">X</span>)</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">return</span> <span class="s2">left</span>;</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s2">left</span>++;</p><p class="p3"><span class="s4"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span></span>right<span class="s4"> = </span>maxRange<span class="s4">;</span></p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span>}</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">return</span> Integer.<span class="s3">MAX_VALUE</span>;</p><p class="p1">
    
12. 
    
13. 
    
14. 
    
15. 
    
16. 
    
17. 
    
18. 
    
19. 
    
20. 
    
21. 
    
22. 
    
23. 
    
24. 
    
25. 
    
26. 
    
27. 
    
28. 
    
29. 
    
30. 
    
31. 
    
32. 
    
33. 
    
34. 
    
35. 
    
36. </p><p class="p1"><span class="Apple-tab-span">        </span>}</p>

复制代码

Laurinda93 发表于 2015-9-18 14:27
个人觉得这个解法应该是没问题的，并且要简单很多；也麻烦lz和大家一起看看思路就是在每次做D步更新，然后 ...

不知道为什么上一条乱码

1.         public static int frogJump(int[] arr, int X, int D) {
   
2.                 if (arr == null || arr.length == 0 || X <= D)
   
3.                         return 0;
   
4. 
   
5.                 int left = 0;
   
6.                 int right = D;
   
7.                 int maxRange = 0;
   
8. 
   
9.                 while (left < right) {
   
10.                         maxRange = Math.max(maxRange, arr[left] + D);
    
11.                         if (maxRange >= X)
    
12.                                 return left;
    
13.                         left++;
    
14. 
    
15.                         right = maxRange;
    
16.                 }
    
17.                 return Integer.MAX_VALUE;
    
18.         }

复制代码

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

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

QawsQAER 发表于 2015-9-19 01:37
是不是读错题了？
根据我的理解，你的代码似乎是把arr[k]当成在可以跳到位置为arr[k]的树叶上（类似leet ...

ok~~~谢谢啦 我觉得是我理解错了呢哭
再去研究一下嘿嘿~~~

但是贪心就可以吧，每次跳到能跳的最远的位置？

如果求所需最少踩的叶子才需要dp吧？

Laurinda93 发表于 2015-9-19 07:08
ok~~~谢谢啦 我觉得是我理解错了呢哭
再去研究一下嘿嘿~~~

我觉得算每秒最多能到哪可以吧，不懂为何偏要用hashamp呢，明明一个extra O(1)不可以解决吗？