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 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i j] 处: …...
【前端】CSS(引入方式+选择器+常用元素属性+盒模型+弹性布局)
文章目录 CSS一、什么是CSS二、语法规范三、引入方式1.内部样式表2.行内样式表3.外部样式 四、选择器1.选择器的种类1.基础选择器:单个选择器构成的1.标签选择器2.类选择器3.id 选择器4.通配符选择器 2.复合选择器1.后代选择器2.子选择器3.并集选择器4.伪类选择器 五…...
迷茫下是自我提升
长夜漫漫,无心睡眠。心中所想,心中所感,忧愁当前,就执笔而下,写下这篇文章。 回忆过往 回想当初为啥学前端,走前端这条路,学校要求嘛,兴趣爱好嘛,还是为了钱。 时间带着…...
用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…...
基于单片机光伏太阳能跟踪系统设计
**单片机设计介绍,基于单片机光伏太阳能跟踪系统设计 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机光伏太阳能跟踪系统的设计,旨在通过单片机技术实现对光伏太阳能设备的自动跟踪,以提高太阳…...
Stable Diffusion 本地化部署
一、前言 最近在家背八股文背诵得快吐了,烦闷的时候,看到使用 AI 进行作图,可以使用本地话部署。刚好自己家里的电脑,之前买来玩暗黑4,配置相对来说来可以,就拿来试试。 此篇是按照 Github 上的 stable-d…...
C++ Algorithm 常用算法
C <algorithm> 头文件是标准库中提供的一系列算法,用于操作范围(range)内的元素。这些算法可以用于数组、容器如vector和list,以及其他满足相应迭代器要求的数据结构。以下是一些常用的C <algorithm> 中的算法及其使用…...
线程安全--深入探究线程等待机制和死锁问题
꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转…...
量子计算获重大突破!微软和Quantinuum将量子计算错误率降低800倍,网友:AI算力的希望
量子计算迎来新突破。 近日,微软和量子计算公司Quantinuum宣布:发现了一种新的量子计算系统,可以将传统量子计算的错误率下降800倍,这让高性能量子计算机走进现实更近了一步。 自生成式AI爆发以来,算力是AI发展面临的…...
WordPress 6.5 “里贾纳”已经发布
WordPress 6.5 “里贾纳”已经发布,其灵感来自著名爵士小提琴家Regina Carter的多才多艺。雷吉娜是一位屡获殊荣的艺术家和著名的爵士乐教育家,以超越流派而闻名,她在古典音乐方面的技术基础和对爵士乐的深刻理解为她赢得了大胆超越小提琴所能…...
甲方安全建设之日志采集实操干货
前言 没有永远的安全,如何在被攻击的情况下,快速响应和快速溯源分析攻击动作是个重要的话题。想要分析攻击者做了什么、怎么攻击进来的、还攻击了谁,那么日志是必不可少的一项,因此我们需要尽可能采集多的日志来进行分析攻击者的…...
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复活”背后的数字永生:被期待成为下一个电商,培育市场认知和用户心智还需时间© 由 九派新闻 提供 数字永生,还是电子宠物?过去一个月,因包小柏用AI技术让爱女在数字世界“复活”一事,《流浪地球2…...
基于单片机钢琴电子节拍器系统设计
**单片机设计介绍,基于单片机钢琴电子节拍器系统设计 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机钢琴电子节拍器系统设计是一个综合性的项目,它结合了单片机编程、音频处理、用户界面设计等多个领域的…...
我的创作纪念日(year Ⅱ)
大家好,我是Kamen Black 君,今天我与大家简单分享一下我两年来在CSDN的创作历程。 print("祝大家每天快乐,love and peace!") 机缘 当初写博客是为了记录一些自己大学中做比赛的心得,没想到自己能走到这一步…...
应急响应实战笔记05Linux实战篇(1)
第1篇:SSH暴力破解 0x00 前言 SSH 是目前较可靠,专为远程登录会话和其他网络服务提供安全性的协议,主要用于给远程登录会话数据进行加密,保证数据传输的安全。SSH口令长度太短或者复杂度不够,如仅包含数字&#x…...
重装系统之后,电脑连网卡都没反应怎么办?
前言 有些电脑比较奇葩,安装完成之后会出现网卡连驱动都没有,这时候要安装电脑驱动可是真的烦躁。怎么下手呢? 如果确定电脑的网卡型号还好,直接找个电脑下载个对应的网卡驱动,用U盘复制过去就能安装。 但如果不知道…...
【三十五】【算法分析与设计】综合练习(2),22。 括号生成,77。 组合,494。 目标和,模拟树递归,临时变量自动维护树定义,递归回溯,非树结构模拟树
22. 括号生成 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例 1: 输入:n 3 输出:["((())࿰…...
QT智能指针
一.概述 Qt智能指针是一种能够在不需要手动管理内存的情况下,自动释放资源的指针。它们是C11的std::shared_ptr的一种扩展,可以用于管理Qt对象,尤其是那些不是QObject的对象。 使用智能指针可以避免内存泄露和悬垂指针等问题,同时…...
C++笔记之pkg-config详解,以及g++、gcc编译时使用pkg-config
C++笔记之pkg-config详解,以及g++、gcc编译时使用pkg-config —— 2024-04-05 code review 文章目录 C++笔记之pkg-config详解,以及g++、gcc编译时使用pkg-config1.pkg-config详解`pkg-config` 的基本用法在 `g++`/`gcc` 编译时使用 `pkg-config`注意事项2.示例C++,普通编译…...
[Apple Vision Pro]开源项目 Beautiful Things App Template
1. 技术框架概述: - Beautiful Things App Template是一个为visionOS设计的免费开源软件(FOSS),用于展示3D模型画廊。 2. 定位: - 该模板作为Beautiful Things网站的延伸,旨在为Apple Vision Pro用户…...
Qt Remote Objects (QtRO) 笔记
简介 Qt Remote Objects (QtRO) 是 Qt 的一个进程间通信模块。 术语 Source 是指提供服务或提供功能供其他程序使用的对象,是 RPC 中的被调用端。 Replica 是指 Source 对象的代理对象,用于 RPC 中的调用端,对 Replica 的调用请求将被转发…...
Unity类银河恶魔城学习记录12-6.5 p128.5 Create item by Craft源代码
此章节在原视频缺失,此过程为根据源代码推断而来,并非原视频步骤 Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释,可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩…...
UE4_如果快速做出毛玻璃效果_假景深
UE4_如果快速做出毛玻璃效果_假景深 2022-08-20 15:02 一个SpiralBlur-SceneTexture材质节点完成效果,启用半透明材质通过修改BlurAmount数值大小调整效果spiralBlur-SceneTexture custom节点,HLSL语言float3 CurColor 0;float2 BaseUV MaterialFloa…...
c# wpf LiveCharts 绑定 简单试验
1.概要 c# wpf LiveCharts 绑定 简单试验 2.代码 <Window x:Class"WpfApp3.Window2"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schem…...
【Kafka】Kafka安装、配置、使用
【Kafka】安装Kafka 1. 安装Kafka2. Kafka使用2.0 集群分发脚本xsync(重要)2.0.1 scp命令2.0.2 rsync远程同步工具2.0.3 写一个集群分发脚本xsync (Shell 脚本) 2.1 Zookeeper安装2.2 对Kafka进行分发2.2.1 执行同步脚本2.2.2 三台云主机配置Kafka环境变量 1. 安装Kafka Kafka…...
2024HW-->Wireshark攻击流量分析
在HW中,最离不开的,肯定是看监控了,那么就要去了解一些wireshark的基础用法以及攻击的流量!!!! 1.Wireshark的基本用法 比如人家面试官给你一段流量包,你要会用 1.分组详情 对于我…...
Lafida多目数据集实测
Lafida 数据集 paper:J. Imaging | Free Full-Text | LaFiDa—A Laserscanner Multi-Fisheye Camera Dataset 官网数据:https://www.ipf.kit.edu/english/projekt_cv_szenen.php 官网:KIT-IPF-Software and Datasets - LaFiDa 标定数据下载&…...
excel wps中编码格式转换
EXCEL报表:另存为CSV格式,转换成UTF-8编码 - 简书 (jianshu.com) 经验证管用...
中国建设教育协会的是假网站吗/seo外包优化
携程目前拥有15000座席,日均电话呼出量30W左右,在如此规模的呼叫中心外呼业务中,我们不断尝试着去降低座席等待时长、提高外呼效率,从而为业务提供更加值得依赖的呼叫中心服务。 作为纯软平台,由携程自主研发的SoftPB…...
研磨材料 东莞网站建设/网站建设公司排名
内容转自“泽平科技”微信公众号,技术咨询请微信搜索“泽平科技” 土壤中的微生物资源非常丰富,原核生物细胞含量大约110^7个/g,但用传统技术培养的微生物仅占微生物总数的0.01%~10%,且大部分微…...
线下广告投放渠道都有哪些/seo技术培训学校
vue实现网页截图 1、首先进行安装html2Canvas npm install html2canvas --save2、然后在需要的vue组件中引入 import html2canvas from "html2canvas";3、先编写一个截图按钮 <el-button class"button-dalod" size"mini" title"生成…...
用群晖做网站/写文的免费软件
解决的问题分布式环境下,希望把用户的操作从并发执行变成原子执行案例:将订单并发变成串行执行, 相比悲观锁来说能够减少数据库的压力。原理redis是单线程的,并发过来的请求,redis都会让他们排队串行执行,r…...
邯郸网站设计公司/谷歌浏览器 安卓下载2023版
设置USB数据监听在Kali Linux中,USB也是作为一个通信端口进行存在。常见的鼠标、键盘、U盘都是通过USB接口传输数据。所以,对于USB接口也可以实施监听,类似网络接口一样。在进行USB数据监听的时候,首先需要加载usbmon模块…...
甘肃省路桥建设集团网站/汽车推广软文
一.xlrd模块 官方文档:https://pypi.org/project/xlrd/ 1.概述 (1)功能: xlrd是用于读取Excel文件数据的Python库,支持支持xlsx和xls格式(2)安装: pip install xlrd2.对象 (1)Excel文件: xlrd.book.Book()##############################################################…...