題目描述：來自LeetCode
方法一：
思路： 基于貪心的思想，我們可以計算每一個可以到達的位置所能到達的最遠的距離，并不斷更新這個最遠距離，因為可以選擇走的更遠的我們當然不選擇近的啦，(可以將陣列長度想象成一段路程，陣列上的點代表加油站，每一個值代表在該加油站加完油后可以行駛的最遠距離，如果在這個加油站加完油之后可以走更遠，我們就加油，如果不能，我們當然不加了，并且選擇在該加油站加油的前提條件是能到達該加油站，不然....怎么加）如果最遠距離大于等于陣列長度，則回傳true，否則回傳false，
故1.判斷遍歷到的第i個點是否可達 i<=可以到達的最遠距離 2.第i個點可以到達的最遠距離i+nums[i]
代碼實作C++:
class Solution {
public:
bool canJump(vector<int>& nums) {
int n=nums.size();
if(n==0) return true;
int far=0;
for(int i=0;i<n;i++){
if(i<=far){
far=max(far,i+nums[i]);
}
if(far>=n-1) return true;
}
return false;
}
};方法二：
從后往前遍歷陣列，如果該位置可以到達最后，我們就視為從當前位置到最后一個元素不存在，將當前位置看做終點，繼續往前遍歷，因為只要能到達當前位置，就一定能到達陣列的最后一位，在第n-2這個位置開始，它能到達終點即n-1的條件就是，nums[n-2]>=1,如果不能到達我們就保留該位置到最后的元素，（即終點不變)，那么n-3能到達終點的條件是什么呢？n-3只能直接到達終點，因為n-2到n-1是不可達的，故nums[n-3]>=2,同理，當n-3也不可達n-1，在判斷n-4的時候，就必須是nums[n-4]>=3,可以發現，只要第i個元素后面的元素有一個不可到達終點，我們判斷第i個元素是否可達第終點的條件就要加上一，如果可達，那第i個元素就變成終點，前面的元素只要能到就能到達終點，故條件又從是否大于一開始判斷，在遍歷結束，如果n==1就說明可達，否則說明不可達
代碼實作c++:
class Solution {
public:
bool canJump(vector<int>& nums) {
int m=nums.size();
if(m==0) return true;
int n=1;
for(int i=m-2;i>=0;i--){
if(nums[i]>=n){//當該位置可以到達終點時，該位置變成終點，修改下一個元素到達終點的條件
n=1;
}else{//當該位置不可以到達終點時，將下一個位置到達終點的判斷條件加一
n++;
}
if(i==0&&n>1) return false;//如果最后到達終點的條件（其實也是元素個數）大于1，說明不可達
}
return true;
}
};今日刷題任務完成~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/317689.html
標籤：其他