https://leetcode.com/problems/frog-jump/
X. DP
http://www.cnblogs.com/grandyang/p/5888439.html
我们也可以用迭代的方法来解，用一个哈希表来建立每个石头和在该位置上能跳的距离之间的映射，建立一个一维dp数组，其中dp[i]表示在位置为i的石头青蛙的弹跳力(只有青蛙能跳到该石头上，dp[i]才大于0)，由于题目中规定了第一个石头上青蛙跳的距离必须是1，为了跟后面的统一，我们对青蛙在第一块石头上的弹跳力初始化为0(虽然为0，但是由于题目上说青蛙最远能到其弹跳力+1的距离，所以仍然可以到达第二块石头)。我们用变量k表示当前石头，然后开始遍历剩余的石头，对于遍历到的石头i，我们来找到刚好能跳到i上的石头k，如果i和k的距离大于青蛙在k上的弹跳力+1，则说明青蛙在k上到不了i，则k自增1。我们从k遍历到i，如果青蛙能从中间某个石头上跳到i上，我们更新石头i上的弹跳力和最大弹跳力。这样当循环完成后，我们只要检查最后一个石头上青蛙的最大弹跳力是否大于0即可
I chose arraylist instead of map (map is better i tihnk), also I think we don't need loop to the stones.length, when current is already bigger than the reach, can prune mostly but still same in worst case.
X. DP
http://www.voidcn.com/blog/tc_to_top/article/p-6237336.html
X. DFS
public boolean canCross(int[] stones){ for (int i = 1; i < stones.length; i++) if (stones[i] - stones[i - 1] > i) return false; return hop(stones, 0, 1); } private boolean hop(int[] stones, int idx, int step) { if (idx == stones.length - 1) return true; if (idx < 0 || step <= 0) return false; for(int jump = step+1; jump >= step - 1; jump--){ if(hop(stones, Arrays.binarySearch(stones, stones[idx] + jump), jump)) return true; } return false; }
https://leetcode.com/problems/frog-jump/discuss/88804/JAVA-DFS-17ms-beat-99.28-so-far
终于等到青蛙过河问题了，一颗赛艇。题目中说青蛙如果上一次跳了k距离，那么下一次只能跳k-1, k, 或k+1的距离，那么青蛙跳到某个石头上可能有多种跳法，由于这道题只是让我们判断青蛙是否能跳到最后一个石头上，并没有让我们返回所有的路径，这样就降低了一些难度。
我们可以用递归来做，我们维护一个哈希表，建立青蛙在pos位置和拥有jump跳跃能力时是否能跳到对岸。为了能用一个变量同时表示pos和jump，我们可以将jump左移很多位并或上pos，由于题目中对于位置大小有限制，所以不会产生冲突。我们还是首先判断pos是否已经到最后一个石头了，是的话直接返回true；然后看当前这种情况是否已经出现在哈希表中，是的话直接从哈希表中取结果。如果没有，我们就遍历余下的所有石头，对于遍历到的石头，我们计算到当前石头的距离dist，如果距离小于jump-1，我们接着遍历下一块石头；如果dist大于jump+1，说明无法跳到下一块石头，m[key]赋值为false，并返回false；如果在青蛙能跳到的范围中，我们调用递归函数，以新位置i为pos，距离dist为jump，如果返回true了，我们给m[key]赋值为true，并返回true。如果结束遍历我们给m[key]赋值为false，并返回false
X. https://discuss.leetcode.com/topic/59439/straight-forward-9ms-7-line-c-solution-with-explanation
https://discuss.leetcode.com/topic/59337/easy-version-java
public boolean canCross(int[] stones) { int k = 0; return helper(stones, 0, k); } private boolean helper(int[] stones, int index, int k) { //目前已经达到了 if (index == stones.length - 1) return true; //选择k的步伐，范围k-1到k for (int i = k - 1; i <= k + 1; i++) { int nextJump = stones[index] + i; //看接下来有没有合适的石头可以跳过去，从接下来的位置中查找有没有nextJump的位置，有的话返回石头的编号 int nextPosition = Arrays.binarySearch(stones, index + 1, stones.length, nextJump); if (nextPosition > 0) { if (helper(stones, nextPosition, i)) return true; } } return false; }
http://xiadong.info/2016/09/leetcode-403-frog-jump/
X. BFS
http://bookshadow.com/weblog/2016/09/18/leetcode-frog-jump/
由于这道题只是让我们判断青蛙是否能跳到最后一个石头上，并没有让我们返回所有的路径，这样就降低了一些难度
http://www.georgelyu.me/2016/09/18/7/
A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.
Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.
If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.
Note:
- The number of stones is ≥ 2 and is < 1,100.
- Each stone's position will be a non-negative integer < 231.
- The first stone's position is always 0.
Example 1:
[0,1,3,5,6,8,12,17] There are a total of 8 stones. The first stone at the 0th unit, second stone at the 1st unit, third stone at the 3rd unit, and so on... The last stone at the 17th unit. Return true. The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.
Example 2:
[0,1,2,3,4,8,9,11] Return false. There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.- Extend: print one possible path
X. DP
http://www.cnblogs.com/grandyang/p/5888439.html
我们也可以用迭代的方法来解，用一个哈希表来建立每个石头和在该位置上能跳的距离之间的映射，建立一个一维dp数组，其中dp[i]表示在位置为i的石头青蛙的弹跳力(只有青蛙能跳到该石头上，dp[i]才大于0)，由于题目中规定了第一个石头上青蛙跳的距离必须是1，为了跟后面的统一，我们对青蛙在第一块石头上的弹跳力初始化为0(虽然为0，但是由于题目上说青蛙最远能到其弹跳力+1的距离，所以仍然可以到达第二块石头)。我们用变量k表示当前石头，然后开始遍历剩余的石头，对于遍历到的石头i，我们来找到刚好能跳到i上的石头k，如果i和k的距离大于青蛙在k上的弹跳力+1，则说明青蛙在k上到不了i，则k自增1。我们从k遍历到i，如果青蛙能从中间某个石头上跳到i上，我们更新石头i上的弹跳力和最大弹跳力。这样当循环完成后，我们只要检查最后一个石头上青蛙的最大弹跳力是否大于0即可
bool canCross(vector<int>& stones) { unordered_map<int, unordered_set<int>> m; vector<int> dp(stones.size(), 0); m[0].insert(0); int k = 0; for (int i = 1; i < stones.size(); ++i) { while (dp[k] + 1 < stones[i] - stones[k]) ++k; for (int j = k; j < i; ++j) { int t = stones[i] - stones[j]; if (m[j].count(t - 1) || m[j].count(t) || m[j].count(t + 1)) { m[i].insert(t); dp[i] = max(dp[i], t); break; } } } return dp.back() > 0; }
更好地做法是对于每个位置记录当前位置能向前走的距离，用一个map套set实现，90ms+
public boolean canCross(int[] stones) {
int len = stones.length;
Map<Integer, HashSet<Integer>> map = new HashMap<>();
for (int i = 0; i < len; i ++) {
map.put(stones[i], new HashSet<>());
}
map.get(0).add(1);
for (int i = 0; i < len - 1; i ++) {
for (int step : map.get(stones[i])) {
int to = step + stones[i];
if (to == stones[len - 1]) {
return true;
}
HashSet<Integer> tmp = map.get(to);
if (tmp != null) {
tmp.add(step);
if (step > 1) {
tmp.add(step - 1);
}
tmp.add(step + 1);
}
}
}
return false;
}
X. https://discuss.leetcode.com/topic/59903/very-easy-to-understand-java-solution-with-explanations
Use map to represent a mapping from the stone (not index) to the steps that can be taken from this stone.
so this will be
[0,1,3,5,6,8,12,17]
{17=[], 0=[1], 1=[1, 2], 3=[1, 2, 3], 5=[1, 2, 3], 6=[1, 2, 3, 4], 8=[1, 2, 3, 4], 12=[3, 4, 5]}
Notice that no need to calculate the last stone.
On each step, we look if any other stone can be reached from it, if so, we update that stone's steps by adding step, step + 1, step - 1. If we can reach the final stone, we return true. No need to calculate to the last stone.
public boolean canCross(int[] stones) {
if (stones.length == 0) {
return true;
}
HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>(stones.length);
map.put(0, new HashSet<Integer>());
map.get(0).add(1);
for (int i = 1; i < stones.length; i++) {
map.put(stones[i], new HashSet<Integer>() );
}
for (int i = 0; i < stones.length - 1; i++) {
int stone = stones[i];
for (int step : map.get(stone)) {
int reach = step + stone;
if (reach == stones[stones.length - 1]) {
return true;
}
HashSet<Integer> set = map.get(reach);
if (set != null) {
set.add(step);
if (step - 1 > 0) set.add(step - 1);
set.add(step + 1);
}
}
}
return false;
} public boolean canCross(int[] stones) {
if(stones.length==2) return stones[1]-stones[0]==1;
List<HashSet<Integer>> dp = new ArrayList<>(stones.length);
for(int i=0;i<stones.length;i++)
dp.add(new HashSet<Integer>());
Iterator<Integer> kSet;
dp.add(1, new HashSet<>(Arrays.asList(1)));
for(int i=2;i<stones.length;i++){
kSet = dp.get(i-1).iterator();
int j=i, k=-1;
while((k!=-1||kSet.hasNext())&&j<stones.length){
if(k==-1) k = kSet.next();
if(Math.abs(stones[j]-stones[i-1]-k)<=1) //k reach point
{
if(j == stones.length-1) return true;
HashSet<Integer> temp = dp.get(j);
temp.add(stones[j]-stones[i-1]);
}
else if (j == stones.length-1||stones[j]-stones[i-1]-1>k)
{k=-1;j=i-1;}
j++;
}
}
return false;
}
Important facts (correct me if I'm wrong):
- When the answer is True, DFS is typically faster than BFS.
- In BFS, pre-check is not necessary. Though it still decreases the general running time.
- Worst case time complexity: read this
I think the complexity is O(Nsqrt(N)).
Assume the number of steps we can take at a position, which is the size of the inner loop, is K. Worst case is when we have one stone at each possible position, creating a lot of possible jumpsizes. To get a jumpsize K, we must at least have stone [0, 1, 3, 6, 10, ..., a_K], i.e. we always take the maximal step at each stone so that at the K-th term of this array, we can take any jumpsize between 1 to K. This array satisfies a_n - a_(n-1) = a_(n-1) - a_(n-2), from which we can easily derive a_K = K(K-1) / 2. Hence, at a position x, the number of jumpsizes we can get is sqrt(x) and the overall complexity is O(N*sqrt(N))
Ref and math proof: https://math.stackexchange.com/questions/422559/what-is-sum-limits-i-1n-sqrt-i.
Assume the number of steps we can take at a position, which is the size of the inner loop, is K. Worst case is when we have one stone at each possible position, creating a lot of possible jumpsizes. To get a jumpsize K, we must at least have stone [0, 1, 3, 6, 10, ..., a_K], i.e. we always take the maximal step at each stone so that at the K-th term of this array, we can take any jumpsize between 1 to K. This array satisfies a_n - a_(n-1) = a_(n-1) - a_(n-2), from which we can easily derive a_K = K(K-1) / 2. Hence, at a position x, the number of jumpsizes we can get is sqrt(x) and the overall complexity is O(N*sqrt(N))
Ref and math proof: https://math.stackexchange.com/questions/422559/what-is-sum-limits-i-1n-sqrt-i.
public boolean canCross(int[] stones) {
Map<Integer, Set<Integer>> map = new HashMap<>(); // stone location --> step options that can be take from this stone
for (int i = 0; i < stones.length; i++) {
if (i > 0 && stones[i] - stones[i-1] > i) return false;//\\
map.put(stones[i], new HashSet<>());
}
map.get(0).add(1);
for (int i = 0; i < stones.length; i++) {
if (map.get(stones[i]).isEmpty()) return false;
for (int step : map.get(stones[i])) {
int reach = stones[i] + step;
if (reach == stones[stones.length-1]) return true;
if (!map.containsKey(reach)) continue;
for (int s = step + 1; s >= step - 1; s--) {
if (s > 0) map.get(reach).add(s);
}
}
}
return false;
}public static boolean canCross(int[] stones) {
Map<Integer, Set<Integer>> stoneMap = new HashMap<>();
for (int i = 1; i < stones.length; i++) {
stoneMap.put(stones[i], new HashSet<Integer>());
}
if(stones[0]+1 == stones[1]) {
stoneMap.get(stones[1]).add(1);
}
for(int i = 1; i < stones.length; i++) {
int eachStone = stones[i];
for(Integer K: stoneMap.get(eachStone)) {
if(K != 1 && stoneMap.containsKey(eachStone + K - 1)) {
stoneMap.get(eachStone + K - 1).add(K - 1);
}
if(stoneMap.containsKey(eachStone + K)) {
stoneMap.get(eachStone + K).add(K);
}
if(stoneMap.containsKey(eachStone + K + 1)) {
stoneMap.get(eachStone + K + 1).add(K + 1);
}
}
}
return stoneMap.get(stones[stones.length - 1]).size() >= 1;
}X. DP
http://www.voidcn.com/blog/tc_to_top/article/p-6237336.html
裸的n^2做法400ms+，lastPos[i]存到到i位置前可能的步长
public boolean canCross(int[] stones) {
int len = stones.length;
if (len == 2 && stones[1] - stones[0] > 1) {
return false;
}
Set[] lastPos = new Set[len + 1];
for (int i = 1; i < len; i ++) {
lastPos[i] = new HashSet<>();
}
lastPos[1].add(1);
for (int i = 2; i < len; i ++) {
for (int j = 1; j < i; j ++) {
if (lastPos[j].size() > 0) {
int dist = stones[i] - stones[j];
if (lastPos[j].contains(dist) || lastPos[j].contains(dist - 1) || lastPos[j].contains(dist + 1)) {
lastPos[i].add(dist);
}
}
}
}
return lastPos[len - 1].size() > 0;
}
X. DFS
public boolean canCross(int[] stones){ for (int i = 1; i < stones.length; i++) if (stones[i] - stones[i - 1] > i) return false; return hop(stones, 0, 1); } private boolean hop(int[] stones, int idx, int step) { if (idx == stones.length - 1) return true; if (idx < 0 || step <= 0) return false; for(int jump = step+1; jump >= step - 1; jump--){ if(hop(stones, Arrays.binarySearch(stones, stones[idx] + jump), jump)) return true; } return false; }
https://leetcode.com/problems/frog-jump/discuss/88804/JAVA-DFS-17ms-beat-99.28-so-far
(1) Using a HashSet to store all the positions of the stones. So when you are trying to jump to a position, you will know whether there is a stone at that position or not.
(2) Starting from the first valid position (the second stone if it is 1), you try to jump as far as possible. At each position, if you jumped x steps to this position, the next possible positions are position + x - 1, position + x and position + x + 1. If any of them is the last stone's position, then you can return true. If not, use DFS from the longest jump first.
(3) This path finding process can be terminated much earlier if there are two stones that are too far away.
(2) Starting from the first valid position (the second stone if it is 1), you try to jump as far as possible. At each position, if you jumped x steps to this position, the next possible positions are position + x - 1, position + x and position + x + 1. If any of them is the last stone's position, then you can return true. If not, use DFS from the longest jump first.
(3) This path finding process can be terminated much earlier if there are two stones that are too far away.
public boolean canCross(int[] stones) {
if (stones == null || stones.length == 0) {return false;}
int n = stones.length;
if (n == 1) {return true;}
if (stones[1] != 1) {return false;}
if (n == 2) {return true;}
int last = stones[n - 1];
HashSet<Integer> hs = new HashSet();
for (int i = 0; i < n; i++) {
if (i > 3 && stones[i] > stones[i - 1] * 2) {return false;} // The two stones are too far away.
hs.add(stones[i]);
}
return canReach(hs, last, 1, 1);
}
private boolean canReach(HashSet<Integer> hs, int last, int pos, int jump) {
if (pos + jump - 1 == last || pos + jump == last || pos + jump + 1 == last) {
return true;
}
if (hs.contains(pos + jump + 1)) {
if (canReach(hs, last, pos + jump + 1, jump + 1)) {return true;}
}
if (hs.contains(pos + jump)) {
if (canReach(hs, last, pos + jump, jump)) {return true;}
}
if (jump > 1 && hs.contains(pos + jump - 1)) {
if (canReach(hs, last, pos + jump - 1, jump - 1)) {return true;}
}
return false;
}
Important facts (correct me if I'm wrong):
- Pre-check is necessary (otherwise Time Limit Exceed) : if (i > 0 && stones[i] - stones[i-1] > i) return false; Reason: when the answer if false, the time complexity of DFS will be exp, but pre-check will detect it before beginning DFS.
- During DFS, we should try to jump as far as we can cause this strategy is more likely to reach the destination. Therefore we should try unit+preStep+1 then unit+preStepand finally unit+preStep-1. If we try unit+preStep-1 first, it will be Time Limit Exceed.
public boolean canCross(int[] stones) {
if (stones[1] != 1) return false;
Set<Integer> units = new HashSet<>(); // stone locations
for (int i = 0; i < stones.length; i++) {
if (i > 0 && stones[i] - stones[i-1] > i) return false; // necessary!
units.add(stones[i]);
}
return cross(units, 1, 1, stones[stones.length-1]);
}
private boolean cross(Set<Integer> units, int unit, int preStep, int destination) {
if (preStep <= 0) return false;
if (!units.contains(unit)) return false;
if (unit == destination) return true;
if ( destination <= unit + preStep + 1 && destination >= unit + preStep - 1) return true;
return cross(units, unit+preStep+1, preStep+1, destination) ||
cross(units, unit+preStep, preStep, destination) ||
cross(units, unit+preStep-1, preStep-1, destination);
}
memo[i][j] = 1 means that the frog can reach the final destination from i-th stone, with j being the previous step size. Because the maximum previous step size for the 0th, 1th, 2th stone is 0, 1, 2, ... , which means the maximum j is equal to i. So we can declare the matrix size as n*n where n is the number of stones.
If ignoring the recursive call overhead, this algorithm should have a time complexity of O(n^2) because we are just filling half of this matrix memo.
public class Solution {
public boolean canCross(int[] stones) {
if(stones[1] != 1) return false;
int n = stones.length;
int[][] memo = new int[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++)
{
memo[i][j] = -1;
}
}
return canCross(stones, 0, 0, memo, n);
}
private boolean canCross(int[] stones, int i, int j, int[][] memo, int n) {
if(memo[i][j]!=-1) return memo[i][j] == 1;
if(i == n - 1) {
memo[i][j] = 1;
return true;
}
for(int k = i + 1; k < n; k++) {
if(stones[k] < j - 1 + stones[i]) continue;
else if(stones[k] > j + 1 + stones[i]) {
memo[i][j] = 0;
return false;
}
else {
if(canCross(stones, k, stones[k] - stones[i], memo, n)) {
memo[i][j] = 1;
return true;
}
}
}
memo[i][j] = 0;
return false;
}终于等到青蛙过河问题了，一颗赛艇。题目中说青蛙如果上一次跳了k距离，那么下一次只能跳k-1, k, 或k+1的距离，那么青蛙跳到某个石头上可能有多种跳法，由于这道题只是让我们判断青蛙是否能跳到最后一个石头上，并没有让我们返回所有的路径，这样就降低了一些难度。
我们可以用递归来做，我们维护一个哈希表，建立青蛙在pos位置和拥有jump跳跃能力时是否能跳到对岸。为了能用一个变量同时表示pos和jump，我们可以将jump左移很多位并或上pos，由于题目中对于位置大小有限制，所以不会产生冲突。我们还是首先判断pos是否已经到最后一个石头了，是的话直接返回true；然后看当前这种情况是否已经出现在哈希表中，是的话直接从哈希表中取结果。如果没有，我们就遍历余下的所有石头，对于遍历到的石头，我们计算到当前石头的距离dist，如果距离小于jump-1，我们接着遍历下一块石头；如果dist大于jump+1，说明无法跳到下一块石头，m[key]赋值为false，并返回false；如果在青蛙能跳到的范围中，我们调用递归函数，以新位置i为pos，距离dist为jump，如果返回true了，我们给m[key]赋值为true，并返回true。如果结束遍历我们给m[key]赋值为false，并返回false
bool canCross(vector<int>& stones) { unordered_map<int, bool> m; return helper(stones, 0, 0, m); } bool helper(vector<int>& stones, int pos, int jump, unordered_map<int, bool>& m) { int n = stones.size(), key = pos | jump << 11; if (pos >= n - 1) return true; if (m.count(key)) return m[key]; for (int i = pos + 1; i < n; ++i) { int dist = stones[i] - stones[pos]; if (dist < jump - 1) continue; if (dist > jump + 1) return m[key] = false; if (helper(stones, i, dist, m)) return m[key] = true; } return m[key] = false; }
https://discuss.leetcode.com/topic/59337/easy-version-java
public boolean canCross(int[] stones) {
if(stones[1] > 1) return false;
if(stones.length == 2) return true;
return helper(stones, 1, 1);
}
private boolean helper(int[] arr, int i, int step){
boolean pass = false;
if(i == arr.length-1) return true;
for(int j = i+1; j < arr.length; j++){
if(arr[j] <= arr[i] + step + 1 && arr[j] >= arr[i]+step-1){
pass = pass || helper(arr, j, arr[j] - arr[i]);
}
}
return pass;
}public boolean canCross(int[] stones) { int k = 0; return helper(stones, 0, k); } private boolean helper(int[] stones, int index, int k) { //目前已经达到了 if (index == stones.length - 1) return true; //选择k的步伐，范围k-1到k for (int i = k - 1; i <= k + 1; i++) { int nextJump = stones[index] + i; //看接下来有没有合适的石头可以跳过去，从接下来的位置中查找有没有nextJump的位置，有的话返回石头的编号 int nextPosition = Arrays.binarySearch(stones, index + 1, stones.length, nextJump); if (nextPosition > 0) { if (helper(stones, nextPosition, i)) return true; } } return false; }
http://xiadong.info/2016/09/leetcode-403-frog-jump/
虽然tag里说这是个DP题, 但是我觉得更像个图论题. 每个stone是一个node, 根据能否到达来判断有没有边相连, 最终要判断第一个节点与最后一个节点是否连通.
那么既然是这样, 就有DFS和BFS两派了. 用BFS的话要记录抵达每个node的上一跳可能有多远, 同时要记录一个node有没有访问过, 所以比较复杂.
bool canCross(vector<int>& stones) {
return canCrossImpl(stones, 0, 0);
}
bool canCrossImpl(vector<int>& stones, int index, int lastStep){
for(int i = index + 1; i < stones.size(); i++){
if(stones[i] - stones[index] < lastStep - 1) continue;
if(stones[i] - stones[index] > lastStep + 1) return false;
if(canCrossImpl(stones, i, stones[i] - stones[index])) return true;
}
return index == stones.size() - 1;
}
X. BFS
http://bookshadow.com/weblog/2016/09/18/leetcode-frog-jump/
利用元组(x, y)表示青蛙跳跃的状态：x表示位置, y表示上一跳的单元数。
初始将(0, 0)加入队列q，利用二维数组v记录元组(x, y)是否被访问过。
循环遍历队列q，根据队头状态扩展队列，直到队列为空。
def canCross(self, stones):
"""
:type stones: List[int]
:rtype: bool
"""
q = collections.deque()
v = collections.defaultdict(lambda : collections.defaultdict(bool))
stoneSet = set(stones)
q.append((0, 0))
v[0][0] = True
while q:
x, y = q.popleft()
if x == stones[-1]: return True
for z in (y - 1, y, y + 1):
if z > 0 and not v[x + z][z] and x + z in stoneSet:
v[x + z][z] = True
q.append((x + z, z))
return False由于这道题只是让我们判断青蛙是否能跳到最后一个石头上，并没有让我们返回所有的路径，这样就降低了一些难度
http://www.georgelyu.me/2016/09/18/7/
