南京專業(yè)網(wǎng)站建設(shè)整合營銷傳播的概念
給你一個(gè)非負(fù)整數(shù)數(shù)組?nums
?,你最初位于數(shù)組的?第一個(gè)下標(biāo)?。數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達(dá)最后一個(gè)下標(biāo),如果可以,返回?true
?;否則,返回?false
?。
示例?1:
輸入:nums = [2,3,1,1,4] 輸出:true 解釋:可以先跳 1 步,從下標(biāo) 0 到達(dá)下標(biāo) 1, 然后再從下標(biāo) 1 跳 3 步到達(dá)最后一個(gè)下標(biāo)。
示例?2:
輸入:nums = [3,2,1,0,4] 輸出:false 解釋:無論怎樣,總會(huì)到達(dá)下標(biāo)為 3 的位置。但該下標(biāo)的最大跳躍長度是 0 , 所以永遠(yuǎn)不可能到達(dá)最后一個(gè)下標(biāo)。
>>思路和分析
示例1中,若站在元素3的位置,我究竟是跳一步還是跳兩步,還是跳三步呢??因?yàn)檫@是至多跳三步,那我究竟跳幾步呢?然后我跳到下一個(gè)元素我又究竟要跳幾步呢?能否跳到終點(diǎn)呢?
如果沿著這個(gè)思路去想,那本題就很難想出來了。其實(shí)可以換一個(gè)維度,不去糾結(jié)于在數(shù)組中得到一個(gè)元素往后具體去跳幾步,我們只看覆蓋范圍。也就是說,在一開始站在起始位置,往后的覆蓋范圍就是覆蓋了兩步,然后站在元素3這個(gè)位置,往后的覆蓋范圍就是三步的覆蓋范圍。那么最終就把終點(diǎn)給覆蓋了。
只要在覆蓋范圍內(nèi),那任何一個(gè)元素的下標(biāo)位置,都可以跳到,別管我是跳幾步,別管我是怎么跳的,我就是可以跳過來。那么這個(gè)問題就轉(zhuǎn)化為跳躍覆蓋范圍究竟可不可以覆蓋終點(diǎn)!
核心:怎么跳躍不重要,關(guān)鍵在覆蓋范圍
思路:每次移動(dòng)取最大跳躍步數(shù)(得到最大的覆蓋范圍),每移動(dòng)一個(gè)單位,就更新最大覆蓋范圍
>>貪心算法
- 局部最優(yōu)解:每次取最大跳躍步數(shù)(取最大覆蓋范圍)
- 整體最優(yōu)解:最后得到整體最大覆蓋范圍,看是否能到終點(diǎn)
局部最優(yōu)推出全局最優(yōu),找不到反例,試試貪心!
C++代碼:
class Solution {
public:bool canJump(vector<int>& nums) {int cover = 0;if (nums.size() == 1) return true; // 只有一個(gè)元素,就是能達(dá)到for (int i = 0; i <= cover; i++) { // 注意這里是小于等于covercover = max(i + nums[i], cover);if (cover >= nums.size() - 1) return true; // 說明可以覆蓋到終點(diǎn)了}return false;}
};
- 時(shí)間復(fù)雜度: O(n)
- 空間復(fù)雜度: O(1)
參考和推薦文章、視頻
?代碼隨想錄 (programmercarl.com)
?貪心算法,怎么跳躍不重要,關(guān)鍵在覆蓋范圍 | LeetCode:55.跳躍游戲_嗶哩嗶哩_bilibili
來自代碼隨想錄的課堂截圖: