LeetCode 每日一題 55. 跳躍遊戲 雙百效率 C/C++描述

  大家好，我叫亓官劼（qí guān jié ）

題目

難度 中等

給定一個非負整數數組，你最初位于數組的第一個位置。

數組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最後一個位置。

示例 1:

輸入: [2,3,1,1,4]
輸出: true
解釋: 我們可以先跳 1 步，從位置 0 到達 位置 1, 然後再從位置 1 跳 3 步到達最後一個位置。      

示例 2:

輸入: [3,2,1,0,4]
輸出: false
解釋: 無論怎樣，你總會到達索引為 3 的位置。但該位置的最大跳躍長度是 0 ， 是以你永遠不可能到達最後一個位置。      

題解一：貪心

  這題我們可以使用貪心進行求解，我們使用一個變量​

​position​

​​來記錄目前最大可以走到的位置，然後從0開始對數組進行周遊，求出走到每一個位置上時，能夠走到的最大的位置，如果最大位置大于n-1，則可以走到頭，我們傳回​

​true​

​​，如果周遊結束之後還是沒有走到頭，則無法走到頭，即傳回​

​false​

​。

完整的題解代碼為：

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

此時貪心算法的執行效率為：