LeetCode[45] Jump Game II

keelii 發(fā)布于2019-08-14 15:02 / 2738人閱讀

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

LeetCode[45] Jump Game II

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.

For 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.)

復雜度
O(N^2), O(1)

思路
每次設置一個窗口，觀察在這一步下能到達的最遠距離，不斷的移動這個窗口。計數(shù)，需要移動幾次，才能覆蓋到末尾的值。

代碼

public int jump(int[] nums) {
    int cnt = 0, start = 0;
    int max = 0, prehigh = 0;
    while(max < nums.length - 1) {
        cnt ++;
        prehigh = max;
        for(int i = start; i <= prehigh; i ++) {
            max = Math.max(max, nums[i] + i);
        }
        start = prehigh + 1;
    }
    return cnt;
}

云服務器 GPU云服務器 Jump LeetCode jump.php LeetCode_String

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65250.html

leetcode45. Jump Game II

摘要：轉(zhuǎn)換為廣度優(yōu)先算法即為我們只需要找到每一步的開始節(jié)點和結束下標，找到下一輪遍歷的最大下標，如果該下標超過了數(shù)組長度，那么結束遍歷，返回步數(shù)，否則將上一輪的最終節(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
[LintCode/LeetCode] Jump Game I & II

摘要：建立動規(guī)數(shù)組，表示從起點處到達該點的可能性。循環(huán)結束后，數(shù)組對所有點作為終點的可能性都進行了賦值。和的不同在于找到最少的步數(shù)。此時的一定是滿足條件的最小的，所以一定是最優(yōu)解。 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
[Leetcode] Jump Game 跳躍游戲

摘要：代碼記錄下當前區(qū)域的上界，以便待會更新下一個區(qū)域的上界更新下一個區(qū)域的上界更新下一個區(qū)域的下界后續(xù)如果要求返回最短跳躍路徑，如何實現(xiàn)可以使用，并根據(jù)一個全局最短步數(shù)維護一個全局最短路徑，當搜索完所有可能后返回這個全局最短路徑。 Jump Game I 最新解法請見：https://yanjia.me/zh/2019/01/... Given an array of non-negat...

venmos 2019-08-14 12:24 評論0 收藏0
leetcode55 Jump Game

摘要：當前起點為數(shù)組中下標為零的位置，要走到數(shù)組的最后一個下標。其中，數(shù)組中每一個元素代表當前下標下可以前進的最大步數(shù)。如果最終的終點就是起始節(jié)點，那么肯定可以從其實節(jié)點找到一條路徑到達終點，否則失敗。題目要求 Given an array of non-negative integers, you are initially positioned at the first index o...

AlanKeene 2019-08-14 18:44 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區(qū)別...

tain335 2019-08-26 10:28 評論0 收藏0