当前位置: 首页 > article >正文

力扣45. 跳跃游戏 II

给定一个长度为 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]


示例 1:

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

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 nums[n-1]

代码:

class Solution {
public:
    int jump(vector<int>& nums) {
        int maxmost = 0, len = nums.size(), step = 0, end = 0;

        for(int i = 0; i < len-1; i++){

            if(i <= maxmost){
                maxmost = max(i+nums[i], maxmost);
                if(i == end){
                    end = maxmost;
                    step++;
                }
            }
        }

        return step;
    }
};

解题思路:

(1)使用贪心思想。

(2)每次跳到下一次能跳到最远距离的下标。

(3)使用 end 来限制当前步数能跳到的最远距离。


http://www.kler.cn/a/444098.html

相关文章:

  • 图形学笔记 - 5. 光线追踪2 - 加速结构
  • 【win10+RAGFlow+Ollama】搭建本地大模型助手(教程+源码)
  • ChromeOS 131 版本更新
  • centos7下docker 容器实现redis主从同步
  • React:闭包陷阱产生和解决
  • 深入了解Python模拟负载均衡器:将请求高效分发至多个服务器
  • 基于springboot社区服务系统
  • 如何区分PHP和java?原生源码和次生源码的区别?
  • 前端本地数据存储方式有哪些
  • 基于QT(C++)实现的日历程序
  • QT基础和练习
  • 利用Python爬虫获取微店商品详情API接口的深入指南
  • 蓝桥杯——竞赛省赛国赛题分享
  • React中定义和使用函数式组件
  • 天天 AI-241215:今日热点-OpenAI发布ChatGPT Projects,万能工具箱上线!
  • Vue零基础教程|从前端框架到GIS开发系列课程(五)组件式开发
  • Quartz 架构和单体应用介绍
  • 汽车IVI中控开发入门及进阶(三十八):HiCar开发
  • 数据结构,链表的简单使用
  • UDP基本了解
  • 为什么要用单例模式?
  • windows C#-命名实参和可选实参(下)
  • C/C++语言——解题
  • 机试题——维修工
  • UI框架DevExpress XAF v24.2新功能预览 - .NET Core / .NET增强
  • Flutter控件FutureBuilder控件详解