Leetcode 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.
Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

Solution 1(動的計画に基づく)
75/75 test cases passed. Status: Accepted Runtime: 756 ms Submitted: 22 minutes ago

class Solution {
public:
    bool canJump(vector<int>& nums) {
        // true : can reach final
        // false : cannot reach
        vector<bool> states(nums.size(), false);
        states[states.size()-1] = true;
        for (int i = states.size() - 1; i >= 0; i--) { 
            for (int len = nums[i]; len > 0; len--) { // from 1 to nums[i]
                if (states[i + len] == true) {
                    states[i] = true;
                    break;
                }
            }
        }
        return states[0];
    }
};

問題解
現在の下付き位置の点が最後の点に達できるかどうかを表すブール配列states[]を確立した.例えば、最初の点が最後の点に到達できる場合、states[0]=trueと表記される.
最後のポイントから計算できます.

まず、最後の点は自分に着くことができて、私たちはそれをtrueとマークします.

は、現在の点iが自身の到達可能な範囲(nums[i])内にstatesがtrueと表記されている点があれば、それは末尾に達する点に到達できることを示しており、明らかにこの点にジャンプすることによって末尾に到達することができ、states[i]=trueと表記されている.

はi == 0まで遍歴し続け、0が達成できるかどうかの情報(すなわちstates[0])

を得た.
ぶんせき
複雑さの感覚はあまりよく分析されず、外層はO(n)のサイクルであり、内層は主にnums[i]の大きさに依存する(O(nums[i]と理解できる).mがnums配列要素の平均数であると仮定すると,アルゴリズムの時間的複雑さはO(nm)である.
(もちろん、条件を満たす直接break;の文を加えた後、複雑さは少し小さいかもしれませんが、756 msを走ったので、限られています).
空間複雑度は単純で,states配列,O(n)であった.
Solution 2(欲張りアルゴリズムベース)
75/75 test cases passed. Status: Accepted Runtime: 8 ms Submitted: 35 minutes ago

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

問題解
1つの整数値furthestReachablePostionを経営し、現在の位置から最も遠い距離を表す.
例えば、入力は[3,2,1,0,4]であり、位置0の最も遠いところは3である.
各点におけるfurthestReachablePostionは、移動後から、前の位置のfurthestReachablePostion、さらに-1、または現在の位置の最も遠いnums[i]であることを考慮することができる.

現在位置の最も遠い位置がfurthestReachablePostionに達し、現在位置iが末尾に等しい位置より大きい場合、この点は末尾に達すると言える.

furthestReachablePostion<=0であれば、現在のポイントから離れられないため、到達できないと言えます.

ぶんせき
時間の複雑さ:O(n)で、1回の遍歴しか使用されていません.
空間複雑度:O(1)、変数を1つ使っただけです.