LiveRamp笔试题求解——frog jump - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

LiveRamp笔试题求解——frog jump

LiveRamp笔试题求解——frog jump# JobHunting - 待字闺中

i*r2015-10-25 07:10

1 楼

青蛙初始位置0，对岸坐标X，青蛙最远可跳距离为D，给出长度N的数组A[K]，下标表示
时刻，值表示该时刻落叶的坐标。青蛙可以用落叶做跳板。返回青蛙最早到达对岸的时
刻。不能到达返回-1.
例如 D=3, X=5, A=[1,2,3], 返回1.
要求时间O(N),空间O(X)
我的做法是设一个长X的bool数组记录[0,X]每个位置有否有叶子。每个时刻看新落叶是
否在前面，能否跳上，不能跳上就记录，能跳上就更新青蛙位置p，然后从p+D倒搜有否
叶子，更新p直至无法前进。每次更新位置判断是否能跳到目的地。
我感觉我的做法最坏情况是O(ND)而不是O(N)，求更好的思路。

j*72015-10-25 07:10

2 楼

// time O(N). space O(X)
public int solution(int[] A, int X, int D) {
LinkedList deque = new LinkedList();
int[] pos = new int[X + 1];
pos[0] = 0;
pos[X] = 0;
for (int i = 1; i < X; i++) {
pos[i] = -1;
}
for (int i = 0; i < A.length; i++) {
if (pos[A[i]] == -1) {
pos[A[i]] = i;
}
}
int[] DP = new int[X + 1];
DP[0] = 0;
deque.add(0);
for (int i = 1; i <= X; i++) {
while (deque.isEmpty() == false && deque.getFirst() + D < i) {
deque.removeFirst();
}
if (pos[i] == -1 || deque.isEmpty()) {
DP[i] = -1;
continue;
}
DP[i] = Math.max(pos[i], DP[deque.getFirst()]);
while (deque.isEmpty() == false && DP[deque.getLast()] >= DP[i])
{
deque.removeLast();
}
deque.addLast(i);
}
return DP[X];
}

j*72015-10-25 07:10

3 楼

http://www.mitbbs.com/article_t/JobHunting/33055941.html