LeetCode題目鏈接鏈接
https://leetcode-cn.com/problems/jump-game/
給定一個非負(fù)整數(shù)數(shù)組脚作，你最初位于數(shù)組的第一個位置。
數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度碎乃。
判斷你是否能夠到達(dá)最后一個位置姊扔。
示例?1:
輸入:[2,3,1,1,4]輸出:true解釋:從位置 0 到 1 跳 1 步, 然后跳 3 步到達(dá)最后一個位置。
示例?2:
輸入:[3,2,1,0,4]輸出:false解釋:無論怎樣梅誓，你總會到達(dá)索引為 3 的位置。但該位置的最大跳躍長度是 0 ， 所以你永遠(yuǎn)不可能到達(dá)最后一個位置梗掰。
解題思路
剛開始做嵌言。并不是很會。參考了別人的代碼及穗，加入自己的理解
注意摧茴，題目中說的是每個元素代表你在該位置可以跳躍的最大長度。加入該元素為3埂陆，則它可以跳躍0,1,2,3個長度
從后往前遍歷苛白。假定數(shù)組為[2,3,1,1,4]。
class Solution {
? ? public boolean canJump(int[] nums) {
? ? //該位置至少跳躍多少長度才能到最后一個
? ? ? ? int len = 1;
? ? ? ?// 從后往前遍歷
? ? ? ? for(int i=nums.length-2;i>=0;i--){
? ? // 如果該位置可以跳躍的大小大于len焚虱，表示該位置可以到達(dá)數(shù)組最后一位
? ? //? len還原為1? 原因： 假設(shè)當(dāng)前i為2购裙，nums[i] =? 1? 因?yàn)?1 >=1 所以下一個循環(huán)只要能跳到nums[2]就可以了。??
? ? ? ? ? ? if(nums[i] >= len) {
? ? ? ? ? ? ? ? len = 1;
? ? ? ? ? ? }else {
//? len++? 原因：如果無法跳遠(yuǎn)到鹃栽，則下一個循環(huán)至少要多條一個長度
? ? ? ? ? ? ? ? len++;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return len == 1;
? ? }
}
