leetcode热题100.跳跃游戏2

Problem: 45. 跳跃游戏 II

文章目录

  • 题目
  • 思路
  • 复杂度
  • Code

题目

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:

$0 <= j <= nums[i] $
i + j < n i + j < n 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

思路

我们思考一种朴素的解法,就是从后往前遍历遍历所有点x,在这层循环中再从左往右遍历所有点,看看哪个点最先能到达x,这个点就是我们的下一个要达到的点,然后我们再从左往右寻找能到达这个点的点就ok

class Solution {
    public int jump(int[] nums) {
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
}

我们观察下每次跳跃的规律,就拿 [ 2 , 3 , 1 , 2 , 4 , 2 , 3 ] [2,3,1,2,4,2,3] [2,3,1,2,4,2,3] 来说,

  • 对于位置0而言,他可以跳到位置1,2上;
  • 对于位置1而言,他可以跳到2,3,4这些位置上;
  • 对于位置2而言,他可以跳到位置4上;

在这里插入图片描述

此时我们发现一件事,当我们遍历数组到位置2,即 [1] 的时候,此时跳跃者肯定会从 [3,1] 这个子数组中跳跃到更远的地方;我们记录这个更远的地方为end,当我们遍历到end的时候,跳跃者肯定会从 [ 上一次跳跃的位置, e n d ] [上一次跳跃的位置,end] [上一次跳跃的位置,end] 中一个地方往前跳,哪个点跳的远就从哪个点跳

不难发现,我们每次到达end点,其实之前或者此刻都跳了一次,我们记录这次跳跃。

在程序一开始的时候,只遍历的第一个点,所以只能从第一个点开始跳;

当遍历结束的时候,如果我们遍历第n个点,而此刻end又恰好是第n个点,因为end是上一次跳跃更新的,所以上一次跳跃我们就到达了n点,所以我们不遍历n点,以免多计算一次

复杂度

时间复杂度:

O ( n ) O(n) O(n)

空间复杂度:

O ( 1 ) O(1) O(1)

Code

class Solution:
    def jump(self, nums: List[int]) -> int:
        right = 0
        end = 0
        n = len(nums)
        cnt = 0
        for i in range(n-1):
            if right < i+nums[i]:
                right = i+nums[i]

