一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3083|回复: 6
收起左侧

liveramp oa 面经

[复制链接] |试试Instant~ |关注本帖
zwcelesta 发表于 2015-9-13 11:36:28 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@LiveRamp - 网上海投 - 在线笔试 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

算法题:青蛙过河。.鐣欏璁哄潧-涓浜-涓夊垎鍦
. more info on 1point3acres.com
输入一个Array, X,D,最早可以跳过X的时刻。. more info on 1point3acres.com

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

详细得跟这个帖子一样:http://www.meetqun.com/thread-10851-1-1.html

思路:* y, B$ w7 Z- u) W; ?1 I. G- _
一个hashtable 1个记录叶子的位置跟最早掉下时间。然后dp的思路。

int solution(vector<int> &A, int X, int D) {
    if(X<=D) return 0;
    vector<int> res(X+1,100000);
    map<int,int> leaf;
    res[0]=0; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    leaf[0]=0;
    leaf[X]=0;
    for(int i=0;i<A.size();++i){. more info on 1point3acres.com
        if(leaf.count(A)) continue;
        else leaf[A]=i;
    }
    for(int i=1;i<=X;++i){
        if(!leaf.count(i)) continue;
        if(i<=D){
            if(leaf.count(i)) res=leaf;
        }
        else{
            for(int k=D;k>0;--k){
                if(leaf<=res[i-k]) res=min(res,res[i-k]);
                else res=min(res,leaf);
            }
        }
    }
    return res[X];.鏈枃鍘熷垱鑷1point3acres璁哄潧
}

评分

1

查看全部评分

Laurinda93 发表于 2015-9-18 14:27:54 | 显示全部楼层
个人觉得这个解法应该是没问题的,并且要简单很多;也麻烦lz和大家一起看看思路就是在每次做D步更新,然后这这个范围内不断更新最大范围,并判断是否能在当前位置跳到;如果可以就返回当前位置,否则更新当前能到达的最大范围








  1. <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">.鏈枃鍘熷垱鑷1point3acres璁哄潧
  2. </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">
  3. </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">





  4. .1point3acres缃














  5. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷



  6. </p><p class="p1"><span class="Apple-tab-span">        </span>}</p>
复制代码
回复 支持 反对

使用道具 举报

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

不知道为什么上一条乱码
  1.         public static int frogJump(int[] arr, int X, int D) {. 鍥磋鎴戜滑@1point 3 acres
  2.                 if (arr == null || arr.length == 0 || X <= D)
  3.                         return 0;

  4.                 int left = 0;
  5.                 int right = D;
  6.                 int maxRange = 0;
  7. . 1point 3acres 璁哄潧
  8.                 while (left < right) {
  9.                         maxRange = Math.max(maxRange, arr[left] + D);. 1point3acres.com/bbs
  10.                         if (maxRange >= X)
  11.                                 return left;. more info on 1point3acres.com
  12.                         left++;
  13. . 鍥磋鎴戜滑@1point 3 acres
  14.                         right = maxRange;
  15.                 }
  16.                 return Integer.MAX_VALUE;
  17.         }
复制代码
回复 支持 反对

使用道具 举报

QawsQAER 发表于 2015-9-19 01:37:38 | 显示全部楼层
Laurinda93 发表于 2015-9-18 14:28.1point3acres缃
不知道为什么上一条乱码

是不是读错题了?
根据我的理解,你的代码似乎是把arr[k]当成在可以跳到位置为arr[k]的树叶上(类似leetcode Jump Game那道题?)。
但是根据题意,arr[k]是指在第k秒会多增一个位置为arr[k]的树叶。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
例如test case
arr[] = {5,1,0,0,2}, x = 5, d = 2,
根据你的解法,一上来这个青蛙就能达到目的地了,返回0.
然而根据题意,应该是在第0秒的时候,position 5 有一片树叶, 但是青蛙最多能跳的距离只为2, 所以不可能以上来就调到position 5 呀?
回复 支持 反对

使用道具 举报

Laurinda93 发表于 2015-9-19 07:08:35 | 显示全部楼层
QawsQAER 发表于 2015-9-19 01:37
是不是读错题了?
根据我的理解,你的代码似乎是把arr[k]当成在可以跳到位置为arr[k]的树叶上(类似leet ...

ok~~~谢谢啦 我觉得是我理解错了呢哭
再去研究一下嘿嘿~~~
回复 支持 反对

使用道具 举报

yangmyfly 发表于 2016-9-20 21:09:14 来自手机 | 显示全部楼层
但是贪心就可以吧,每次跳到能跳的最远的位置?
回复 支持 反对

使用道具 举报

yangmyfly 发表于 2016-9-20 21:11:47 来自手机 | 显示全部楼层
如果求所需最少踩的叶子才需要dp吧?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 11:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表