45. Jump Game II

45. Jump Game II

class Solution {
public:
    int jump(vector<int>& nums) {
        int level = 0;
        int maxReach = 0;
        int i = 0;
        while(maxReach < nums.size() - 1)
        {
            ++level;
            for(int maxT = maxReach; i <= maxT; ++i)
            {
                maxReach = max(maxReach, nums[i] + i);
                if(maxReach >= nums.size() - 1)
                    return level;
            }
        }
        return level;
    }
};

视为BFS问题

每个区域里都可以走到下一层的任何一个点，实在走不到了，只能换层了

class Solution {
public:
    int jump(vector<int>& nums) {
        int level = 0, maxReachFurther = 0, maxReachEnd = 0; // #defind jumptime level，这样解释比较合理
        for(int i = 0; i < nums.size() - 1; ++i)  // 这里用nums.size() - 1而不是nums.size() 是因为如果走到了最后一个，但是最后一个，那么已经不用考虑换层了，例如[0]，如果到达0，再换层，那就扰乱了结果。因为假设的是一定可以到达终点，而最后一次起跳就表示了一定可以到达终点。这里面对最后一跳超越终点也无所谓，因为已经记录了这一跳了。
        {
            maxReachFurther = max(maxReachFurther, nums[i] + i); // 目前层能达到的最远
            // 首先先从0开始起跳，跳跃次数加一。然后每次碰到这次的结尾，跳跃次数加一。
            if(maxReachEnd == i)
            {
                maxReachEnd = maxReachFurther;  // 对于下一层来说  记录上一层能达到的最远，如果遇见，那么这一层就结束了
                ++level; // level代表着需要重新起跳，跳到下一层了，记录的不是层数而跳跃的次数。
            }
        }
        return level;
    }
};

review

class Solution {
public:
    int jump(vector<int>& nums) {
        int level = 0;
        int this_level_border = 0; // 上一层所决定的这一层的边界
        int cur_reach = 0; // 当前最大能到的，下一层的边界
        int n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            if(this_level_border >= n - 1)
                return level;
            cur_reach = max(cur_reach, nums[i] + i);
            if(this_level_border == i)
            {
                ++level;
                this_level_border = cur_reach;
            }
        }
        return level;
    }
};