C++實(shí)現(xiàn)LeetCode(55.跳躍游戲)
[LeetCode] 55. Jump Game 跳躍游戲
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.
Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.
這道題說的是有一個(gè)非負(fù)整數(shù)的數(shù)組,每個(gè)數(shù)字表示在當(dāng)前位置的最大跳力(這里的跳力指的是在當(dāng)前位置為基礎(chǔ)上能到達(dá)的最遠(yuǎn)位置),求判斷能不能到達(dá)最后一個(gè)位置,開始博主以為是必須剛好到達(dá)最后一個(gè)位置,超過了不算,其實(shí)是理解題意有誤,因?yàn)槊總€(gè)位置上的數(shù)字表示的是最大的跳力而不是像玩大富翁一樣搖骰子搖出幾一定要走幾。這里可以用動(dòng)態(tài)規(guī)劃 Dynamic Programming 來解,維護(hù)一個(gè)一維數(shù)組 dp,其中 dp[i] 表示達(dá)到i位置時(shí)剩余的跳力,若到達(dá)某個(gè)位置時(shí)跳力為負(fù)了,說明無法到達(dá)該位置。接下來難點(diǎn)就是推導(dǎo)狀態(tài)轉(zhuǎn)移方程啦,想想啊,到達(dá)當(dāng)前位置的剩余跳力跟什么有關(guān)呢,其實(shí)是跟上一個(gè)位置的剩余跳力(dp 值)和上一個(gè)位置新的跳力(nums 數(shù)組中的值)有關(guān),這里新的跳力就是原數(shù)組中每個(gè)位置的數(shù)字,因?yàn)槠浯砹艘援?dāng)前位置為起點(diǎn)能到達(dá)的最遠(yuǎn)位置。所以當(dāng)前位置的剩余跳力(dp 值)和當(dāng)前位置新的跳力中的較大那個(gè)數(shù)決定了當(dāng)前能到的最遠(yuǎn)距離,而下一個(gè)位置的剩余跳力(dp 值)就等于當(dāng)前的這個(gè)較大值減去1,因?yàn)樾枰ㄒ粋€(gè)跳力到達(dá)下一個(gè)位置,所以就有狀態(tài)轉(zhuǎn)移方程了:dp[i] = max(dp[i - 1], nums[i - 1]) - 1,如果當(dāng)某一個(gè)時(shí)刻 dp 數(shù)組的值為負(fù)了,說明無法抵達(dá)當(dāng)前位置,則直接返回 false,最后循環(huán)結(jié)束后直接返回 true 即可,參見代碼如下:
解法一:
class Solution { public: bool canJump(vector<int>& nums) { vector<int> dp(nums.size(), 0); for (int i = 1; i < nums.size(); ++i) { dp[i] = max(dp[i - 1], nums[i - 1]) - 1; if (dp[i] < 0) return false; } return true; } };
其實(shí)這題最好的解法不是 DP,而是貪婪算法 Greedy Algorithm,因?yàn)檫@里并不是很關(guān)心每一個(gè)位置上的剩余步數(shù),而只希望知道能否到達(dá)末尾,也就是說我們只對(duì)最遠(yuǎn)能到達(dá)的位置感興趣,所以維護(hù)一個(gè)變量 reach,表示最遠(yuǎn)能到達(dá)的位置,初始化為0。遍歷數(shù)組中每一個(gè)數(shù)字,如果當(dāng)前坐標(biāo)大于 reach 或者 reach 已經(jīng)抵達(dá)最后一個(gè)位置則跳出循環(huán),否則就更新 reach 的值為其和 i + nums[i] 中的較大值,其中 i + nums[i] 表示當(dāng)前位置能到達(dá)的最大位置,參見代碼如下:
解法二:
class Solution { public: bool canJump(vector<int>& nums) { int n = nums.size(), reach = 0; for (int i = 0; i < n; ++i) { if (i > reach || reach >= n - 1) break; reach = max(reach, i + nums[i]); } return reach >= n - 1; } };
到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(55.跳躍游戲)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)跳躍游戲內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- C++實(shí)現(xiàn)LeetCode(16.最近三數(shù)之和)
- C++實(shí)現(xiàn)LeetCode(14.最長(zhǎng)共同前綴)
- C++實(shí)現(xiàn)LeetCode(13.羅馬數(shù)字轉(zhuǎn)化成整數(shù))
- C++實(shí)現(xiàn)LeetCode(12.整數(shù)轉(zhuǎn)化成羅馬數(shù)字)
- C++實(shí)現(xiàn)LeetCode(45.跳躍游戲之二)
- C++實(shí)現(xiàn)LeetCode(769.可排序的最大塊數(shù))
- C++實(shí)現(xiàn)LeetCode(23.合并k個(gè)有序鏈表)
相關(guān)文章
C語言數(shù)據(jù)結(jié)構(gòu)之鏈隊(duì)列的基本操作
這篇文章主要為大家介紹了C語言之鏈隊(duì)列的基本操作,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助2021-12-12Matlab制作視頻并轉(zhuǎn)換成gif動(dòng)態(tài)圖的兩種方法
這篇文章主要介紹了Matlab制作視頻并轉(zhuǎn)換成gif動(dòng)態(tài)圖的兩種方法,第一種方法使用movie(f)直接取生成AVI視頻文件,相對(duì)來說比較簡(jiǎn)單,需要的朋友可以參考下2018-08-08Visual?Studio2022報(bào)錯(cuò)無法打開源文件?"openssl/conf.h"解決方法
這篇文章主要介紹了Visual?Studio2022報(bào)錯(cuò)無法打開源文件"openssl/conf.h"解決方式,本文通過圖文并茂的形式給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-07-07C語言將24小時(shí)制轉(zhuǎn)換為12小時(shí)制的方法
這篇文章主要介紹了C語言將24小時(shí)制轉(zhuǎn)換為12小時(shí)制的方法,涉及C語言針對(duì)時(shí)間的相關(guān)操作技巧,非常簡(jiǎn)單實(shí)用,需要的朋友可以參考下2015-07-07C++中volatile和mutable關(guān)鍵字用法詳解
這篇文章主要介紹了C++中volatile和mutable關(guān)鍵字用法詳解,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02C++實(shí)現(xiàn)簡(jiǎn)單猜數(shù)字小游戲
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡(jiǎn)單猜數(shù)字小游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-01-01