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.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
題解：
輸入一個數(shù)組街氢，數(shù)組中的元素 nums[i] 表示可以從第 i 個位置最多向前跳躍 nums[i] 步，問對于輸入的數(shù)組nums，是否可以從數(shù)組的第0個位置跳躍到數(shù)組的最后一個位置襟雷。
例如：
A = [2,3,1,1,4], return true.
A[0] = 2; 表示可以從數(shù)組的第0個位置跳躍到第 （0+2） 個位置上；
A[1] = 3; 表示可以從數(shù)組的第1個位置跳躍到第 （1+3） 個位置上殿如；
A[2] = 1; 表示可以從數(shù)組的第2個位置跳躍到第 （2+1） 個位置上鸭蛙；
A[3] = 1; 表示可以從數(shù)組的第3個位置跳躍到第 （3+1） 個位置上；
A[4] = 4; 表示可以從數(shù)組的第4個位置跳躍到第 （4+4） 個位置上登下；
可以看出，數(shù)組中各位置所能跳躍到的最遠(yuǎn)的位置為：[2,4,3,4,8]叮喳；
當(dāng)我遍歷數(shù)組A時被芳，定義一個max_jump用來存儲截止到當(dāng)前位置之前所能跳躍的最大的步數(shù)，例如馍悟，截止到A[2]之前畔濒，我們所能跳躍到的最遠(yuǎn)的距離為 位置4 ；
當(dāng) max_jump < i 時锣咒，說明截止到位置 i 之前侵状，我們所能到達(dá)的最遠(yuǎn)位置max_jump 小于 當(dāng)前位置 i ，也就是說我們無法到達(dá)位置 i 毅整，返回false趣兄；
反正，說明我們能夠到達(dá)位置 i 悼嫉，那么就將 max_jump 更新為截止到 i 時我們所能到達(dá)的最遠(yuǎn)的位置艇潭；
若遍歷結(jié)束仍然沒有觸發(fā) false ，說明我們成功的到達(dá)了數(shù)組A的最后一個位置戏蔑，返回 true 蹋凝。
My Solution （C/C++完整實(shí)現(xiàn)）：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
bool canJump(vector<int> &nums) {
int max_jump = 0;
for (int i = 0; i < nums.size(); i++) {
if (i > max_jump) {
return false;
}
else {
max_jump = max(max_jump, nums[i] + i);
}
}
return true;
}
};
int main() {
vector<int> nums;
nums.push_back(2);
nums.push_back(3);
nums.push_back(1);
nums.push_back(1);
nums.push_back(4);
Solution s;
cout << s.canJump(nums);
return 0;
}
結(jié)果：
1
My Solution（Python）：
class Solution:
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
max_jump = nums[0]
for i in range(1, len(nums)):
if i <= max_jump:
max_jump = max(i+nums[i], max_jump)
else:
return False
return True
