^{<blockquote id="4e3q0"></blockquote>}

LeetCode[45] Jump Game II

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

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

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

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

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

代碼

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

云服務(wù)器 GPU云服務(wù)器 Jump LeetCode jump.php LeetCode_String

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

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

相關(guān)文章

leetcode45. Jump Game II

摘要：轉(zhuǎn)換為廣度優(yōu)先算法即為我們只需要找到每一步的開始節(jié)點(diǎn)和結(jié)束下標(biāo)，找到下一輪遍歷的最大下標(biāo)，如果該下標(biāo)超過了數(shù)組長度，那么結(jié)束遍歷，返回步數(shù)，否則將上一輪的最終節(jié)點(diǎn)加一作為起始節(jié)點(diǎn)，并將下一輪最大下標(biāo)最為結(jié)束節(jié)點(diǎn)，繼續(xù)遍歷。題目要求 Given an array of non-negative integers, you are initially positioned at the ...

shiguibiao 2019-08-15 10:50 評(píng)論0 收藏0
[LintCode/LeetCode] Jump Game I & II

摘要：建立動(dòng)規(guī)數(shù)組，表示從起點(diǎn)處到達(dá)該點(diǎn)的可能性。循環(huán)結(jié)束后，數(shù)組對所有點(diǎn)作為終點(diǎn)的可能性都進(jì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 評(píng)論0 收藏0
[Leetcode] Jump Game 跳躍游戲

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

venmos 2019-08-14 12:24 評(píng)論0 收藏0
leetcode55 Jump Game

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

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

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 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 評(píng)論0 收藏0