[LintCode/LeetCode] Jump Game I & II

rose 發(fā)布于2019-08-14 15:27 / 1466人閱讀

摘要：建立動規(guī)數(shù)組，表示從起點處到達該點的可能性。循環(huán)結(jié)束后，數(shù)組對所有點作為終點的可能性都進行了賦值。和的不同在于找到最少的步數(shù)。此時的一定是滿足條件的最小的，所以一定是最優(yōu)解。

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

建立動規(guī)boolean數(shù)組dp，表示從起點A[0]處到達該點的可能性。所以，起點的可能性dp[0] = true。
然后進行兩次循環(huán)，令j < i，當dp[j]為true且j點可以到達i點時，dp[i]也為true。
循環(huán)結(jié)束后，dp數(shù)組對所有點作為終點的可能性都進行了賦值。返回數(shù)組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的不同在于找到最少的步數(shù)。這里有一個很巧妙的思想就是，i和j既然都是從起點開始遍歷，每一個點i只要滿足j + A[j] >= i，證明有解，就break出來。此時的j一定是滿足條件的最小的j，所以dp[i] = dp[j] + 1一定是最優(yōu)解。

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中綁定域名

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/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 [位運算]

摘要：整個過程相當于，直接在和里去掉既是又是的。所以最后返回的，一定是只出現(xiàn)過一次的，而出現(xiàn)兩次的都在里，出現(xiàn)三次的都被消去了。 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

摘要：轉(zhuǎn)換為廣度優(yōu)先算法即為我們只需要找到每一步的開始節(jié)點和結(jié)束下標，找到下一輪遍歷的最大下標，如果該下標超過了數(shù)組長度，那么結(jié)束遍歷，返回步數(shù)，否則將上一輪的最終節(jié)點加一作為起始節(jié)點，并將下一輪最大下標最為結(jié)束節(jié)點，繼續(xù)遍歷。題目要求 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

摘要：復雜度思路每次設置一個窗口，觀察在這一步下能到達的最遠距離，不斷的移動這個窗口。計數(shù)，需要移動幾次，才能覆蓋到末尾的值。 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