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

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 = 0end = 0n = len(nums)cnt = 0for i in range(n-1):if right < i+nums[i]:right = i+nums[i]if end == i:cnt += 1end = rightreturn cnt

相关文章:

leetcode热题100.跳跃游戏2

Problem: 45. 跳跃游戏 II 文章目录 题目思路复杂度Code 题目 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说&#xff0c;如果你在 nums[i] 处&#xff0c;你可以跳转到任意 nums[i j] 处: …...

【前端】CSS(引入方式+选择器+常用元素属性+盒模型+弹性布局)

文章目录 CSS一、什么是CSS二、语法规范三、引入方式1.内部样式表2.行内样式表3.外部样式 四、选择器1.选择器的种类1.基础选择器&#xff1a;单个选择器构成的1.标签选择器2.类选择器3.id 选择器4.通配符选择器 2.复合选择器1.后代选择器2.子选择器3.并集选择器4.伪类选择器 五…...

迷茫下是自我提升

长夜漫漫&#xff0c;无心睡眠。心中所想&#xff0c;心中所感&#xff0c;忧愁当前&#xff0c;就执笔而下&#xff0c;写下这篇文章。 回忆过往 回想当初为啥学前端&#xff0c;走前端这条路&#xff0c;学校要求嘛&#xff0c;兴趣爱好嘛&#xff0c;还是为了钱。 时间带着…...

用vscode仿制小米官网

html内容: <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title><link rel&quo…...

【Java+Springboot】------ 通过JDBC+GetMapping方法进行数据select查询、多种方式传参、最简单的基本示例!

一、JDBC如何使用、PostGresql数据库 1、在pom.xml 先引用jdbc组件。 <!--jdbc--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-jdbc</artifactId></dependency> 2、在pom.xml 再引用p…...

基于单片机光伏太阳能跟踪系统设计

**单片机设计介绍&#xff0c;基于单片机光伏太阳能跟踪系统设计 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机光伏太阳能跟踪系统的设计&#xff0c;旨在通过单片机技术实现对光伏太阳能设备的自动跟踪&#xff0c;以提高太阳…...

Stable Diffusion 本地化部署

一、前言 最近在家背八股文背诵得快吐了&#xff0c;烦闷的时候&#xff0c;看到使用 AI 进行作图&#xff0c;可以使用本地话部署。刚好自己家里的电脑&#xff0c;之前买来玩暗黑4&#xff0c;配置相对来说来可以&#xff0c;就拿来试试。 此篇是按照 Github 上的 stable-d…...

C++ Algorithm 常用算法

C <algorithm> 头文件是标准库中提供的一系列算法&#xff0c;用于操作范围&#xff08;range&#xff09;内的元素。这些算法可以用于数组、容器如vector和list&#xff0c;以及其他满足相应迭代器要求的数据结构。以下是一些常用的C <algorithm> 中的算法及其使用…...

线程安全--深入探究线程等待机制和死锁问题

꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转…...

量子计算获重大突破!微软和Quantinuum将量子计算错误率降低800倍,网友:AI算力的希望

量子计算迎来新突破。 近日&#xff0c;微软和量子计算公司Quantinuum宣布&#xff1a;发现了一种新的量子计算系统&#xff0c;可以将传统量子计算的错误率下降800倍&#xff0c;这让高性能量子计算机走进现实更近了一步。 自生成式AI爆发以来&#xff0c;算力是AI发展面临的…...

WordPress 6.5 “里贾纳”已经发布

WordPress 6.5 “里贾纳”已经发布&#xff0c;其灵感来自著名爵士小提琴家Regina Carter的多才多艺。雷吉娜是一位屡获殊荣的艺术家和著名的爵士乐教育家&#xff0c;以超越流派而闻名&#xff0c;她在古典音乐方面的技术基础和对爵士乐的深刻理解为她赢得了大胆超越小提琴所能…...

甲方安全建设之日志采集实操干货

