跳跃游戏-算法

题目

给定一个数组nums = {1,2,3,4,5}，每个元素nums[i]表示从i这个位置最多可以向前跳跃nums[i]个台阶，求最小需要跳几次就可以调到末尾

思路

反向查找

从末尾开始逐个向前判断最远的起跳位置，接着再以该位置递归的判断

public int jumpToTheEndWithMinSteps(int[] nums){
    int position = nums.length-1;
    int steps = 0;
    while(position>0){
        for(int i=0;i<position;i++){
            if(i+nums[i]>=position){
                position = i;
                steps++;
                break;            
            }        
        }    
    }
    return steps;
}

效果

时间复杂度：O(n^2)

空间复杂度：O(1)

正向查找

从i=0位置开始向后找，每次在当前最远位置如i，计算从i开始跳跃空间nums[i]内这个区间内能够跳的最远位置是哪里，然后以此类推

public int jumpToTheEndWithMinSteps(int[] nums){
    int length = nums.length;
    int end = 0;
    int maxPosition = 0;
    int steps = 0;
    for(int i=0;i<length;i++){
        //计算i<j<=end区间内能够跳的最远的位置，将其记录为maxPosition
        maxPosition = Math.max(maxPosition,i+nums[i]);
        //每次区间结束，都更新一下最新调的最远的位置
        if(i==end){
            end = maxPosition;
            steps++;        
        }    
    }
    return steps;
}

效果

时间复杂度：O(n)

空间复杂度：O(1)