一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 5023|回复: 13
收起左侧

讨论一下liveramp的过河问题

[复制链接] |试试Instant~ |关注本帖
gaohannk 发表于 2016-5-30 07:33:04 | 显示全部楼层 |阅读模式

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

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

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

x
liveramp的OA里面有道过河问题,这个过河问题还有两个版本,一个是青蛙,一个是猴子。
题目看连接
http://www.1point3acres.com/bbs/ ... ;highlight=liveramp
http://www.1point3acres.com/bbs/ ... ;highlight=liveramp

首先说一下两个题目不同点就是A[k]的表示,
青蛙的是 A[k] represent the position where a leaf will fall at time k.
猴子的是 A[k] represent a time when the stone at position k will be out of water.
基本上就是反的,猴子的可以 A[k]=-1 表示 k 不会有stone, 对应的青蛙就应该是数组A里面没有值为K的元素
另外 根据猴子的那个图示,初始position是-1对岸是A.length, 而青蛙的似乎初始是在position 0 对岸是 X,
后面的代码是根据猴子的写的。
我想到了两种解法:第一种native 每一秒钟查看stone 和leaf 是不是可以保证过河,至少 需要A.length/D 多个stone, 也就是A.length.D 秒。 time O(max(A)*N)
第二种DP, B represent 跳到position i 最少需要的时间。
B = max(min(B[i-1],B[i-2], ... , B[i-D]),A)  if B[i-1]!=-1or B[i-2]!=-1, ... , B[i-D] !=-1
      =  -1 if A= -1 or B[i-1] until B[i-D] = -1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴


代码如下:
  1.         public static int solution(int[] A, int D) {. visit 1point3acres.com for more.
  2.       if (A == null || A.length == 0)
  3.            return -1;
  4.                 if (D > A.length)
  5.                         return 0;. visit 1point3acres.com for more.
  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) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  12.                                 B[i] = -1;
  13.                         } else {
  14.                                 int temp = Integer.MAX_VALUE;
  15.                                 int count = 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  16.                                 for (int j = 1; j <= D; j++) {. From 1point 3acres bbs
  17.                                         if (B[i - j] == -1) {
  18.                                                 count++;
  19.                                                 continue;
  20.                                         }
  21.                                         temp = Math.min(temp, B[i - j]);
  22.                                 }.1point3acres缃
  23.                                 B[i] = count == D ? -1 : Math.max(temp, A[i]);
  24.                         }. more info on 1point3acres.com
  25.                 }
  26.                 int res = Integer.MAX_VALUE;. more info on 1point3acres.com
  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.         }
复制代码

评分

3

查看全部评分

本帖被以下淘专辑推荐:

garygao1993 发表于 2016-9-29 05:59:46 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
楼上是烙印?...惊了...『似乎并没有工作』... seems not working?
回复 支持 1 反对 0

使用道具 举报

 楼主| gaohannk 发表于 2016-5-30 07:33:45 | 显示全部楼层
关注一亩三分地微博:
Warald
time O(D*N)
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2016-5-30 07:35):
B = max(min(B[i-1],B[i-2], ... , B[i-D]),A)  if B[i-1]!=-1 or B[i-2]!=-1, ... ,or B[i-D] !=-1
      =  -1 if A= -1 or B[i-1] until B[i-D] = -1
回复 支持 反对

使用道具 举报

 楼主| gaohannk 发表于 2016-5-30 07:35:38 | 显示全部楼层
gaohannk 发表于 2016-5-30 07:33
time O(D*N)

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

被什么老师丢字符呢? 算了大家自己体会一下吧。
回复 支持 反对

使用道具 举报

whitney94 发表于 2016-9-14 06:24:19 | 显示全部楼层
能问一下楼主为什么这行是取B和A的max嘛?谢谢!B = max(min(B[i-1],B[i-2], ... , B[i-D]),A)
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

garygao1993 发表于 2016-9-20 16:00:22 | 显示全部楼层
  1. int crossRiver(vector<int>& A, int D) {. visit 1point3acres.com for more.
  2.         int N = (int)A.size();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3.         if (D > N) return 0;. 1point 3acres 璁哄潧
  4.         if (D <= 0) return -1;
  5.         deque<int> B; // 维护一个大小为 D 的双向队列

  6.         // 在0时刻我们能到达任意在0到 D - 1 的石头-google 1point3acres
  7.         for (int i = 0; i < D; ++i) {
  8.                 // 位置 i 没有石头
  9.                 if (A[i] == -1) continue;

  10.                 // 如果到达靠前的石头要花更多或者相等的时间,那就不会跳到那个石头,所以把它从队列中除去
  11.                 while (!B.empty() && A[B.back()] >= A[i])
  12.                         B.pop_back();

  13.                 // 将石头的位置放入队列.鐣欏璁哄潧-涓浜-涓夊垎鍦
  14.                 B.push_back(i);
  15.         }
  16.         for (int i = D; i < N; ++i) {
  17.                 // 如果队列中第一个石头已经在跳跃范围 D 以外了,那我们就不能从那个石头跳到位置 i 了,所以除去
  18.                 if (!B.empty() && i - B.front() == D + 1)
  19.                         B.pop_front();
  20. . more info on 1point3acres.com
  21.                 // 如果队列中没有石头,意味着就没有能够到达位置 i 的石头,提前结束
  22.                 if (B.empty()) return -1;
  23. . visit 1point3acres.com for more.
  24.                 // 位置 i 没有石头
  25.                 if (A[i] == -1) continue;

  26.                 // 在保证能有石头跳到位置 i 的情况下,把位置靠前但耗时没有更少的石头从队列除去
  27.                 while (B.size() > 1 && A[B.back()] >= A[i]).鐣欏璁哄潧-涓浜-涓夊垎鍦
  28.                         B.pop_back();

  29.                 // 把 A[i] 改为从起到到达 A[i] 的最快时间
  30.                 A[i] = max(A[B.front()], A[i]);.1point3acres缃
  31. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  32.                 // 如果到达队列队首的石头耗时与到达石头 i 的耗时相同,则我们不会在队首石头停留,直接往 i 跳,所以把队首除去
  33.                 if (A[B.front()] == A[i])
    . from: 1point3acres.com/bbs
  34.                         B.pop_front();

  35.                 // 将石头的位置放入队列
  36.                 B.push_back(i);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  37.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  38.         // 如果队首石头无法直接到达终点,那就从队列除去
  39.         if (N - B.front() == D + 1) B.pop_front();

  40.         // 队列有石头则可到达终点,最快时间为此时队列队首的耗时. from: 1point3acres.com/bbs
  41.         return B.empty() ? -1 : A[B.front()];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  42. }
复制代码


不知道我这个解法有没有问题?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2016-9-20 16:07):
这个想法是来自这题 https://leetcode.com/problems/sliding-window-maximum/
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2016-10-2 15:54):
应该在最后 if (N - B.front() == D + 1) B.pop_front(); 的条件加一个 !B.empty(),不确定还有没有别的 bug,求指导
回复 支持 反对

