LeetCode[45] Jump Game II

keelii 發布于2019-08-14 15:02 / 2727人閱讀

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

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)

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

代碼

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65250.html

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
[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
[Leetcode] Jump Game 跳躍游戲

摘要：代碼記錄下當前區域的上界，以便待會更新下一個區域的上界更新下一個區域的上界更新下一個區域的下界后續如果要求返回最短跳躍路徑，如何實現可以使用，并根據一個全局最短步數維護一個全局最短路徑，當搜索完所有可能后返回這個全局最短路徑。 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

摘要：當前起點為數組中下標為零的位置，要走到數組的最后一個下標。其中，數組中每一個元素代表當前下標下可以前進的最大步數。如果最終的終點就是起始節點，那么肯定可以從其實節點找到一條路徑到達終點，否則失敗。題目要求 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 題攻略）

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

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