当前位置: 首页 > 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;同时…...

十大类型学系统性阐释:自感痕迹论的发生学分类体系

十大类型学系统性阐释&#xff1a;自感痕迹论的发生学分类体系引言&#xff1a;类型学作为公理的微分展开一个完备的发生学体系&#xff0c;不应满足于对单一现象的孤立分类。它应当从少数基本公设出发&#xff0c;在不同分析层面自然衍生出互相关联又各具独立性的类型学。自感…...

【Unity 2D实战】巧用Cinemachine Confiner:告别穿帮镜头,实现精准地图边界限制

1. 为什么需要地图边界限制&#xff1f; 在2D游戏开发中&#xff0c;摄像机跟随角色移动是最基础的功能之一。但很多新手开发者都会遇到一个尴尬的问题&#xff1a;当角色走到地图边缘时&#xff0c;摄像机依然会继续移动&#xff0c;导致玩家看到地图之外的空白区域或者未设计…...

人生杠杆具象化的庖丁解牛

它的本质是&#xff1a;**找到那些 投入一次努力&#xff0c;却能产生无限次复用或指数级放大效果 的工具、媒介或关系。它打破了“时间金钱”的线性交换逻辑&#xff0c;实现了 “单位时间产出最大化”。这是一种 从“加法思维”到“乘法思维” 的范式转移。 如果把人生比作物…...

Flutter Provider 状态管理完全指南

Flutter Provider 状态管理完全指南 引言 Provider 是 Flutter 中最流行的状态管理方案之一&#xff0c;它基于 InheritedWidget 实现&#xff0c;提供了简单而强大的状态管理方式。本文将深入探讨 Provider 的各种用法和高级技巧。 基础概念回顾 Provider 类型 Provider - 最基…...

Legacy iOS Kit终极指南:一站式拯救老旧iPhone/iPad的免费工具

Legacy iOS Kit终极指南&#xff1a;一站式拯救老旧iPhone/iPad的免费工具 【免费下载链接】Legacy-iOS-Kit An all-in-one tool to restore/downgrade, save SHSH blobs, jailbreak legacy iOS devices, and more 项目地址: https://gitcode.com/gh_mirrors/le/Legacy-iOS-K…...

还在手动整理ai会议纪要浪费宝贵下班时间?2026年这4款真香AI工具3分钟搞定3小时会议

作为挖了快三年AI效率工具的爱好者&#xff0c;我上周刚被3小时项目复盘会的纪要搞到加班到九点&#xff0c;试了一圈新出的工具&#xff0c;直接给大家上结论&#xff1a;听脑AI是目前同类会议纪要工具里最值得用的&#xff0c;没有之一。 直达链接&#xff1a;https://iting…...

SAP销售单文本处理保姆级教程:用SAVE_TEXT和READ_TEXT BAPI搞定抬头备注

SAP销售单文本处理实战指南&#xff1a;从业务需求到代码实现的完整闭环 销售订单处理过程中&#xff0c;文本信息承载着关键业务逻辑——加急标识、特殊包装要求、客户备注等非结构化数据往往决定了后续物流和财务流程的准确性。当这些信息在流转中丢失时&#xff0c;轻则导致…...

机器学习40讲-13:线性降维主成分的使用

分享一个大牛的人工智能 教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请轻击人工智能教程​​​​​​https://www.captainai.net/troubleshooter 在前一篇文章中,我以岭回归和LASSO为例介绍了线性回归的正则化处理。这两种方法都属于收缩方法(shr…...

终极指南:如何使用Chrome插件markdownReader提升Markdown阅读体验

终极指南&#xff1a;如何使用Chrome插件markdownReader提升Markdown阅读体验 【免费下载链接】markdownReader markdownReader is a extention for chrome, used for reading markdown file. 项目地址: https://gitcode.com/gh_mirrors/ma/markdownReader 还在为浏览器…...

半导体行业成本管理:从学习曲线到EDA工具链的实战策略

1. 行业成本与价格压力的永恒博弈在半导体这个行当里干了十几年&#xff0c;我越来越觉得&#xff0c;我们这行最核心的生存法则&#xff0c;不是什么高深莫测的量子物理&#xff0c;而是一个看似简单、实则残酷的算术题&#xff1a;一边是不断上涨的原材料、设备和设计成本&am…...