[leetcode] 403. Frog Jump

mo0n1andin 发布于2019-08-14 16:52 / 2540人阅读

摘要：还有一个石头可能由之前的多个石头到达，这又是可以优化的地方。当前结果可由之前的结果得出，且有重复的搜索方法，就需要用。

[链接描述]leetcode 题目。

有点类似于jump game，只不过这里对步数有了隐形的要求，当前步数和之前步数有关。
如果我们用brute force的方法来解，每一步有三种可能，一共n个石头，时间复杂度就是O(3^n)。
这其中有很多步数是多余的，第i个石头无法从任何一个石头到达，那么我们应该立即中止搜寻。
还有一个石头可能由之前的多个石头到达，这又是可以优化的地方。
当前结果可由之前的结果得出，且有重复的搜索方法，就需要用DP。

public class Solution {
    public boolean canCross(int[] stones) {
        if(stones[1] != 1) return false;
        int n = stones.length;
        int[][] dp = new int[n][n];     // for ith stones, j means maximun previous steps
        for(int i=0; i stones[i] + j + 1){    // too far
                dp[i][j] = 0;
                continue;
            } else {   // j-1, j, j+1 three possibility 
                if(canCross(dp, stones, k, stones[k] - stones[i], n)){
                    dp[i][j] = 1;
                    return true;
                }
            }
        }
        
        dp[i][j] = 0;
        return false;
    }
}

public class Solution {
    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;
        HashSet set = new HashSet<>();
        for(int i = 0; i < n; i++){
            if(i > 3 && stones[i] > stones[i-1]*2) return false;
            set.add(stones[i]);
        }
        
        return canCross(set, stones[n-1], 1, 1);
    }
    
    public boolean canCross(HashSet set, int last, int pos, int jump){
        if(pos + jump == last || pos + jump + 1 == last || pos + jump -1 == last){
            return true;
        }
        if(set.contains(pos + jump + 1)){
            if(canCross(set, last, pos+jump+1, jump+1)) return true;
        }
        if(set.contains(pos + jump)){
            if(canCross(set, last, pos+jump, jump)) return true;
        }
        if(jump > 1 && set.contains(pos + jump-1)){
            if(canCross(set, last, pos+jump-1, jump-1)) return true;
        }
        return false;
    }
}

云服务器 GPU云服务器 Frog Jump jump.php Leetcod

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66292.html

[LeetCode] 403. Frog Jump

Problem 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 li...

赵连江 2019-08-16 13:38 评论0 收藏0
leetcode403. Frog Jump

摘要：石头的位置用整数数组来表示。广度优先遍历可以从起点开始，对从该点出发的所有可能步数进行遍历，并更新从该点可达的点的所有的可行步数。利用数据结构来记录该结果，其中的为的数，它的对应的是从该出发的所有的上一步的步长。题目要求 A frog is crossing a river. The river is divided into x units and at each unit the...

Soarkey 2019-08-16 16:44 评论0 收藏0
leetcode45. Jump Game II

摘要：转换为广度优先算法即为我们只需要找到每一步的开始节点和结束下标，找到下一轮遍历的最大下标，如果该下标超过了数组长度，那么结束遍历，返回步数，否则将上一轮的最终节点加一作为起始节点，并将下一轮最大下标最为结束节点，继续遍历。题目要求 Given an array of non-negative integers, you are initially positioned at the ...

shiguibiao 2019-08-15 10:50 评论0 收藏0
LeetCode[45] Jump Game II

摘要：复杂度思路每次设置一个窗口，观察在这一步下能到达的最远距离，不断的移动这个窗口。计数，需要移动几次，才能覆盖到末尾的值。 LeetCode[45] Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array. Eac...

keelii 2019-08-14 15:02 评论0 收藏0
[LintCode/LeetCode] Jump Game I & II

摘要：建立动规数组，表示从起点处到达该点的可能性。循环结束后，数组对所有点作为终点的可能性都进行了赋值。和的不同在于找到最少的步数。此时的一定是满足条件的最小的，所以一定是最优解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...

rose 2019-08-14 15:27 评论0 收藏0