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

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

27 人参与  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://zhangshiyu.com/post/33035.html

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

  • 评论(0)
  • 赞助本站

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

最新文章

  • 家宴过后,我捉奸了庶妹和我老公无广告_庶妹老公侍卫TOP10_小说后续在线阅读_无删减免费完结_
  • 寝室六个人,她们背着我建五人群必读文_太天真申请书冷笑最新阅读_小说后续在线阅读_无删减免费完结_
  • 开局获得狐仙传承结局+番外_江帆赵雪隐藏剧情_小说后续在线阅读_无删减免费完结_
  • 刀锈春根生,白骨犹温完结全文_卫舟棠棠知意一口气完结_小说后续在线阅读_无删减免费完结_
  • 夫君立筷子定我灾星罪名,我改嫁冷宫皇子后他追悔莫及好评_赵荀孟如安青瑶精心编著_小说后续在线阅读_无删减免费完结_
  • 邻居低素质,而我没素质独家番外_老太太赖皮欣欣超长版_小说后续在线阅读_无删减免费完结_
  • 重生后我转嫁首富瘸腿独子,总裁前夫却疯了一口气看完_妹妹傅云琛沈明辉独家番外_小说后续在线阅读_无删减免费完结_
  • 我拒绝给系花捐款后,全系同学悔疯了在线阅读_小说后续在线阅读_无删减免费完结_
  • 我让位给女友的透视眼竹马,他却说如果能重生再也不来了。虐心反转_玉石林若女友推荐_小说后续在线阅读_无删减免费完结_
  • 相国独子的丫鬟砸坏我的玉佩后,我当场拒婚阅读_玉佩陈郡谢氏全新_小说后续在线阅读_无删减免费完结_
  • 手术时,我看着病人惨死最新试读_淼淼陆知衍姜颜全本完结_小说后续在线阅读_无删减免费完结_
  • 男友霸道给我开黑卡,转头却骂我是捞女最新章节_肖年顾客黑卡热文_小说后续在线阅读_无删减免费完结_

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

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