一.題目

Jump Game

My Submissions Total Accepted: 62617 Total Submissions: 228632 Difficulty: Medium

 

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.

 

Subscribe to see which companies asked this question

Show Tags Have you met this question in a real interview? Yes No Discuss

二.解題技巧

這道題可以用貪心法來做，每次都選擇下下一跳最遠的地方來作為下一跳的位置，如果最終能夠達到最後的坐標，即滿足條件。否則，不能達到最後一個下標。可以先將數組中的每個元素都加上自己的下標，這樣就可以得到當前位置所能達到的最遠距離。這樣，只要在當前位置和當前位置所能達到的最遠位置之間選擇最大值，就可以得到下下一跳能夠達到最遠距離的下一跳位置。

三.實現代碼

#include 
#include 

using std::vector;
using std::max_element;

class Solution
{
public:
    bool canJump(vector& nums)
    {
        const vector::size_type SIZE = nums.size();
        const vector::size_type LastIndex = SIZE - 1;

        //
        for (vector::size_type Index = 0; Index < SIZE; ++Index)
        {
            nums[Index] += Index;
        }

        vector::iterator Now = nums.begin();

        while (Now != nums.end())
        {
            if (*Now >= LastIndex)
            {
                return true;
            }

            if (Now == nums.begin() + *Now)
            {
                return false;
            }

            Now = max_element(Now + 1, nums.begin() + *Now + 1);
        }

        return true;
    }
};

四.體會

這道題的主要技巧在於如何判斷選擇下下一跳最遠的位置來作為下一跳，通過將數組元素的值加上對應的下標，就可以得到每一個位置下一跳的位置，這樣就可通過尋找下下跳最遠的地方來判斷是否可以到達最後一個坐標。