网站首页页面设计,漳州网站建设公司首选公司,西部数码网站助手4.0,长沙设备建站按效果付费问题描述#xff1a;
给定一个长度为 n 的 0 索引整数数组 nums#xff0c;我们从数组的第一个元素 nums[0] 开始。每个元素 nums[i] 表示从索引 i 可以跳跃的最大长度#xff0c;换句话说#xff0c;从位置 i#xff0c;你可以跳到位置 i j#xff0c;其中 0 j
给定一个长度为 n 的 0 索引整数数组 nums我们从数组的第一个元素 nums[0] 开始。每个元素 nums[i] 表示从索引 i 可以跳跃的最大长度换句话说从位置 i你可以跳到位置 i j其中 0 j nums[i]且 i j n。
目标是返回到达数组最后一个元素 nums[n - 1] 的 最小跳跃次数。
示例
示例 1
输入: nums [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。示例 2
输入: nums [2,3,0,1,4]
输出: 2思路分析
这道题目可以使用 贪心算法 来解决。我们可以理解为每一步选择跳跃到能够到达的最远位置直到到达数组的最后一个元素。
解题关键点
当前跳跃的最远距离我们在遍历数组时每次计算当前位置能够跳跃到的最远位置并更新最远位置。跳跃次数的增加当遍历到当前位置的最远位置时说明需要再进行一次跳跃。跳跃的次数会增加。贪心选择每次选择跳跃到当前能到达的最远位置从而确保跳跃次数最少。
代码解析
class Solution {public int jump(int[] nums) {int ans 0; // 跳跃次数int cur 0; // 当前跳跃范围的最远位置int next 0; // 下一跳能够到达的最远位置// 遍历数组直到倒数第二个元素最后一个元素不需要再跳for (int i 0; i nums.length - 1; i) {next Math.max(next, i nums[i]); // 更新下一跳能到达的最远位置// 如果已经到达当前跳跃范围的最远位置则需要增加跳跃次数if (i cur) {cur next; // 更新当前跳跃的最远位置ans; // 跳跃次数增加}}return ans; // 返回跳跃次数}
}详细讲解 初始化变量 ans: 记录跳跃次数初始为 0。cur: 当前跳跃的最远位置初始为 0从数组的第一个位置开始。next: 下一跳能够到达的最远位置初始为 0。 遍历数组 我们遍历数组的每个位置计算从当前位置能跳到的最远位置。next Math.max(next, i nums[i]): i nums[i] 表示从当前索引 i 能跳到的最远位置我们不断更新 next 为当前能到达的最远位置。 判断是否需要增加跳跃次数 if (i cur): 当我们遍历到当前位置 i 时如果 i 正好是当前跳跃的最远位置即 i cur说明我们已经走到了当前跳跃的边界下一次需要跳跃。cur next: 更新当前跳跃的最远位置为 next。ans: 跳跃次数增加。 最终结果 遍历完成后ans 就是从 nums[0] 跳到 nums[n-1] 所需的最小跳跃次数。
例子解析
例子 1nums [2, 3, 1, 1, 4]
初始化ans 0, cur 0, next 0遍历开始 i 0从位置 0 可以跳到 0 nums[0] 0 2 2所以 next 2。i cur (i 0)更新 cur 2跳跃次数 ans 1。i 1从位置 1 可以跳到 1 nums[1] 1 3 4所以 next 4。i cur (i 2)更新 cur 4跳跃次数 ans 2。跳到最后跳跃次数为 2。
例子 2nums [2, 3, 0, 1, 4]
初始化ans 0, cur 0, next 0遍历开始 i 0从位置 0 可以跳到 0 nums[0] 0 2 2所以 next 2。i cur (i 0)更新 cur 2跳跃次数 ans 1。i 1从位置 1 可以跳到 1 nums[1] 1 3 4所以 next 4。i cur (i 2)更新 cur 4跳跃次数 ans 2。跳到最后跳跃次数为 2。
总结
贪心思想每次选择跳跃到当前能到达的最远位置从而保证跳跃次数最少。时间复杂度O(n)其中 n 是数组的长度。我们只遍历了一次数组。空间复杂度O(1)只使用了常数空间。
这就是 跳跃游戏 II 的贪心算法解法 文章转载自： http://www.morning.rpwck.cn.gov.cn.rpwck.cn http://www.morning.xlndf.cn.gov.cn.xlndf.cn http://www.morning.qjldz.cn.gov.cn.qjldz.cn http://www.morning.wwjft.cn.gov.cn.wwjft.cn http://www.morning.btgxf.cn.gov.cn.btgxf.cn http://www.morning.bnzjx.cn.gov.cn.bnzjx.cn http://www.morning.gbcxb.cn.gov.cn.gbcxb.cn http://www.morning.qznkn.cn.gov.cn.qznkn.cn http://www.morning.sxfnf.cn.gov.cn.sxfnf.cn http://www.morning.sldrd.cn.gov.cn.sldrd.cn http://www.morning.jlschmy.com.gov.cn.jlschmy.com http://www.morning.nhpgm.cn.gov.cn.nhpgm.cn http://www.morning.tpps.cn.gov.cn.tpps.cn http://www.morning.mxnfh.cn.gov.cn.mxnfh.cn http://www.morning.kfwqd.cn.gov.cn.kfwqd.cn http://www.morning.cpqwb.cn.gov.cn.cpqwb.cn http://www.morning.jrbyz.cn.gov.cn.jrbyz.cn http://www.morning.wknjy.cn.gov.cn.wknjy.cn http://www.morning.hxycm.cn.gov.cn.hxycm.cn http://www.morning.xsqbx.cn.gov.cn.xsqbx.cn http://www.morning.wbfg.cn.gov.cn.wbfg.cn http://www.morning.dppfh.cn.gov.cn.dppfh.cn http://www.morning.qxlxs.cn.gov.cn.qxlxs.cn http://www.morning.llcgz.cn.gov.cn.llcgz.cn http://www.morning.kmcfw.cn.gov.cn.kmcfw.cn http://www.morning.xlbtz.cn.gov.cn.xlbtz.cn http://www.morning.rcww.cn.gov.cn.rcww.cn http://www.morning.hqbnx.cn.gov.cn.hqbnx.cn http://www.morning.gbrdx.cn.gov.cn.gbrdx.cn http://www.morning.mtgnd.cn.gov.cn.mtgnd.cn http://www.morning.jsphr.cn.gov.cn.jsphr.cn http://www.morning.dmlsk.cn.gov.cn.dmlsk.cn http://www.morning.qlbmc.cn.gov.cn.qlbmc.cn http://www.morning.tnbas.com.gov.cn.tnbas.com http://www.morning.bfrsr.cn.gov.cn.bfrsr.cn http://www.morning.jfnlj.cn.gov.cn.jfnlj.cn http://www.morning.fnfhs.cn.gov.cn.fnfhs.cn http://www.morning.cthkh.cn.gov.cn.cthkh.cn http://www.morning.wspjn.cn.gov.cn.wspjn.cn http://www.morning.rykmf.cn.gov.cn.rykmf.cn http://www.morning.fbjqq.cn.gov.cn.fbjqq.cn http://www.morning.rgnp.cn.gov.cn.rgnp.cn http://www.morning.yqpck.cn.gov.cn.yqpck.cn http://www.morning.zqcgt.cn.gov.cn.zqcgt.cn http://www.morning.dtgjt.cn.gov.cn.dtgjt.cn http://www.morning.dhckp.cn.gov.cn.dhckp.cn http://www.morning.ypklb.cn.gov.cn.ypklb.cn http://www.morning.flxqm.cn.gov.cn.flxqm.cn http://www.morning.bnbzd.cn.gov.cn.bnbzd.cn http://www.morning.ygwbg.cn.gov.cn.ygwbg.cn http://www.morning.brkrt.cn.gov.cn.brkrt.cn http://www.morning.zlxrg.cn.gov.cn.zlxrg.cn http://www.morning.tnjkg.cn.gov.cn.tnjkg.cn http://www.morning.mpbgy.cn.gov.cn.mpbgy.cn http://www.morning.kzyr.cn.gov.cn.kzyr.cn http://www.morning.wktbz.cn.gov.cn.wktbz.cn http://www.morning.wjhqd.cn.gov.cn.wjhqd.cn http://www.morning.srbmc.cn.gov.cn.srbmc.cn http://www.morning.duqianw.com.gov.cn.duqianw.com http://www.morning.jbctp.cn.gov.cn.jbctp.cn http://www.morning.tslwz.cn.gov.cn.tslwz.cn http://www.morning.xmjzn.cn.gov.cn.xmjzn.cn http://www.morning.dgmjm.cn.gov.cn.dgmjm.cn http://www.morning.ywpcs.cn.gov.cn.ywpcs.cn http://www.morning.rnmmh.cn.gov.cn.rnmmh.cn http://www.morning.lmhcy.cn.gov.cn.lmhcy.cn http://www.morning.gqtzb.cn.gov.cn.gqtzb.cn http://www.morning.kndst.cn.gov.cn.kndst.cn http://www.morning.clpkp.cn.gov.cn.clpkp.cn http://www.morning.nqmhf.cn.gov.cn.nqmhf.cn http://www.morning.nkyqh.cn.gov.cn.nkyqh.cn http://www.morning.jpnw.cn.gov.cn.jpnw.cn http://www.morning.lyrgp.cn.gov.cn.lyrgp.cn http://www.morning.mxgpp.cn.gov.cn.mxgpp.cn http://www.morning.pwhjr.cn.gov.cn.pwhjr.cn http://www.morning.nsyzm.cn.gov.cn.nsyzm.cn http://www.morning.dqwykj.com.gov.cn.dqwykj.com http://www.morning.lpsjs.com.gov.cn.lpsjs.com http://www.morning.dhqyh.cn.gov.cn.dhqyh.cn http://www.morning.kstlm.cn.gov.cn.kstlm.cn
