当前位置:首页 » 《随便一记》 » 正文

【Leetcode贪心区间问题二】45. 跳跃游戏 II_AloneYueCSDN

14 人参与  2022年01月11日 15:41  分类 : 《随便一记》  评论

点击全文阅读


文章目录

  • Leetcode45
    • 1.问题描述
    • 2.解决方案

Leetcode45

1.问题描述

在这里插入图片描述

2.解决方案

思路关键在于:在当前步覆盖范围内找一个下一步能走最远的,作为下一步的选择!
官方说法:以最小的步数增加最大的覆盖范围,直到覆盖范围覆盖到了终点!

在这里插入图片描述


代码实现也思路清晰
1.在i<=curDistance范围内找到最大的nextDistance
2.在i==curDistance进行判断要不要再走一步
2.1 不用走了
2.2 再走一步
2.3 剪枝,如果这到终点了直接返回(这一步不一定会提升效率说实话)

代码实现有个注意的点,官方的curDistance初始化是为零,我初始化为了nums[0],其实都可以,初始化为零不过就是第一次循环后把nums[0]赋给了curDistance,效果一样的

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()==1) return 0;
        int ans=1;
        int curDistance=nums[0];
        int nextDistance=0;

        for(int i=1;i<nums.size();i++){
            //1.在i<=curDistance范围内找到最大的nextDistance
            nextDistance=max(nextDistance,nums[i]+i);
            
            //2.在i==curDistance进行判断要不要再走一步
            if(i==curDistance){
                //2.1 不用走了
                if(curDistance==nums.size()-1) return ans;
                
                //2.2 再走一步
                curDistance=nextDistance;
                ans++;
                //2.3 剪枝,如果这到终点了直接返回(这一步不一定会提升效率说实话)
                if(nextDistance>=nums.size()-1) return ans;
            }
        }

        return ans;
    }
};

点击全文阅读


本文链接:http://m.zhangshiyu.com/post/33035.html

范围内  剪枝  终点  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 傅憬琛叶汐恬:结局+番外精编之作(疯起爱意,傅总只想宠心上人)完整章节列表_笔趣阁
  • 全书免费云朝朝容临渊节选_云朝朝容临渊节选全书免费
  • 神秘家的双头蛇母被砍头那夜,我黑化了陆临现陆娆沈寒云全书在线
  • 白色大油花的撞破艺术家老公和人体模特加练回春现场,我在画展上当众离婚教他做人周瀜白茉影全书在线
  • 从市府大秘到权力巅峰读者推荐_陆一鸣凌思文后续+完结_小说后续在线阅读_无删减免费完结_
  • 周晚黎厉北辰小说(死后我弃夫虐茶,独美不原谅)(周晚黎厉北辰)全书+后续+结局在线阅读
  • 小说大结局小说山与星辰小说已更新+特别篇(林景山苏星辰)纯净版
  • 终章小说顾澜音封灼年完结篇(碑婚)已更新+延伸(顾澜音封灼年)清爽版
  • 宋予柯奕烜小说小说全集+延伸+完本(玩笑沦陷)畅享在线阅读
  • 宋璃陆泽野小说(七零大院:离婚后嫁绝嗣京少多胎)小说结尾+隐藏篇章(宋璃陆泽野)畅享阅读
  • 完结文重生后我让校花保管所有准考证完结+结局+番外宝藏美文列表_完结文重生后我让校花保管所有准考证完结+结局+番外宝藏美文(秦雨然江述怀洛瑶)
  • 重生在高考前,我笑着送小青梅和小混混去庆祝成人礼一口气读完乔念沈晏安陆坤完本_重生在高考前,我笑着送小青梅和小混混去庆祝成人礼一口气读完(乔念沈晏安陆坤)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1