## Wednesday, September 21, 2016

### LeetCode - 403 Frog Jump

https://leetcode.com/problems/frog-jump/
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

```    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;
}```

```    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<>());
}
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) {
if (step > 1) {
}
}
}
}
return false;
}```
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.

The time complexity is O(n2).
Slightly modified the example in the original post -
`[0 , 1, 3, 5, 6, 8, 10 ...]`
As more stones are added, the size of HashSet at each stone grows.
The list after the each stone represents the options for the next jump.
{0=[1], 1 = [1, 2], 3 = [1, 2, 3], 5 = [1, 2, 3], 6 = [1, 2, 3, 4], 8 = [1, 2, 3, 4 ], 10 = [1, 2, 3, 4, 5 ]... }
The size of HashSet at each stone won't be big than `n` (n is the total number of stones), since there is at most one way to directly jump from a previous stone to the current one.
``````    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>());
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) {
if (step - 1 > 0) set.add(step - 1);
}
}
}

return false;
} ``````
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.
``````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++)

Iterator<Integer> kSet;

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);
}
else if (j == stones.length-1||stones[j]-stones[i-1]-1>k)
{k=-1;j=i-1;}
j++;

}

}
return false;
}``````
https://discuss.leetcode.com/topic/59423/simple-easy-to-understand-java-solution
``````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]) {
}
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)) {
}
if(stoneMap.containsKey(eachStone + K + 1)) {
stoneMap.get(eachStone + K + 1).add(K + 1);
}
}
}
return stoneMap.get(stones[stones.length - 1]).size() >= 1;
}``````
https://discuss.leetcode.com/topic/61561/simple-and-easy-understand-java-solution
http://www.voidcn.com/blog/tc_to_top/article/p-6237336.html

```    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<>();
}
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)) {
}
}
}
}
return lastPos[len - 1].size() > 0;
}```
``````public boolean canCross(int[] stones)
if (stones == null || stones.length == 0) {
return false;
}
if (stones[1] > 1) {
return false;
}

Set[] lastJump = new Set[stones.length];
for (int i = 1; i < stones.length; i++) {
lastJump[i] = new HashSet<Integer>();
}

for (int i = 2; i < stones.length; i++) {
for (int j = 1; j < i; j++) {
//cell j can be reached
if (lastJump[j].size() > 0) {
int currJump = stones[i] - stones[j];
if (lastJump[j].contains(currJump) ||
lastJump[j].contains(currJump + 1) ||
lastJump[j].contains(currJump - 1)) {
}
}
}
}
return lastJump[stones.length - 1].size() > 0;
}``````

X. DFS
https://discuss.leetcode.com/topic/59439/straight-forward-9ms-7-line-c-solution-with-explanation
Search for the last stone in a depth-first way, prune those exceeding the [k-1,k+1] range. Well, I think the code is simple enough and need no more explanation.
``````bool canCross(vector<int>& stones, int pos = 0, int k = 0) {
for (int i = pos + 1; i < stones.size(); i++) {
int gap = stones[i] - stones[pos];
if (gap < k - 1) continue;
if (gap > k + 1) return false;
if (canCross(stones, i, gap)) return true;
}
return pos == stones.size() - 1;
}
``````
This can pass OJ at 9ms but is inefficient for extreme cases. (update: new test cases are added and the solution above no longer passes OJ, please see the solution below which takes 62ms) We can memorize the returns with minimum effort:
``````unordered_map<int, bool> dp;

bool canCross(vector<int>& stones, int pos = 0, int k = 0) {
int key = pos | k << 11;

if (dp.count(key) > 0)
return dp[key];

for (int i = pos + 1; i < stones.size(); i++) {
int gap = stones[i] - stones[pos];
if (gap < k - 1)
continue;
if (gap > k + 1)
return dp[key] = false;
if (canCross(stones, i, gap))
return dp[key] = true;
}

return dp[key] = (pos == stones.size() - 1);
}
``````
The number of stones is less than 1100 so pos will always be less than 2^11 (2048).
Stone positions could be theoretically up to 2^31 but k is practically not possible to be that big for the parameter as the steps must start from 0 and 1 and at the 1100th step the greatest valid k would be 1100. So combining pos and k is safe here.

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;
}``````
http://blog.csdn.net/mebiuw/article/details/52577052
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; }

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

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/