一亩三分地论坛

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

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

讨论一下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.鏈枃鍘熷垱鑷1point3acres璁哄潧
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) {
  2.       if (A == null || A.length == 0)
  3.            return -1;
    .1point3acres缃
  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.                                 }. 1point 3acres 璁哄潧
  23.                                 B[i] = count == D ? -1 : Math.max(temp, A[i]);
  24.                         }. from: 1point3acres.com/bbs
  25.                 }
  26.                 int res = Integer.MAX_VALUE;
    . From 1point 3acres bbs
  27.                 int count = 0;
  28.                 for (int j = 1; j <= D; j++) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  29.                         if (B[A.length - j] == -1) {
  30.                                 count++;
  31.                                 continue;.1point3acres缃
  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 | 显示全部楼层
楼上是烙印?...惊了...『似乎并没有工作』... seems not working?
回复 支持 1 反对 0

使用道具 举报

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

补充内容 (2016-5-30 07:35):
. From 1point 3acres bbsB = 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)
回复 支持 反对

使用道具 举报

garygao1993 发表于 2016-9-20 16:00:22 | 显示全部楼层
  1. int crossRiver(vector<int>& A, int D) {
  2.         int N = (int)A.size();. from: 1point3acres.com/bbs
  3.         if (D > N) return 0;
  4.         if (D <= 0) return -1; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.         deque<int> B; // 维护一个大小为 D 的双向队列

  6.         // 在0时刻我们能到达任意在0到 D - 1 的石头
  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. . From 1point 3acres bbs
  21.                 // 如果队列中没有石头,意味着就没有能够到达位置 i 的石头,提前结束
  22.                 if (B.empty()) return -1;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  23.                 // 位置 i 没有石头
  24.                 if (A[i] == -1) continue;

  25.                 // 在保证能有石头跳到位置 i 的情况下,把位置靠前但耗时没有更少的石头从队列除去
  26.                 while (B.size() > 1 && A[B.back()] >= A[i])
  27.                         B.pop_back();

  28.                 // 把 A[i] 改为从起到到达 A[i] 的最快时间
    . more info on 1point3acres.com
  29.                 A[i] = max(A[B.front()], A[i]);

  30. -google 1point3acres
  31.                 // 如果到达队列队首的石头耗时与到达石头 i 的耗时相同,则我们不会在队首石头停留,直接往 i 跳,所以把队首除去
  32.                 if (A[B.front()] == A[i]). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  33.                         B.pop_front();

  34.                 // 将石头的位置放入队列
  35.                 B.push_back(i);
  36.         }
  37.         // 如果队首石头无法直接到达终点,那就从队列除去 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  38.         if (N - B.front() == D + 1) B.pop_front();

  39.         // 队列有石头则可到达终点,最快时间为此时队列队首的耗时
  40.         return B.empty() ? -1 : A[B.front()];
  41. }
复制代码
. from: 1point3acres.com/bbs

不知道我这个解法有没有问题?

补充内容 (2016-9-20 16:07):
这个想法是来自这题 https://leetcode.com/problems/sliding-window-maximum/.1point3acres缃
. visit 1point3acres.com for more.
补充内容 (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
不知道我这个解法有没有问题?
. 1point 3acres 璁哄潧
补充内容 (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里面的最小值是不是等于当前时间,等于就说明对应的位置可以时候,更新最远距离,最远距离超过岸边值,就说明能够到达. 1point3acres.com/bbs

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-20 16:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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