成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

[Leetcode] Jump Game 跳躍游戲

venmos / 1880人閱讀

摘要：代碼記錄下當(dāng)前區(qū)域的上界，以便待會更新下一個區(qū)域的上界更新下一個區(qū)域的上界更新下一個區(qū)域的下界后續(xù)如果要求返回最短跳躍路徑，如何實(shí)現(xiàn)可以使用，并根據(jù)一個全局最短步數(shù)維護(hù)一個全局最短路徑，當(dāng)搜索完所有可能后返回這個全局最短路徑。

Jump Game I 最新解法請見：https://yanjia.me/zh/2019/01/... 
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.


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


A = [3,2,1,0,4], return false.
貪心法 復(fù)雜度

時間 O(N) 空間 O(1)

思路

如果只是判斷能否跳到終點(diǎn)，我們只要在遍歷數(shù)組的過程中，更新每個點(diǎn)能跳到最遠(yuǎn)的范圍就行了，如果最后這個范圍大于等于終點(diǎn)，就是可以跳到。

代碼 
public class Solution {
    public boolean canJump(int[] nums) {
        int max = 0, i = 0;
        for(i = 0; i <= max && i < nums.length; i++){
            max = Math.max(max, nums[i] + i);
        }
        return i == nums.length;
    }
}
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) 空間 O(1)

思路

如果要計(jì)算最短的步數(shù)，就不能貪心每次都找最遠(yuǎn)距離了，因?yàn)橛锌赡芤婚_始跳的遠(yuǎn)的路徑，后面反而更慢。所以我們要探索所有的可能性，這里用快慢指針分出一塊當(dāng)前結(jié)點(diǎn)能跳的一塊區(qū)域，然后再對這塊區(qū)域遍歷，找出這塊區(qū)域能跳到的下一塊區(qū)域的上下邊界，每塊區(qū)域都對應(yīng)一步，直到上界超過終點(diǎn)時為之。

代碼 
public class Solution {
    public int jump(int[] nums) {
        int high = 0, low = 0, preHigh = 0, step = 0;
        while(high < nums.length - 1){
            step++;
            //記錄下當(dāng)前區(qū)域的上界，以便待會更新下一個區(qū)域的上界
            preHigh = high;
            for(int i = low; i <= preHigh; i++){
                //更新下一個區(qū)域的上界
                high = Math.max(high, i + nums[i]);
            }
            //更新下一個區(qū)域的下界
            low = preHigh + 1;
        }
        return step;
    }
}
后續(xù) Follow Up

Q：如果要求返回最短跳躍路徑，如何實(shí)現(xiàn)？
A：可以使用DFS，并根據(jù)一個全局最短步數(shù)維護(hù)一個全局最短路徑，當(dāng)搜索完所有可能后返回這個全局最短路徑。

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

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/64453.html

相關(guān)文章

  • Chrome 小恐龍游戲源碼探究八 -- 奔跑的小恐龍

    摘要：例如，將函數(shù)修改為小恐龍眨眼這樣小恐龍會不停的眨眼睛。小恐龍的開場動畫下面來實(shí)現(xiàn)小恐龍對鍵盤按鍵的響應(yīng)。接下來還需要更新動畫幀才能實(shí)現(xiàn)小恐龍的奔跑動畫。 文章首發(fā)于我的 GitHub 博客 前言 上一篇文章：《Chrome 小恐龍游戲源碼探究七 -- 晝夜模式交替》實(shí)現(xiàn)了游戲晝夜模式的交替，這一篇文章中，將實(shí)現(xiàn)：1、小恐龍的繪制 2、鍵盤對小恐龍的控制 3、頁面失焦后，重新聚焦會重置...

    paulquei 評論0 收藏0

  • 揭密微信跳一跳小游戲那些外掛

    摘要：所以，我們這個小游戲發(fā)布以后，我們就開始花了很多很多時間來打擊外掛。二距離判斷像素點(diǎn)判斷該方法采用自目前最火的跳一跳小游戲輔助程序。 作者：Hahn， 騰訊高級UI工程師商業(yè)轉(zhuǎn)載請聯(lián)系騰訊WeTest獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。 原文鏈接：http://wetest.qq.com/lab/view/364.html WeTest 導(dǎo)讀 張小龍：這個游戲發(fā)布以后，其實(shí)它的效果有點(diǎn)超...

    lyning 評論0 收藏0

  • 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 評論0 收藏0

  • LeetCode[45] Jump Game II

    摘要：復(fù)雜度思路每次設(shè)置一個窗口，觀察在這一步下能到達(dá)的最遠(yuǎn)距離，不斷的移動這個窗口。計(jì)數(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 評論0 收藏0

發(fā)表評論

0條評論

venmos

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<