一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 2760|回复: 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. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
http://www.1point3acres.com/bbs/ ... ;highlight=liveramp

首先说一下两个题目不同点就是A[k]的表示,
. from: 1point3acres.com/bbs 青蛙的是 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)-google 1point3acres
  3.            return -1;
  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;.1point3acres缃
  15.                                 int count = 0;
  16.                                 for (int j = 1; j <= D; j++) {. 1point3acres.com/bbs
  17.                                         if (B[i - j] == -1) {
  18.                                                 count++;
  19.                                                 continue;. 1point3acres.com/bbs
  20.                                         }. visit 1point3acres.com for more.
  21.                                         temp = Math.min(temp, B[i - j]);
  22.                                 }. From 1point 3acres bbs
  23.                                 B[i] = count == D ? -1 : Math.max(temp, A[i]);
  24.                         }
  25.                 }
  26.                 int res = Integer.MAX_VALUE;
  27.                 int count = 0;
  28.                 for (int j = 1; j <= D; j++) {
  29.                         if (B[A.length - j] == -1) {
  30.                                 count++;. 1point3acres.com/bbs
  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 | 显示全部楼层
楼上是烙印?...惊了...『似乎并没有工作』... seems not working?
回复 支持 1 反对 0

使用道具 举报

 楼主| gaohannk 发表于 2016-5-30 07:33:45 | 显示全部楼层
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. 鍥磋鎴戜滑@1point 3 acres
      =  -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();.1point3acres缃
  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) {. 鍥磋鎴戜滑@1point 3 acres
  17.                 // 如果队列中第一个石头已经在跳跃范围 D 以外了,那我们就不能从那个石头跳到位置 i 了,所以除去
  18.                 if (!B.empty() && i - B.front() == D + 1)
  19.                         B.pop_front();

  20.                 // 如果队列中没有石头,意味着就没有能够到达位置 i 的石头,提前结束
  21.                 if (B.empty()) return -1;

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

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

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

  29.                 // 如果到达队列队首的石头耗时与到达石头 i 的耗时相同,则我们不会在队首石头停留,直接往 i 跳,所以把队首除去
  30.                 if (A[B.front()] == A[i]).鐣欏璁哄潧-涓浜-涓夊垎鍦
  31.                         B.pop_front();

  32.                 // 将石头的位置放入队列
  33.                 B.push_back(i);
  34.         }
  35.         // 如果队首石头无法直接到达终点,那就从队列除去
  36.         if (N - B.front() == D + 1) B.pop_front();

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


不知道我这个解法有没有问题?.鏈枃鍘熷垱鑷1point3acres璁哄潧
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2016-9-20 16:07):
这个想法是来自这题 https://leetcode.com/problems/sliding-window-maximum/

补充内容 (2016-10-2 15:54):
应该在最后 if (N - B.front() == D + 1) B.pop_front(); 的条件加一个 !B.empty(),不确定还有没有别的 bug,求指导
回复 支持 反对

使用道具 举报

头像被屏蔽
startuptech11 发表于 2016-9-29 04:44:55 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

仲夏夜 发表于 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 发表于 6 天前 | 显示全部楼层
请问下楼主,这道题可不可以用priorityqueue储存数组A里面的元素,然后dp储存当前时间所能到达的最远距离,每次只要看priorityqueue里面的最小值是不是等于当前时间,等于就说明对应的位置可以时候,更新最远距离,最远距离超过岸边值,就说明能够到达

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 19:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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