l******s
发帖数: 3045 | 1 A frog is trying to jump across a river by hopping on rocks in between the
left and right banks.
At each step, the frog can choose 3 speeds to jump to the next rocks (not
necessary neighbor), increase 1 speed, decrease 1 speed or keep the same
speed.
You are given a list of rock's positions (sorted), and need return if the
frog can jump cross the river.
The frog starts from stone position 0, and the initial speed is 0. | k****r
发帖数: 807 | 2 bfs?
Use a queue to record the pair of speed and position P(s,p);
At each poll to add new P(s, p + s), P(s + 1, p + s + 1), P(s - 1, p + s - 1
) if there is a rock at any of new position.
return true, if the right bank is reached; return false, if queue is empty. | l******s
发帖数: 3045 | 3 Code, Code, we are on programming discussion board.
BTW: this problem comes from Snapchat.
1
.
【在 k****r 的大作中提到】
: bfs?
: Use a queue to record the pair of speed and position P(s,p);
: At each poll to add new P(s, p + s), P(s + 1, p + s + 1), P(s - 1, p + s - 1
: ) if there is a rock at any of new position.
: return true, if the right bank is reached; return false, if queue is empty.
| v*****u
发帖数: 1796 | 4 看不懂题目。。。
【在 l******s 的大作中提到】
: A frog is trying to jump across a river by hopping on rocks in between the
: left and right banks.
: At each step, the frog can choose 3 speeds to jump to the next rocks (not
: necessary neighbor), increase 1 speed, decrease 1 speed or keep the same
: speed.
: You are given a list of rock's positions (sorted), and need return if the
: frog can jump cross the river.
: The frog starts from stone position 0, and the initial speed is 0.
| l******s
发帖数: 3045 | 5 I was in a telephone and listen to all to get the problem. There wasn't text
descriptions and samples, and function input needs you define it, so I
started in this way.
I was waiting for your questions just like how the interview worked. Now I
am adding a few samples below:
1) stone list 0, 1, 3, 5, 6, 8, 12, 17 is reachable, the frog is jumping
from stone 0 with +1 speed, it goes to stone 1, then +1 it goes to stone 3,
then keep same speed to go to stone 5, and so on, after trying all
possibilities there is a way the frog can jump out of stone 17.
2) 0, 1, 2, 3, 4, 8, 9, 11 is not reachable because there is no jumping
combinations satisfy the frog jump over stone 11.
【在 v*****u 的大作中提到】
: 看不懂题目。。。
| y***a
发帖数: 840 | 6 a=[ 0, 1, 3, 5, 6, 8, 12, 17]
b=[0, 1, 2, 3, 4, 8, 9, 11]
def jump(pL, current_speed, current_position):
if not pL:
return [(current_speed, current_position)]
if current_position+current_speed in pL:
idx = pL.index(current_position+current_speed)
rv = jump(pL[idx+1:], current_speed, current_position+current_speed)
if rv:
return [(current_speed, current_position+current_speed)] + rv
if current_position+current_speed+1 in pL:
idx = pL.index(current_position+current_speed+1)
rv = jump(pL[idx+1:], current_speed+1, current_position+current_
speed+1)
if rv:
return [(current_speed+1, current_position+current_speed+1)] +
rv
if current_position+current_speed-1 in pL:
idx = pL.index(current_position+current_speed-1)
rv = jump(pL[idx+1:], current_speed-1, current_position+current_
speed-1)
if rv:
return [(current_speed-1, current_position+current_speed-1)] +
rv
return None
print '============',a
print jump(a, 0, 0)
print '============',b
print jump(b, 0, 0) | I******c
发帖数: 163 | 7 这道题用dynamic programming来解决
做一个表格，横轴代表每个石头的位置，纵轴代表速度。速度的最大值就是最远石头的
开方。因为假设速度增加的最佳情况是1+2+3+4+5....,所以最远石头的距离就是n*(n+1
),n就是最大速度。
对于表中的任何一个值t(p,s)代表青蛙有没有可能以s的速度到达p石头的位置。
t(p,s)= t(p-s,s-1) || t(p-s),s) || t(p-s,s+1) | I******c
发帖数: 163 | 8 个人认为，无论是用dfs (backtracking) 还是bfs都是穷尽的思路，其中很多重复计算
，时间复杂度是指数级。 | b***S
发帖数: 29 | 9 0, 1, 3, 5, 6, 8, 12, 17 is reachable
怎么从8跳到12啊,前面6->8的时候速度才是2, 2+1=3, 3+8=11啊,到不了12啊
text
,
【在 l******s 的大作中提到】
: I was in a telephone and listen to all to get the problem. There wasn't text
: descriptions and samples, and function input needs you define it, so I
: started in this way.
: I was waiting for your questions just like how the interview worked. Now I
: am adding a few samples below:
: 1) stone list 0, 1, 3, 5, 6, 8, 12, 17 is reachable, the frog is jumping
: from stone 0 with +1 speed, it goes to stone 1, then +1 it goes to stone 3,
: then keep same speed to go to stone 5, and so on, after trying all
: possibilities there is a way the frog can jump out of stone 17.
: 2) 0, 1, 2, 3, 4, 8, 9, 11 is not reachable because there is no jumping
| W***o
发帖数: 6519 | 10 没有距离信息嘛？
【在 l******s 的大作中提到】
: A frog is trying to jump across a river by hopping on rocks in between the
: left and right banks.
: At each step, the frog can choose 3 speeds to jump to the next rocks (not
: necessary neighbor), increase 1 speed, decrease 1 speed or keep the same
: speed.
: You are given a list of rock's positions (sorted), and need return if the
: frog can jump cross the river.
: The frog starts from stone position 0, and the initial speed is 0.
| | | g*****y
发帖数: 7271 | 11 from 5 to 8, skip 6.
【在 b***S 的大作中提到】
: 0, 1, 3, 5, 6, 8, 12, 17 is reachable
: 怎么从8跳到12啊,前面6->8的时候速度才是2, 2+1=3, 3+8=11啊,到不了12啊
:
: text
: ,
| w********m
发帖数: 1137 | 12 像楼上说的，二维dp
leetcode可以收录了
应该是hard | C*****n
发帖数: 1049 | 13 这道题我在snapchat onsite的时候也遇到了，以前没见过，当时只给出了dfs的解。
现在给出dfs和dp的解，可能有bug，没做深度测试。
#include
#include
using namespace std;
//basically we can use a dfs to solve the problem
bool jumpDfs(vector & stone_pos, int pos, int speed) {
int n=stone_pos.size();
if(pos==n-1) return true;
if(!stone_pos[pos] || pos>=n || speed<1) return false;
for(int s=speed-1; s<=speed+1; ++s) {
if(jumpDfs(stone_pos,pos+s,s)) return true;
}
return false;
}
//assume init_speed >= 0
bool canJumpOverDfs(vector & stone_idx, int init_speed) {
//convert stone_idx to a bool array {1,1,1,0,0,1,1,0,0,0,0,0,1}
int n=stone_idx.back()+1;
vector stone_pos(n);
for(int p:stone_idx) stone_pos[p]=true;
return jumpDfs(stone_pos,0,init_speed);
}
//dfs has a lot of repeated calculations, we can use dp to avoid it
//assume init_speed >= 0
bool canJumpOverDp(vector & stone_idx, int init_speed) {
//convert stone_idx to a bool array {1,1,1,0,0,1,1,0,0,0,0,0,1}
int n=stone_idx.back()+1;
vector stone_pos(n);
for(int p:stone_idx) stone_pos[p]=true;
//assume every stone_position is a stone, the max speed at the end is
less than
int safe_max_speed=init_speed+n-1;
//the actual max speed could be calculated by:
//(init_speed+1) + (init_speed+2) + ... + max_speed = n;
// max_speed < safe_max_speed
//dp[p][s] means at stone position p, if there exists a case that frog
has speed s
vector> dp(n, vector(safe_max_speed+1));
if(init_speed>=1) dp[0][init_speed-1]=true;
dp[0][init_speed]=dp[0][init_speed+1]=true;
for(int p=1; p
if(stone_pos[p]) {
for(int s=1; s<=safe_max_speed; ++s) {
//any dp[p][s] can be achived by the previous stone_position
p-(s-1) with speed s-1
//after the jump, increase speed by 1, then we get stone_
position p with speed s;
//also it can be achived by the previous stone_position p-s
with speed s;
//and the previous stone_position p-(s+1) with speed s+1
if(p>=s-1) dp[p][s]=dp[p-s+1][s-1];
if(p>=s) dp[p][s]=dp[p][s] || dp[p-s][s];
if(p>=s+1) dp[p][s]=dp[p][s] || dp[p-s-1][s+1];
}
}
}
//check the last stone_position, if there exists a case that frog has
any speed
for(bool b:dp[n-1]) {
if(b) return true;
}
return false;
}
int main() {
vector stone_idx={0,1,2,5,6,12};
//initial speed 5,6,7 are good to reach the end
cout << "Dfs: init speed=4, can jump over? " << canJumpOverDfs(stone_idx
,4) << endl;
cout << "Dp: init speed=4, can jump over? " << canJumpOverDp(stone_idx,
4) << endl;
cout << "Dfs: init speed=5, can jump over? " << canJumpOverDfs(stone_idx
,5) << endl;
cout << "Dp: init speed=5, can jump over? " << canJumpOverDp(stone_idx,
5) << endl;
} | k****i
发帖数: 101 | 14 hop _ _ [] = True
hop speed pos poz = or [
hop speed_n pos_n $ dropWhile (<= pos_n) poz |
n <- [-1..1], let speed_n = speed + n, let pos_n = pos + speed_n,
elem pos_n poz ]
main = do
print $ hop 0 0 [0, 1, 3, 5, 6, 8, 12, 17] -- True
print $ hop 0 0 [0, 1, 2, 3, 4, 8, 9, 11] -- False
【在 l******s 的大作中提到】
: A frog is trying to jump across a river by hopping on rocks in between the
: left and right banks.
: At each step, the frog can choose 3 speeds to jump to the next rocks (not
: necessary neighbor), increase 1 speed, decrease 1 speed or keep the same
: speed.
: You are given a list of rock's positions (sorted), and need return if the
: frog can jump cross the river.
: The frog starts from stone position 0, and the initial speed is 0.
| g*********e
发帖数: 14401 | 15 dp
Use Boolean matrix dp(x, s) to denote if frog can reach rock x at step s.
O(n*s*s)
【在 l******s 的大作中提到】
: A frog is trying to jump across a river by hopping on rocks in between the
: left and right banks.
: At each step, the frog can choose 3 speeds to jump to the next rocks (not
: necessary neighbor), increase 1 speed, decrease 1 speed or keep the same
: speed.
: You are given a list of rock's positions (sorted), and need return if the
: frog can jump cross the river.
: The frog starts from stone position 0, and the initial speed is 0.
| g*********e
发帖数: 14401 | 16 Definitely doesn't warrant "hard"
A typical medium problem for Leetcode
【在 w********m 的大作中提到】
: 像楼上说的，二维dp
: leetcode可以收录了
: 应该是hard
| w********m
发帖数: 1137 | 17 https://leetcode.com/problems/frog-jump/
【在 g*********e 的大作中提到】
: Definitely doesn't warrant "hard"
: A typical medium problem for Leetcode
| w***j
发帖数: 10 | 18 [0, Integer.MAX_VALUE]
【在 g*********e 的大作中提到】
: dp
: Use Boolean matrix dp(x, s) to denote if frog can reach rock x at step s.
: O(n*s*s)
|
|
