55.?跳躍游戲

?

給定一個非負整數數組，你最初位于數組的第一個位置。

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

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

示例?1:

輸入: [2,3,1,1,4] 輸出: true 解釋: 從位置 0 到 1 跳 1 步, 然后跳 3 步到達最后一個位置。

示例?2:

輸入: [3,2,1,0,4] 輸出: false 解釋: 無論怎樣，你總會到達索引為 3 的位置。但該位置的最大跳躍長度是 0 ， 所以你永遠不可能到達最后一個位置。

解法1：

貪心，遍歷所有的元素，維護的指標為當前能夠達到的最大值，該最大值由上一次跳躍的最大值和這次跳躍的距離取較大值

一定要遍歷所有的元素，而不是跳躍

maxreach的更新方法：max（上一次跳躍的最大值，本次跳躍的最大距離）

#include<bits/stdc++.h> using namespace std; class Solution { public:bool canJump(vector<int>& nums) {int N=nums.size();int maxreach=0;//注意是下標值而不是元素值for(int i=0;i<N;i++){//maxreach停止了，i仍然在增加if(i>maxreach)return false;maxreach=max(maxreach,i+nums[i]);//更新if(maxreach>=N-1)return true;}}//bool }; int main(){int n;cin>>n;vector<int>a;for(int i=0;i<n;i++){int x;cin>>x;a.push_back(x);}Solution work;if(work.canJump(a))cout<<"true"<<endl;elsecout<<"false"<<endl; } /* 2 3 1 1 4 3 2 1 0 4 3 0 8 2 0 0 7 */

解法2

由于數組元素大于等于0，所以當且僅當數組中有0，才可能過不去；其他情況一定可以跳到終點。

因此找到數組中的0元素，對于每一個0元素，查看其是否可以過去；

重點：不能過去的充要條件是：0元素之前所有元素的值不大于該元素與0元素的距離

#include<bits/stdc++.h> using namespace std; class Solution { public:bool canJump(vector<int>& nums) {int N=nums.size();if(N<=1) return true;if(nums[0]==0) return false;//點數N>1,不可能跳到終點for(int i=1;i!=N-1;i++){//遍歷:第2個點到倒數第2個點if(nums[i]==0){vector<int>subnums(nums.begin(),nums.begin()+i);if(!jumpZERO(subnums))return false;}}return true;}//bool private:bool jumpZERO(vector<int>& subnums){vector<int>::iterator it;for(it=subnums.begin();it!=subnums.end();it++){//當前點可以跳到末尾0，就可以通過if(*it>(subnums.end()-it))return true;}return false;} }; int main(){int n;cin>>n;vector<int>a;for(int i=0;i<n;i++){int x;cin>>x;a.push_back(x);}Solution work;if(work.canJump(a))cout<<"true"<<endl;elsecout<<"false"<<endl; } /* 2 3 1 1 4 3 2 1 0 4 3 0 8 2 0 0 7 */

45.?跳躍游戲 II

?

給定一個非負整數數組，你最初位于數組的第一個位置。

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

你的目標是使用最少的跳躍次數到達數組的最后一個位置。

示例:

輸入: [2,3,1,1,4] 輸出: 2 解釋: 跳到最后一個位置的最小跳躍數是 2。從下標為 0 跳到下標為 1 的位置，跳?1步，然后跳?3 步到達數組的最后一個位置。

這道題的要求是給定一整數數組，數組元素表示每次可以跳躍的最大距離。然后初始位置在數組的第一個元素，目的是以最少的步數到達最后元素。

這道題是Jump Game II，是其Jump Game的擴展。

在Jump Game中，采用貪心的思路，采用reach變量維護能到達最遠處，即為全局最優解。當遍歷到i的時候，局部最優解為A[i]+i，因此，此時的全局最優解即為reach和A[i]+i的最大值：reach = max(reach, A[i] + i)。

而這道題，需要求的是最少的步數。因此需要添加step變量記錄最少步數。至于什么時候step需要加1？答案是當前的i超過了前一步的最遠位置。所以引入last變量記錄上一步能到達的最遠位置。reach、step、last的初始值均為0。當遍歷到i的時候，如果i超過了last（即上一步能到達的最遠位置），說明步數需要加1（即step++），此時仍需要更新last為當前最遠位置reach。全程只需遍歷1次數組，而且空間復雜度為常量。

時間復雜度：O(n)

空間復雜度：O(1)

class Solution { public:int jump(vector<int>& nums) {int n=nums.size();int reach=0;int step=0;int last=0;//上一步能達到的最遠位置for(int i=0;i<=reach&&i<n;i++){if(i>last){++step;last=reach;}reach=max(reach,nums[i]+i);}return reach>=n-1?step:0;} };

?

總結

以上是生活随笔為你收集整理的【LeetCode 55】【LeetCode 45】 跳跃游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。