程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode_Jump Game

LeetCode_Jump Game

編輯:C++入門知識

LeetCode_Jump Game


一.題目

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;
    }
};


四.體會

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved