网站建设咨询,做视频找素材的网站有哪些,高端外贸网站制作,前端网站开发流程题目描述给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说#xff0c;如果你在 nums[i] 处#xff0c;你可以跳转到任意 nums[i j] 处:0 j nums[i] i j n返回到达 nums[n - 1] 的…题目描述给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处:0 j nums[i] i j n返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。解析这道题最容易想到的解法就是回溯法通过DFS将所有的情况都算出来但是这样算的话时间复杂度将达到O(n^2)容易超时。所以需要对该题进行一番分析通过题目描述看起来很像f(n-1)求f(n)的样子即动态规划求解但是这道题又不是常规的动态规划通过下面简单的例子进行分析上面是一个长度为7的数组最少用3步就可以达到末尾index[0,1,4]。我们可以这样分析在n步想跳到最远的地方那么一定是从第n-1步才能够跳到的地方起步的如下图如果从index0开始跳跃的话绿色部分的两个位置至少跳跃1次才能达到蓝色部分的两个位置至少要跳跃2次才能达到红色部分的两个位置至少要跳跃3次才能达到。所以是在前面最优的区段内求下一次能够跳跃到的区段实际还是动态规划。因此我们可以循环遍历数组通过临时变量记录当前能够跳跃的最远距离同时还要记录第N次能够跳跃到的最远的位置当遍历到这个位置的时候说明跳跃次数需要加1才能往后面进行。代码public int jump(int[] nums) {int maxPos 0;int jumpNumMaxIndex 0;int jumpNum 0;for (int i 0; i nums.length - 1; i) {maxPos Math.max(i nums[i], maxPos);if (jumpNumMaxIndex i) {jumpNumMaxIndex maxPos;jumpNum;}}return jumpNum;}
