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

LeetCode-100题(Hot) 45. 跳跃游戏 II [Java实现] [极速]_IllTamer的博客

18 人参与  2021年12月21日 14:33  分类 : 《随便一记》  评论

点击全文阅读


给你一个非负整数数组 nums ,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。


刚开始用的深搜,结果超时了emmm,而后转用贪心。在每一次从起始位置到perEnd的过程中动态更新所能走到的最远位置的下标,当每走到当前边界时,更新边界为最远处下标并将步数+1.

由题设 “一定能到达目标”,设循环次数为 nums.length-1 次以防止当 边界值为nums.length-1 即恰好走到尽头时步数仍+1的情况

    public int jump(int[] nums) {
        int step = 0;
        int maxPosition = 0;
        int perEnd = 0;
        // 因无论如何都能访问到最后一位,故跳过最后一位防止边界==nums.length时导致step+1
        for (int i = 0; i < nums.length-1; ++ i) {
            maxPosition = Math.max(maxPosition, i+nums[i]);
            if (i == perEnd) {
                perEnd = maxPosition;
                ++ step;
            }
        }
        return step;
    }

                ​​​​​​​        ​​​​​​​        ​​​​​​​ 


点击全文阅读


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

位置  数组  下标  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

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

最新文章

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

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

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