            if end == i:
                cnt += 1
                end = right
        return cnt

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/519807.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

leetcode.24. 两两交换链表中的节点

题目 给定一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后的链表。 你不能只是单纯的改变节点内部的值&#xff0c;而是需要实际的进行节点交换。 思路 创建虚拟头节点&#xff0c;画图&#xff0c;确认步骤。 实现 /*** Definition for singly-li…

C++运算符重载如何模拟数学表达式,或模拟Python sympy和numpy

在人工智能数学基础一书中&#xff0c;下面是一题Python求函数极限的例子&#xff1a; 【例2.6】使用Python编程求 lim( x → 1) (x^2 - 1 / x - 1) ————————————————————————————————————————— import sympy from sympy import oo…

详细剖析多线程3----代码案例分析

文章目录 一、单例模式(校招中最常考的设计模式之⼀)1.1饿汉模式1.2懒汉模式 二、阻塞队列三、定时器四、线程池五、总结 一、单例模式(校招中最常考的设计模式之⼀) 单例模式是一种设计模式&#xff0c;其核心思想是保证一个类只有一个实例&#xff0c;并提供一个全局访问点来…

Three.js阴影贴图

生成阴影贴图的步骤如下&#xff1a; 从光位置视点&#xff08;阴影相机&#xff09;创建深度图。从相机的角度进行屏幕渲染在每个像素点&#xff0c;将阴影相机的MVP矩阵计算出的深度值与深度图值进行比较如果深度图值较低&#xff0c;则说明该像素点存在阴影 &#xff0c;因…

html5如何在使用原生开发的情况下实现组件化

我们知道如何在vue/react中使用组件化开发&#xff0c;那么如果只是一个简单的界面&#xff0c;一个HTML就搞定的事情&#xff0c;你还会去新建一个vue/react项目吗&#xff1f; 在使用原生HTML开发时&#xff0c;我们也会遇到一些常见的功能、模块&#xff0c;那么如何在原生…

【APUE】网络socket编程温度采集智能存储与上报项目技术------多路复用

作者简介&#xff1a; 一个平凡而乐于分享的小比特&#xff0c;中南民族大学通信工程专业研究生在读&#xff0c;研究方向无线联邦学习 擅长领域&#xff1a;驱动开发&#xff0c;嵌入式软件开发&#xff0c;BSP开发 作者主页&#xff1a;一个平凡而乐于分享的小比特的个人主页…

无锡国家集成电路设计中心某公司的单锂小电机直流电机H桥驱动电路

H桥驱动 L9110S是一款直流电机驱动电路&#xff0c;适合单节锂电池应用。输出电流0.4A。价格约3毛。 推荐原因&#xff1a; 某些人应该知道这个地方&#xff0c;大多数人应该不知道这个地方&#xff0c;所以推荐一下。 这个地方去过几次&#xff0c;某公司与某方走的“近”&…

在同一个局域网如何共享打印机和文件

1.在连接了打印机的主机上设置 1.1启用windows共享 打开网络与共享中心&#xff0c;点击“更改高级共享设置” 选择&#xff1a; “启用网络发现”“启用文件和打印机共享”“启用共享以便可以访问网络的用户可以读取和写入公用文件夹中的文件” 打开控制面板&#xff0c;选…

C#将Console写至文件,且文件固定最大长度

参考文章 将C#的Console.Write同步到控制台和log文件输出 业务需求 在生产环境中&#xff0c;控制台窗口不便展示出来。 为了在生产环境中&#xff0c;完整记录控制台应用的输出&#xff0c;选择将其输出到文件中。 但是&#xff0c;一次性存储所有输出的话&#xff0c;文件会…

NASA数据集——加拿大西北地区(NWT)2014 年被野火烧毁的北方森林的实地数据

ABoVE: Characterization of Carbon Dynamics in Burned Forest Plots, NWT, Canada, 2014 简介 文件修订日期&#xff1a;2019-04-12 数据集版本: 1 摘要 该数据集提供了加拿大西北地区&#xff08;NWT&#xff09;2014 年被野火烧毁的北方森林的实地数据。在 2015 年的实…

(学习日记)2024.04.03:UCOSIII第三十一节:信号量函数接口讲解

写在前面&#xff1a; 由于时间的不足与学习的碎片化&#xff0c;写博客变得有些奢侈。 但是对于记录学习&#xff08;忘了以后能快速复习&#xff09;的渴望一天天变得强烈。 既然如此 不如以天为单位&#xff0c;以时间为顺序&#xff0c;仅仅将博客当做一个知识学习的目录&a…

Linux (Ubuntu)- mysql8 部署

目录 1.基本部署 2.修改密码 3.开启root可远程连接配置 1.基本部署 01》》先查看OS类型&#xff0c;如果是Ubuntu在往下边看 rootspray:/etc/mysql/mysql.conf.d# lsb_release -a LSB Version: core-11.1.0ubuntu2-noarch:security-11.1.0ubuntu2-noarch Distributor ID: …

12-1-CSS 常用样式属性

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 CSS 常用样式属性1 CSS 三角形2 CSS 用户界面样式2.1 什么是界面样式2.2 鼠标…

【Spring】AOP——使用@around实现面向切面的方法增强

工作业务中&#xff0c;有大量分布式加锁的重复代码&#xff0c;存在两个问题&#xff0c;一是代码重复率高&#xff0c;二是容易产生霰弹式修改&#xff0c;使用注解和AOP可以实现代码复用&#xff0c;简化分布式锁加锁和解锁流程。 around注解是AspectJ框架提供的&#xff0c…

RK3568测试

作者简介&#xff1a; 一个平凡而乐于分享的小比特&#xff0c;中南民族大学通信工程专业研究生在读&#xff0c;研究方向无线联邦学习 擅长领域&#xff1a;驱动开发&#xff0c;嵌入式软件开发&#xff0c;BSP开发 作者主页&#xff1a;一个平凡而乐于分享的小比特的个人主页…

Prometheus+grafana环境搭建Docker服务(docker+二进制两种方式安装)(八)

由于所有组件写一篇幅过长&#xff0c;所以每个组件分一篇方便查看&#xff0c;前七篇链接如下 Prometheusgrafana环境搭建方法及流程两种方式(docker和源码包)(一)-CSDN博客 Prometheusgrafana环境搭建rabbitmq(docker二进制两种方式安装)(二)-CSDN博客 Prometheusgrafana环…

java数据结构与算法刷题-----LeetCode172. 阶乘后的零

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 数学&#xff1a;阶乘的10因子个数数学优化:思路转变为求5的倍数…

【蓝桥杯选拔赛真题57】C++字符串反转 第十四届蓝桥杯青少年创意编程大赛 算法思维 C++编程选拔赛真题解

目录 C字符串反转 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 七、推荐资料 C字符串反转 第十四届蓝桥杯青少年创意编程大赛C选拔赛真题 一、题目要求 1、编程实现 给定一个只包含大写字母"M…

C++进阶--C++11(2)

C11第一篇 C11是C编程语言的一个版本&#xff0c;于2011年发布。C11引入了许多新特性&#xff0c;为C语言提供了更强大和更现代化的编程能力。 可变参数模板 在C11中&#xff0c;可变参数模板可以定义接受任意数量和类型参数的函数模板或类模板。它可以表示0到任意个数&…

蓝桥杯 第2155题质因数个数 C++ Java Python

题目 思路和解题方法 目标是计算给定数 n 的质因数个数。可以使用了试除法来找到 n 的所有质因数 读取输入的数 n。从 2 开始遍历到 sqrt(n)&#xff0c;对于每个数 i&#xff1a; 如果 n 能被 i 整除&#xff0c;则进行以下操作&#xff1a; 将 n 除以 i&#xff0c;直到 n 不…