55. Jump Game I & II

我們看完題目, 很快地給出了下面的方法

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

道理很簡單, 就是設一個我們能達到的最遠距離, i+nums.at(i)就是根據這格資訊我們可以到的最遠位置,一旦reach超過我們目標的size(nums.size()-1), 我們就給true, 其餘結果就是false

很快地跑了測資, 發現沒有辦法全部通過

為什麼呢, 原來存在一種case是

[0,2,3]

我們可以看到第一個為0, 理論上這在之後都不會有結果(第一步都跨不出去)

因為我們的設計, 迴圈會繼續往下走, 所以2, 3就突破這個設計了

所以我們再加一個判別, 讓他不要超越

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

當我們發現現在這個位置, reach根本到達不了, 我們就給false,

這樣便可行了

參考網路上的做法後, 有個更優雅的, 只是他優雅到很難第一次就看明白

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

意思是一樣的, 主要都是跳出, 只是在最後面會判斷到底是達到的跳出, 還是沒辦法到達不了先掉出

我覺得要做jump 2前, 先理解過jump1會很好懂

jump無疑就是一個進階版, 剛剛只問能不能跳到最後一格, 這次則是要求,在最小跳耀距離可以到(看題目的意思是不管怎樣應該都會到？)

有一個很好的case

[2, 3, 1, 1, 1]

如果我們全部都走一步, 總共走四步, 會到, 但是其實最短的是從2->3->1就能抵達了, 只需兩步

這要怎麼做呢

首先我們可以確定的是, 最小走n步一定會到

所以我們先建立while迴圈, 我們會給一個當前目標最遠值(cur), 並設定cur到目標位置時即可中斷並且結算

而每個迴圈我們都去檢查目標最遠值以及當前index的中間的每個點(range)的狀況, 為什麼呢？ 因為有可能中間的點有更好更遠的結果, 以替代現有的當前最遠值

以下是code

class Solution {
  public:
    int jump(vector<int> &nums) {
        int step = 0;
        int cur = 0;
        int index = 0;
        while (cur < nums.size() - 1) {
            step++;
            int range = cur;
            for (; index <= range; index++) {
                cur = max(cur, nums.at(index) + index);
            }
        }
        return step;
    }
};

我覺得蠻有深度的, 在這邊紀錄一下

在心領神會後 寫出dp的解法

class Solution {
public:
    int jump(vector<int>& nums) {
        vector<int> dp(nums.size(), nums.size());
        dp[0] = 0;
        for(int i = 0 ; i < nums.size();i++){
           int step = nums[i];
            for(int j = 1; j <= step;j++){
                if(i + j < nums.size())
                dp[i + j] = min(dp[i + j], dp[i] + 1);
            }
        }
        return dp[nums.size() - 1];
    }
};