[LintCode/LeetCode] Jump Game I & II

rose 发布于2019-08-14 15:27 / 1388人阅读

摘要：建立动规数组，表示从起点处到达该点的可能性。循环结束后，数组对所有点作为终点的可能性都进行了赋值。和的不同在于找到最少的步数。此时的一定是满足条件的最小的，所以一定是最优解。

Jump Game Problem

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Notice

This problem have two method which is Greedy and Dynamic Programming.

The time complexity of Greedy method is O(n).

The time complexity of Dynamic Programming method is O(n^2).

We manually set the small data set to allow you pass the test in both ways. This is just to let you learn how to use this problem in dynamic programming ways. If you finish it in dynamic programming ways, you can try greedy method to make it accept again.

Example

A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Note

建立动规boolean数组dp，表示从起点A[0]处到达该点的可能性。所以，起点的可能性dp[0] = true。
然后进行两次循环，令j < i，当dp[j]为true且j点可以到达i点时，dp[i]也为true。
循环结束后，dp数组对所有点作为终点的可能性都进行了赋值。返回数组A的终点dp[A.length-1]即可。

Solution

public class Solution {
    public boolean canJump(int[] A) {
        int n = A.length;
        boolean[] dp = new boolean[n];
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && j + A[j] >= i) dp[i] = true;
            }
        }
        return dp[n-1];
    }
}

Greedy

public class Solution {
    public boolean canJump(int[] A) {
        int n = A.length;
        if (n <= 1) return true;
        for (int i = n-2; i >= 0; i--) {
            if (A[i] == 0) {
                int need = 1;
                while (need > A[i]) {
                    need++;
                    i--;
                    if (i < 0) return false;
                }
            }
        }
        return true;
    }
}

Jump Game II Problem

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example

Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Note

和Jump Game I的不同在于找到最少的步数。这里有一个很巧妙的思想就是，i和j既然都是从起点开始遍历，每一个点i只要满足j + A[j] >= i，证明有解，就break出来。此时的j一定是满足条件的最小的j，所以dp[i] = dp[j] + 1一定是最优解。

Solution

public class Solution {
    public int jump(int[] A) {
        int n = A.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 0;
            for (int j = 0; j < i; j++) {
                if (j + A[j] >= i) {
                    dp[i] = dp[j]+1;
                    break;
                }
            }
        }
        return dp[n-1];
    }
}

Greedy

public class Solution {
    public int jump(int[] A) {
        int step = 0, lastMax = 0, curMax = 0;
        for (int i = 0; i < n-1; i++) {
            //Find the farthest point you can reach from current point
            curMax = Math.max(curMax, i+A[i]);
            //When reaching current step max distance
            //Add a new step; set the new step max distance to reach
            if (i == lastMax) {
                step++;
                lastMax = curMax;
            }
        }
        return step;
    }
}

GPU云服务器云服务器 II ii6 ii7 ii7中绑定域名

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

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

[LintCode/LeetCode] Subsets &amp; Subsets II

Subsets Problem Given a set of distinct integers, return all possible subsets. Notice Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets. Example ...

tracy 2019-08-14 14:26 评论0 收藏0
[LintCode/LeetCode] Single Number I &amp; II [位运算]

摘要：整个过程相当于，直接在和里去掉既是又是的。所以最后返回的，一定是只出现过一次的，而出现两次的都在里，出现三次的都被消去了。 Single Number I Problem Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return...

Drinkey 2019-08-14 15:33 评论0 收藏0
[LintCode/LeetCode] Combination Sum I &amp; II

摘要：和唯一的不同是组合中不能存在重复的元素，因此，在递归时将初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

ThreeWords 2019-08-14 15:23 评论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