大理石在哪些网站做宣传,永兴县网站建设,渠道建设网站,潍坊市建设工程交易中心网站题目
给定一个数组nums {1,2,3,4,5}#xff0c;每个元素nums[i]表示从i这个位置最多可以向前跳跃nums[i]个台阶#xff0c;求最小需要跳几次就可以调到末尾
思路
反向查找
从末尾开始逐个向前判断最远的起跳位置#xff0c;接着再以该位置递归的判断
public int jumpT…题目
给定一个数组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(position0){for(int i0;iposition;i){if(inums[i]position){position i;steps;break; } } }return steps;
}
效果
时间复杂度O(n^2)
空间复杂度O(1) 正向查找
从i0位置开始向后找每次在当前最远位置如i计算从i开始跳跃空间nums[i]内这个区间内能够跳的最远位置是哪里然后以此类推
public int jumpToTheEndWithMinSteps(int[] nums){int length nums.length;int end 0;int maxPosition 0;int steps 0;for(int i0;ilength;i){//计算ijend区间内能够跳的最远的位置将其记录为maxPositionmaxPosition Math.max(maxPosition,inums[i]);//每次区间结束都更新一下最新调的最远的位置if(iend){end maxPosition;steps; } }return steps;
}
效果
时间复杂度O(n)
空间复杂度O(1)
