n******n
发帖数: 11 | 1 在面试时遇到这样一个问题，大概意思是：
- A bug is trying to cross the river start from position 0 to position X
- Every time bug can jump no more than the D steps (1 to D steps);
- Leaves will fall from the tree to the river based on schedule A. A[0] = 1
means a leaf will fall on position 1 at time 0;
- Need to find the earliest time that the bug can jump from position 0 to x
using leaves; If there is no answer, return -1;
Example:
A = [1, 3, 1, 4, 2, 5]
X = 7
D = 3
Answer: 3
Explanation: At time 3, there will be leaves on position 1,3, and 4; bug can
jump 1 step, 3 step, and then 3 steps to cross the river;
Expected time complexity is O(n)
请教各位解题思路，先谢谢了~ | j**7
发帖数: 143 | 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];
} | T****U
发帖数: 3344 | 3 int[] dp = new int[A.length + 1];
for (int i = 0; i < A.length; i++){
if (A[i] > dp[i] && A[i] - dp[i] <= D){
dp[i + 1] = A[i];
} else {
dp[i + 1] = dp[i];
}
if (dp[i + 1] >= x - D) return i; // jumping takes no time
}
return -1;
1
x
【在 n******n 的大作中提到】
: 在面试时遇到这样一个问题，大概意思是：
: - A bug is trying to cross the river start from position 0 to position X
: - Every time bug can jump no more than the D steps (1 to D steps);
: - Leaves will fall from the tree to the river based on schedule A. A[0] = 1
: means a leaf will fall on position 1 at time 0;
: - Need to find the earliest time that the bug can jump from position 0 to x
: using leaves; If there is no answer, return -1;
: Example:
: A = [1, 3, 1, 4, 2, 5]
: X = 7
| n******n
发帖数: 11 | 4 谢谢回复， 这个好像不对
如果 A=[5,2,1], X=8, D=4 就会return -1
【在 T****U 的大作中提到】
: int[] dp = new int[A.length + 1];
: for (int i = 0; i < A.length; i++){
: if (A[i] > dp[i] && A[i] - dp[i] <= D){
: dp[i + 1] = A[i];
: } else {
: dp[i + 1] = dp[i];
: }
: if (dp[i + 1] >= x - D) return i; // jumping takes no time
: }
: return -1;
| k**l
发帖数: 2966 | 5 这是开发超超级玛莉的group?
1
x
【在 n******n 的大作中提到】
: 在面试时遇到这样一个问题，大概意思是：
: - A bug is trying to cross the river start from position 0 to position X
: - Every time bug can jump no more than the D steps (1 to D steps);
: - Leaves will fall from the tree to the river based on schedule A. A[0] = 1
: means a leaf will fall on position 1 at time 0;
: - Need to find the earliest time that the bug can jump from position 0 to x
: using leaves; If there is no answer, return -1;
: Example:
: A = [1, 3, 1, 4, 2, 5]
: X = 7
| g******y
发帖数: 143 | 6 for each time i = 0 : n
call jump game I function
if it returns true, then return i
1
x
【在 n******n 的大作中提到】
: 在面试时遇到这样一个问题，大概意思是：
: - A bug is trying to cross the river start from position 0 to position X
: - Every time bug can jump no more than the D steps (1 to D steps);
: - Leaves will fall from the tree to the river based on schedule A. A[0] = 1
: means a leaf will fall on position 1 at time 0;
: - Need to find the earliest time that the bug can jump from position 0 to x
: using leaves; If there is no answer, return -1;
: Example:
: A = [1, 3, 1, 4, 2, 5]
: X = 7
| j**7
发帖数: 143 | 7 In order to reach position i, we must jump to i from positions
i-D, i-D+1, .... i-1. Thus, there are D number of ways to jump to position i.
DP[i]= the earliest time we can reach position i.
The best way to reach position i is selected from DP[i-D] to DP[i-1]. We
have to find the min value from DP[i-D] to DP[i-1].
In other words, we have to find the minimum value in a sub-array of size D.
Therefore, this problem can be reduced to the problem of finding the minimum
value in a sliding window of size D in an array.
https://leetcode.com/problems/sliding-window-maximum/
1
x
【在 n******n 的大作中提到】
: 在面试时遇到这样一个问题，大概意思是：
: - A bug is trying to cross the river start from position 0 to position X
: - Every time bug can jump no more than the D steps (1 to D steps);
: - Leaves will fall from the tree to the river based on schedule A. A[0] = 1
: means a leaf will fall on position 1 at time 0;
: - Need to find the earliest time that the bug can jump from position 0 to x
: using leaves; If there is no answer, return -1;
: Example:
: A = [1, 3, 1, 4, 2, 5]
: X = 7
| r****7
发帖数: 2282 | 8 o(n)的n指啥？A中的元素数目？
我可以想到o(A.size() * D)的解法，优化一下可以o(A.size() * lg(D))
1
x
【在 n******n 的大作中提到】
: 在面试时遇到这样一个问题，大概意思是：
: - A bug is trying to cross the river start from position 0 to position X
: - Every time bug can jump no more than the D steps (1 to D steps);
: - Leaves will fall from the tree to the river based on schedule A. A[0] = 1
: means a leaf will fall on position 1 at time 0;
: - Need to find the earliest time that the bug can jump from position 0 to x
: using leaves; If there is no answer, return -1;
: Example:
: A = [1, 3, 1, 4, 2, 5]
: X = 7
| y******s
发帖数: 92 | 9 public static int cross(int[] A, int X, int D) {
int reach = D;
if (reach >= X) {
return 0;
}
PriorityQueue pq = new PriorityQueue();
for (int i = 0; i < A.length; i++) {
if (A[i] <= reach) {
reach = Math.max(reach, A[i] + D);
}
else {
pq.add(A[i]);
}
while (!pq.isEmpty() && reach >= pq.peek()) {
reach = Math.max(reach, pq.poll()+D);
}
if (reach >= X) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] A = {1, 3, 1, 4, 2, 5};
System.out.println(cross(A, 7, 3));
int[] B = {5, 2, 1};
System.out.println(cross(B, 8, 4));
} | l******s
发帖数: 3045 | 10 谢谢分享。不过会有time O(n)的可能么？
写了一个O(nln(n))的对付一下。
private static int jumpTimes(int[] leaves, int distance, int maxStep){
SortedDictionary dict = new SortedDictionary();
int i = 0;
for(i = 0; i < leaves.Length; i++)
if(!dict.ContainsKey(leaves[i])) dict[leaves[i]] = i;
int[,] lt = new int[dict.Count, 2];
i = 0;
foreach(var d in dict)
{ lt[i, 0] = d.Key; lt[i++, 1] = d.Value; }
for(i = 0; i < lt.Length; i++){
if(lt[i, 0] - (i == 0 ? 0 : lt[i - 1, 0]) > maxStep) return -1;
int j = i - 1, min = int.MaxValue;
while(j >= 0 && lt[i, 0] - lt[j, 0] <= maxStep){
if(lt[j, 1] > lt[i, 1]) min = Math.Min(min, lt[j, 1]);
else { min = lt[i, 1]; break; }
j--;
}
if(min != int.MaxValue) lt[i, 1] = min;
if(lt[i, 0] + maxStep >= distance) return lt[i, 1];
}
return -1;
} | | | l******s
发帖数: 3045 | 11 这个方法是Time O(X)吧，当步幅很大时就要吃亏了，比如X = 2,000,000,000, D =
200,000,000。
【在 j**7 的大作中提到】
: In order to reach position i, we must jump to i from positions
: i-D, i-D+1, .... i-1. Thus, there are D number of ways to jump to position i.
: DP[i]= the earliest time we can reach position i.
: The best way to reach position i is selected from DP[i-D] to DP[i-1]. We
: have to find the min value from DP[i-D] to DP[i-1].
: In other words, we have to find the minimum value in a sub-array of size D.
: Therefore, this problem can be reduced to the problem of finding the minimum
: value in a sliding window of size D in an array.
: https://leetcode.com/problems/sliding-window-maximum/
:
| j**7
发帖数: 143 | 12 是 O(N+X). 如果X比N要小就是O(N)了。
【在 l******s 的大作中提到】
: 这个方法是Time O(X)吧，当步幅很大时就要吃亏了，比如X = 2,000,000,000, D =
: 200,000,000。
| l*******2
发帖数: 8 | 13 叶子掉下来就一直停那儿？这样的话是不是greedy就可以？每次能跑多远跑多远
1
x
【在 n******n 的大作中提到】
: 在面试时遇到这样一个问题，大概意思是：
: - A bug is trying to cross the river start from position 0 to position X
: - Every time bug can jump no more than the D steps (1 to D steps);
: - Leaves will fall from the tree to the river based on schedule A. A[0] = 1
: means a leaf will fall on position 1 at time 0;
: - Need to find the earliest time that the bug can jump from position 0 to x
: using leaves; If there is no answer, return -1;
: Example:
: A = [1, 3, 1, 4, 2, 5]
: X = 7
| g******z
发帖数: 893 | 14 这题的意思是虫子每轮只能跳一次，还是等到有路径了可以一轮一口气就跳完？如果是
前者，那楼主的例子应该返回4吧？
我按照后者写了一个，看着是O(Dn)的，大家看看有问题没
def jump(A, X, D):
n = len(A)
L = [False]*(X+1)
C = [False]*(X+1)
C[0], C[X] = True, True
L[0] = True
for t in range(n):
C[A[t]] = True
if not L[A[t]] and (L[A[t]-1] or L[A[t]-2] or L[A[t]-3]):
L[A[t]] = True
if A[t]==X:
return t
for i in range(D):
if not L[A[t]+i+1] and C[A[t]+i+1]:
L[A[t]+i+1] = True
if A[t]+i+1==X:
return t
return -1 | l*3
发帖数: 2279 | 15 没看懂，能讲一下思路吗？谢谢。
【在 j**7 的大作中提到】
: 是 O(N+X). 如果X比N要小就是O(N)了。
| n******n
发帖数: 11 | 16 我也没怎么看懂jas7的方法，不过他提示了看leetcode的Sliding Window Maximum，感
觉是对的。。。我继续看，yimingts的方法我貌似看懂了，但里面有个priority queue
，所以感觉是nlogn了
【在 l*3 的大作中提到】
: 没看懂，能讲一下思路吗？谢谢。
| l*3
发帖数: 2279 | 17 这个懂了，谢谢！
i.
.
minimum
【在 j**7 的大作中提到】
: In order to reach position i, we must jump to i from positions
: i-D, i-D+1, .... i-1. Thus, there are D number of ways to jump to position i.
: DP[i]= the earliest time we can reach position i.
: The best way to reach position i is selected from DP[i-D] to DP[i-1]. We
: have to find the min value from DP[i-D] to DP[i-1].
: In other words, we have to find the minimum value in a sub-array of size D.
: Therefore, this problem can be reduced to the problem of finding the minimum
: value in a sliding window of size D in an array.
: https://leetcode.com/problems/sliding-window-maximum/
:
| l*3
发帖数: 2279 | 18 懂了，sliding window maxi算法已看，十分巧妙！
queue
【在 n******n 的大作中提到】
: 我也没怎么看懂jas7的方法，不过他提示了看leetcode的Sliding Window Maximum，感
: 觉是对的。。。我继续看，yimingts的方法我貌似看懂了，但里面有个priority queue
: ，所以感觉是nlogn了
| j******3
发帖数: 16 | 19 感觉线性时间不现实，严格来说应该是O(Dn)吧。强行忽略window size的系数，才会到
n吧，不然真是白瞎了。
随便写了个O(Dn)，用的DP，我估摸着贪心算法可能可行。
算法链接 cpp.sh/5afu | M***6
发帖数: 895 | 20 原题在这。https://codility.com/demo/results/demoH5GMV3-PV8/
A small frog wants to get to the other side of a river. The frog is
currently located at position 0, and wants to get to position X. Leaves fall
from a tree onto the surface of the river.
You are given a non-empty zero-indexed array A consisting of N integers
representing the falling leaves. A[K] represents the position where one leaf
falls at time K, measured in seconds.
The goal is to find the earliest time when the frog can jump to the other
side of the river. The frog can cross only when leaves appear at every
position across the river from 1 to X. You may assume that the speed of the
current in the river is negligibly small, i.e. the leaves do not change
their positions once they fall in the river.
For example, you are given integer X = 5 and array A such that:
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
In second 6, a leaf falls into position 5. This is the earliest time when
leaves appear in every position across the river.
Write a function:
class Solution { public int solution(int X, int[] A); }
that, given a non-empty zero-indexed array A consisting of N integers and
integer X, returns the earliest time when the frog can jump to the other
side of the river.
If the frog is never able to jump to the other side of the river, the
function should return −1.
For example, given X = 5 and array A such that:
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
the function should return 6, as explained above.
Assume that:
N and X are integers within the range [1..100,000];
each element of array A is an integer within the range [1..X].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(X), beyond input storage (not
counting the storage required for input arguments).
Elements of input arrays can be modified. | | | d****m
发帖数: 1008 | 21 你面的哪家啊？我刚刚做的一个公司的online coding challenge就这道题。
其实没必要想那么麻烦，遍历一边数组记录下来每个位置落叶的最短时间，这个是O(N)
。然后对这个新的数组求一个sliding window minimum就行了，之前有个人已经发过了
，就是leetcode上那题。最后求出所有sliding window minimum里面的maximum就是最
短过河所需时间。
尽管需要三个iteration，但是每个都是O(N)所以还是线性的。 | j**7
发帖数: 143 | 22 你这题不一样
fall
leaf
the
【在 M***6 的大作中提到】
: 原题在这。https://codility.com/demo/results/demoH5GMV3-PV8/
: A small frog wants to get to the other side of a river. The frog is
: currently located at position 0, and wants to get to position X. Leaves fall
: from a tree onto the surface of the river.
: You are given a non-empty zero-indexed array A consisting of N integers
: representing the falling leaves. A[K] represents the position where one leaf
: falls at time K, measured in seconds.
: The goal is to find the earliest time when the frog can jump to the other
: side of the river. The frog can cross only when leaves appear at every
: position across the river from 1 to X. You may assume that the speed of the
| j**7
发帖数: 143 | 23 你的思路跟我的一样。sliding window minimum 有个O(N)解法所以这题也是O(N).
我做的一个公司给的Codility test有这道题。Codility要求时间复杂度是O(N)空间复
杂度是O(X).
N is an integer within the range [0..100,000]
X and D are integers within the range [1..100,000]
each element of array A is an integer within the range [1..X-1].
Expected: O(N) time and O(X) extra space.
N)
【在 d****m 的大作中提到】
: 你面的哪家啊？我刚刚做的一个公司的online coding challenge就这道题。
: 其实没必要想那么麻烦，遍历一边数组记录下来每个位置落叶的最短时间，这个是O(N)
: 。然后对这个新的数组求一个sliding window minimum就行了，之前有个人已经发过了
: ，就是leetcode上那题。最后求出所有sliding window minimum里面的maximum就是最
: 短过河所需时间。
: 尽管需要三个iteration，但是每个都是O(N)所以还是线性的。
| g*******d
发帖数: 495 | 24 贴一个我的解法
https://coderpad.io/W6A44W42
先用一个map，从position对应到出现叶子的时间；如果某位置不会出现叶子，那么就
没这个item。
然后尝试前进1到D步，每次尽量往远的地方走；如果必须等待叶子落下，就前进到等待
最少的地方。
重复直到走到了目的地。 | s***g
发帖数: 1250 | 25 int bugCrossRiver(vector a, int X, int D)
{
int n = a.size();
int stepToX = X;
int curPos = 0;
int prePos = 0;
for (int i=0; i
int diff = a[i]-curPos;
if (diff>0 && diff<=D) {
curPos = a[i];
stepToX -= curPos;
stepToX += prePos;
prePos = a[i];
if (stepToX<=D) {
return i;
}
}
}
return -1;
} | r****7
发帖数: 2282 | 26 记录每个位置落叶最短时间是什么意思？
如果只遍历N就是原数组，要么就是N*D
N)
【在 d****m 的大作中提到】
: 你面的哪家啊？我刚刚做的一个公司的online coding challenge就这道题。
: 其实没必要想那么麻烦，遍历一边数组记录下来每个位置落叶的最短时间，这个是O(N)
: 。然后对这个新的数组求一个sliding window minimum就行了，之前有个人已经发过了
: ，就是leetcode上那题。最后求出所有sliding window minimum里面的maximum就是最
: 短过河所需时间。
: 尽管需要三个iteration，但是每个都是O(N)所以还是线性的。
|
|