前言 没有永远的安全&#xff0c;如何在被攻击的情况下&#xff0c;快速响应和快速溯源分析攻击动作是个重要的话题。想要分析攻击者做了什么、怎么攻击进来的、还攻击了谁&#xff0c;那么日志是必不可少的一项&#xff0c;因此我们需要尽可能采集多的日志来进行分析攻击者的…...

dm8 开启归档模式

dm8 开启归档模式 1 命令行 [dmdbatest1 dm8]$ disql sysdba/Dameng123localhost:5237服务器[localhost:5237]:处于普通打开状态 登录使用时间 : 3.198(ms) disql V8 SQL> select name,status$,arch_mode from v$database;行号 NAME STATUS$ ARCH_MODE ----------…...

“AI复活”背后的数字永生:被期待成为下一个电商,培育市场认知和用户心智还需时间

“AI复活”背后的数字永生&#xff1a;被期待成为下一个电商&#xff0c;培育市场认知和用户心智还需时间© 由 九派新闻 提供 数字永生&#xff0c;还是电子宠物&#xff1f;过去一个月&#xff0c;因包小柏用AI技术让爱女在数字世界“复活”一事&#xff0c;《流浪地球2…...

基于单片机钢琴电子节拍器系统设计

**单片机设计介绍&#xff0c;基于单片机钢琴电子节拍器系统设计 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机钢琴电子节拍器系统设计是一个综合性的项目&#xff0c;它结合了单片机编程、音频处理、用户界面设计等多个领域的…...

我的创作纪念日(year Ⅱ)

大家好&#xff0c;我是Kamen Black 君&#xff0c;今天我与大家简单分享一下我两年来在CSDN的创作历程。 print("祝大家每天快乐&#xff0c;love and peace&#xff01;") 机缘 当初写博客是为了记录一些自己大学中做比赛的心得&#xff0c;没想到自己能走到这一步…...

应急响应实战笔记05Linux实战篇(1)

第1篇&#xff1a;SSH暴力破解 0x00 前言 ​ SSH 是目前较可靠&#xff0c;专为远程登录会话和其他网络服务提供安全性的协议&#xff0c;主要用于给远程登录会话数据进行加密&#xff0c;保证数据传输的安全。SSH口令长度太短或者复杂度不够&#xff0c;如仅包含数字&#x…...

重装系统之后,电脑连网卡都没反应怎么办?

前言 有些电脑比较奇葩&#xff0c;安装完成之后会出现网卡连驱动都没有&#xff0c;这时候要安装电脑驱动可是真的烦躁。怎么下手呢&#xff1f; 如果确定电脑的网卡型号还好&#xff0c;直接找个电脑下载个对应的网卡驱动&#xff0c;用U盘复制过去就能安装。 但如果不知道…...

【三十五】【算法分析与设计】综合练习(2),22。 括号生成,77。 组合,494。 目标和,模拟树递归,临时变量自动维护树定义,递归回溯,非树结构模拟树

22. 括号生成 数字 n 代表生成括号的对数&#xff0c;请你设计一个函数&#xff0c;用于能够生成所有可能的并且 有效的 括号组合。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xff1a;["&#xff08;&#xff08;&#xff08;&#xff09;&#xff09;&#xff0…...

QT智能指针

一.概述 Qt智能指针是一种能够在不需要手动管理内存的情况下&#xff0c;自动释放资源的指针。它们是C11的std::shared_ptr的一种扩展&#xff0c;可以用于管理Qt对象&#xff0c;尤其是那些不是QObject的对象。 使用智能指针可以避免内存泄露和悬垂指针等问题&#xff0c;同时…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

02.运算符

目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&&#xff1a;逻辑与 ||&#xff1a;逻辑或 &#xff01;&#xff1a;逻辑非 短路求值 位运算符 按位与&&#xff1a; 按位或 | 按位取反~ …...

Python环境安装与虚拟环境配置详解

本文档旨在为Python开发者提供一站式的环境安装与虚拟环境配置指南&#xff0c;适用于Windows、macOS和Linux系统。无论你是初学者还是有经验的开发者&#xff0c;都能在此找到适合自己的环境搭建方法和常见问题的解决方案。 快速开始 一分钟快速安装与虚拟环境配置 # macOS/…...