LeetCode Jump Game

LeetCode 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.


给定一个数组,每个数字A[i]表示站在i位置最多能跳的步数,初始时站在数组左边,问能否跳到数组右边。

使用贪心策略,维护一个当前能跳到的最远位置maxpos。从左往右遍历数组,如果位置i>maxpos,说明根据之前的数字,没办法跳到位置i,直接break;否则更新maxpos为max(maxpos,A[i]+i)。最后检查maxpos>=n-1。完整代码如下:

class Solution {
public:
	bool canJump(vector<int>& nums) {
		int maxpos = 0;
		for (int i = 0; i < nums.size(); ++i) {
			if (i > maxpos)break;
			maxpos = max(maxpos, i + nums[i]);
		}
		return maxpos >= nums.size() - 1;
	}
};

本代码提交AC,用时12MS。

One thought on “LeetCode Jump Game

  1. Pingback: LeetCode Jump Game II | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *