题解 | #跳跃游戏(三)#

跳跃游戏(三)

http://www.nowcoder.com/practice/14abdfaf0ec4419cbc722decc709938b

题意

给一个数组,每个位置表示当前能到之后的数组的最远距离,求从最开始到最后一个的位置跳转的最小次数

限制:

数组长度不大于1000

方法

遍历枚举

直接模拟题目,增加一个辅助数组记录每个位置的最小跳次数.

从头开始遍历,对每个可以到达的位置,更新它和它之后的位置的最小跳跃次数

如果有位置能直接到终点,则直接输出即可

以题目的样例数据[2,1,3,3,0,0,100]为例

下标	值	操作	辅助数组
0	2	把它之后的两个位置赋值1	[0,1,1,INF,INF,INF,INF]
1	1	把它之后的一个位置赋值2,但是因为之后一个位置为1,小于2,所以不产生效果过	[0,1,1,INF,INF,INF,INF]
2	3	把它之后的3个位置赋值2	[0,1,1,2,2,2,INF]
3	3	直接能到终点直接输出3	-

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int minJumpStep(vector<int>& nums) {
        if(nums.size() == 1)return 0; // 特殊情况处理
        if(nums.size() == 0)return -1; // 特殊情况处理
        const int INF = 0x3f3f3f3f;
        vector<int> ans(nums.size(),INF); //初始化
        ans[0] = 0;
        for(int i = 0;i<nums.size();i++){
            if(ans[i]==INF)continue; // 不可达忽略
            if(i+nums[i] >= nums.size()-1){ // 直接跳到终点 输出
                return ans[i]+1;
            }
            for(int j = 1;j<=nums[i];j++){ // 注意只保存最小值
                ans[i+j] = min(ans[i+j],ans[i]+1);
            }
        }
        return -1;
    }
};

复杂度分析

时间复杂度: 对于每个位置,最坏情况更新几乎整个数组,所以时间复杂度为 $O (n^{2})$

空间复杂度: 主要消耗在辅助数组的存储,所以空间复杂度为 $O (n)$

基于数学性质的时间复杂度优化

注意到因为跳跃是从1到当前最大距离都会更新的,那么如果每次更新前,整个距离数组是单调递增的,那么每个数组更新后也是单调递增的

因为更新的值大于当前位置的值,且更新当前位置之后位置的值. 上一次更新的值一定不大于这次更新的值,同时更新时为了维护最小的次数,所以每个位置最多被更新一次

根据单调性,可以从后向前更新

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int minJumpStep(vector<int>& nums) {
        if(nums.size() == 1)return 0; // 特殊情况处理
        if(nums.size() == 0)return -1; // 特殊情况处理
        const int INF = 0x3f3f3f3f;
        vector<int> ans(nums.size(),INF); //初始化
        ans[0] = 0;
        for(int i = 0;i<nums.size();i++){
            if(ans[i]==INF)continue;
            if(i+nums[i] >= nums.size()-1){
                return ans[i]+1;
            }
            for(int j = nums[i];j>=1;j--){ // 从后向前
                if(ans[i+j]!=INF)break; // 唯一一次被更新
                ans[i+j] = ans[i]+1;
            }
        }
        return -1;
    }
};