使用道具 举报

startuptech11 发表于 2016-9-29 04:44:55 | 显示全部楼层
garygao1993 发表于 2016-9-20 16:00
不知道我这个解法有没有问题?

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

该代码似乎并没有工作。
回复 支持 反对

使用道具 举报

仲夏夜 发表于 2016-10-2 14:46:21 | 显示全部楼层
garygao1993 发表于 2016-9-29 05:59
楼上是烙印?...惊了...『似乎并没有工作』... seems not working?

输入为A=[-1], D=1,会报错了,楼考虑了D=N?
回复 支持 反对

使用道具 举报

garygao1993 发表于 2016-10-2 15:52:47 | 显示全部楼层
仲夏夜 发表于 2016-10-2 14:46
输入为A=[-1], D=1,会报错了,楼考虑了D=N?

有道理,应该在最后 if (N - B.front() == D + 1) B.pop_front(); 的条件加一个 !B.empty()
回复 支持 反对

使用道具 举报

Mimilu 发表于 2016-10-4 12:16:05 | 显示全部楼层
garygao1993 发表于 2016-9-29 05:59
楼上是烙印?...惊了...『似乎并没有工作』... seems not working?

呼叫管理员
回复 支持 反对

使用道具 举报

SuperMe 发表于 2016-10-7 06:18:04 | 显示全部楼层
garygao1993 发表于 2016-9-29 05:59
楼上是烙印?...惊了...『似乎并没有工作』... seems not working?

烙印是什么意思??
回复 支持 反对

使用道具 举报

freeaccount 发表于 2016-11-15 06:24:11 | 显示全部楼层
SuperMe 发表于 2016-10-6 17:18
烙印是什么意思??

来挖坟。。。老印,就是印度人。据说是本论坛太有名所以会有印度人用google translate来访问。。。
回复 支持 反对

使用道具 举报

zhaoty0906 发表于 2016-11-29 09:50:46 | 显示全部楼层
请问下楼主,这道题可不可以用priorityqueue储存数组A里面的元素,然后dp储存当前时间所能到达的最远距离,每次只要看priorityqueue里面的最小值是不是等于当前时间,等于就说明对应的位置可以时候,更新最远距离,最远距离超过岸边值,就说明能够到达

补充内容 (2016-11-29 10:07):
发现问题了
回复 支持 反对

使用道具 举报

miracle2138 发表于 2017-2-19 00:50:06 | 显示全部楼层
public int monkeyCross(int D, int[] A, int N){
                if(-1 + D >= N) return 0;
                if(A == null || A.length == 0) return -1;. visit 1point3acres.com for more.
                int size = 0;
                for(int i : A){
                        size = Math.max(size, i);
                }
                int[] time = new int[size + 1];
                Arrays.fill(time, -1);
. visit 1point3acres.com for more.                for(int i = 0; i < A.length; i++){. 鍥磋鎴戜滑@1point 3 acres
                        if(A[i] == -1) continue;
                        time[A[i]] = i;
                }
                Set<Integer> reach = new HashSet<>();
                reach.add(-1);
                Set<Integer> unreach = new HashSet<>();
                int max_sofar = -1;
                for(int i = 0; i < time.length; i++){
                        if(time[i] != -1 && !reach.contains(time[i]) && !unreach.contains(time[i])){
                                if(max_sofar + D >= time[i]){
                                        reach.add(time[i]);
                                        max_sofar = time[i];
                                        for(int j = 1; j <= D; j++){
                                                int pos = j + time[i];
                                                if(unreach.contains(pos)){
                                                        max_sofar = Math.max(max_sofar, pos);. 1point3acres.com/bbs
                                                        unreach.remove(pos);.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                                        reach.add(pos);. From 1point 3acres bbs
                                                }
                                        }
                                        if(max_sofar + D >= N). Waral 鍗氬鏈夋洿澶氭枃绔,
                                                return i;
                                }else{
                                        unreach.add(time[i]);. From 1point 3acres bbs
                                }
                        }
                }
                return -1;
        }

我的解法,猴子过河。空间应该是O(N+MAX(A))时间是O(MAX(A)*D)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-30 11:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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