55. 跳躍游戲
題目：
給定一個非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個位置。

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

判斷你是否能夠到達(dá)最后一個位置。

示例 1:輸入: [2,3,1,1,4] 輸出: true 解釋: 我們可以先跳 1 步，從位置 0 到達(dá) 位置 1, 然后再從位置 1 跳 3 步到達(dá)最后一個位置。 示例 2:輸入: [3,2,1,0,4] 輸出: false 解釋: 無論怎樣，你總會到達(dá)索引為 3 的位置。但該位置的最大跳躍長度是 0 ， 所以你永遠(yuǎn)不可能到達(dá)最后一個位置。

解題思路：

貪心算法，如果我跳的這一步能走得更遠(yuǎn)，那么我就走這一步 。

那么怎么才能知道哪一步走得更遠(yuǎn)呢?我們直接用一個新的數(shù)組來記錄每一個位置下一次能夠跳的最遠(yuǎn)的位置的下標(biāo)。即=i+nums[i]

那么只要遍歷新的數(shù)組，如果能夠跳的最遠(yuǎn)的位置比此時此刻的下標(biāo)大就行了，如果小，就直接退出。

最好判斷跳的位置

代碼：

class Solution { public:bool canJump(vector<int>& nums) {vector<int> index;for(int i=0;i<nums.size();i++){index.push_back(i+nums[i]);}int jump=0;int max=index[0];while(jump<index.size()&&jump<=max){if(max<index[jump]){max=index[jump];}jump++;}if(jump==index.size()) return true;return false;} };

需要注意的地方：
1.jump<index.size()&&jump<=max

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的LeetCode 55. 跳跃游戏 中等难度的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。