[[387128]]

前言

周五了，和大家玩?zhèn)€跳躍游戲

題目

給定一個(gè)非負(fù)整數(shù)數(shù)組 nums ，你最初位于數(shù)組的 第一個(gè)下標(biāo) 。

數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度。

判斷你是否能夠到達(dá)最后一個(gè)下標(biāo)。

示例 1：輸入：nums = [2,3,1,1,4] 輸出：true

解釋?zhuān)嚎梢韵忍?1 步，從下標(biāo) 0 到達(dá)下標(biāo) 1, 然后再?gòu)南聵?biāo) 1 跳 3 步到達(dá)最后一個(gè)下標(biāo)。

示例 2：輸入：nums = [3,2,1,0,4] 輸出：false

解釋?zhuān)簾o(wú)論怎樣，總會(huì)到達(dá)下標(biāo)為 3 的位置。但該下標(biāo)的最大跳躍長(zhǎng)度是 0 ， 所以永遠(yuǎn)不可能到達(dá)最后一個(gè)下標(biāo)。

分析

簡(jiǎn)單分析一下，由題目得出，要想到達(dá)最后一個(gè)下標(biāo)，得滿(mǎn)足兩個(gè)條件：

• 1、假設(shè)每個(gè)位置都能跳到，那么我們只需要遍歷數(shù)組，看看有沒(méi)有位置能直接通過(guò)這個(gè)位置上的數(shù)字跳到結(jié)尾。

比如[2,3,2,1,4]，我們遍歷數(shù)字，看看哪個(gè)位置可以跳到最后，可以發(fā)現(xiàn)第三個(gè)位置的數(shù)字是2，所以可以通過(guò)第三個(gè)位置跳到最后的下標(biāo)，數(shù)組成立。

• 2、上述假設(shè)成立的還有個(gè)條件就是 每個(gè)位置是否都能跳到。

比如[2,0,2,1,4]，按照上面的邏輯，第三個(gè)位置是可以跳到最后下標(biāo)。但是，第三個(gè)位置是否能到達(dá)呢?如果第三個(gè)位置都到不了，那又何談最后的位置呢?在這個(gè)例子中，第一個(gè)位置為2，是可以跳到第三個(gè)位置的。

如果改成[1,0,2,1,4]，第三個(gè)位置就到不了了。

結(jié)合上述分析，我們可以得出以下解法：

public boolean canJump(int[] nums) { 
        //能到達(dá)的最大位置k 
        int k =0; 
        //遍歷數(shù)組 
        for(int i=0;i<nums.length;i++){ 
            //如果達(dá)不到i位置，就直接返回false 
            if(k<i) return false; 
            k=Math.max(k,i+nums[i]); 
        } 
        return true; 
    } 

也可以在每次獲取k之后再判斷一次，如果滿(mǎn)足條件就直接返回，減少循環(huán)次數(shù)：

public boolean canJump(int[] nums) { 
        //能到達(dá)的最大位置k 
        int k =0; 
        //獲取數(shù)組長(zhǎng)度 
        int l = nums.length; 
        //遍歷數(shù)組 
        for(int i=0;i<l;i++){ 
            if(k<i) return false; 
            k=Math.max(k,i+nums[i]); 
            if (k >= l-1) { 
             return true; 
            } 
        } 
        return false; 
    } 

這種在到了某個(gè)位置，作出當(dāng)前最好的選擇 的算法一般稱(chēng)為貪心算法。

貪心算法的思路就是把問(wèn)題分為若干個(gè)子問(wèn)題，然后針對(duì)每個(gè)子問(wèn)題進(jìn)行局部求解，最終得到整個(gè)問(wèn)題的解。

貪心算法主要有兩個(gè)特點(diǎn)：

• 總是作出在當(dāng)前看來(lái)最好的選擇。
• 從局部的最優(yōu)選擇到整體最優(yōu)解。

所以“貪心”的意思大概就是目光短淺，只看到到眼前的最好，而不會(huì)從整體的角度思考。

雖然不能保證最后的解法是最優(yōu)的，但是這種辦法確實(shí)是能夠解決問(wèn)題的，將大問(wèn)題化解成小問(wèn)題，小問(wèn)題好好解決。

那有什么時(shí)候會(huì)有更好的解呢?這就引出 動(dòng)態(tài)規(guī)劃了。

動(dòng)態(tài)規(guī)劃的思想同樣是解決子問(wèn)題，但是每一步的選擇都會(huì)依賴(lài)于相關(guān)的子問(wèn)題解，所以有時(shí)候的復(fù)雜問(wèn)題選擇動(dòng)態(tài)規(guī)劃能有更好的解法，因?yàn)樗麑?duì)于子問(wèn)題間的相關(guān)性更強(qiáng)。

就等下次聊了，拜拜。

時(shí)間復(fù)雜度

O(n)

空間復(fù)雜度

O(1)

參考

https://blog.csdn.net/qq_42363032/article/details/103597453

https://leetcode-cn.com/problems/jump-game/submissions/

本文轉(zhuǎn)載自微信公眾號(hào)「碼上積木」，作者積木zz 。轉(zhuǎn)載本文請(qǐng)聯(lián)系碼上積木公眾號(hào)。