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

【面试经典150题】跳跃游戏

题目链接

给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false

  • 1 <= nums.length <= 1 0 4 10^4 104
  • 0 <= nums[i] <= 1 0 5 10^5 105

分析:

假设当前位于nums[i],表示该元素后面的nums[i]个元素任我跳,那该跳哪个呢?

是不是得考虑跳到哪一个位置下下一步可以跳得更远。这个由index+nums[i]决定。

也就是说后面的nums[i]个元素里,哪个索引+元素值最大就跳到哪里。

/*** @param {number[]} nums* @return {boolean}*/
var canJump = function (nums) {let i = 0;let nextIndex;let maxVal = 0;while (i + nums[i] < nums.length - 1) {if (nums[i] === 0) {return false;}for (let j = i + 1; j <= i + nums[i]; j++) {if (j + nums[j] > maxVal) {nextIndex = j;maxVal = j + nums[j];}}maxVal = 0;i = nextIndex;}return true;
};

时间复杂度: O ( n 2 ) O(n^2) O(n2)

空间复杂度: O ( 1 ) O(1) O(1)

时间复杂度太高,换个思路:

维护一个最大可达位置maxReach。

/*** @param {number[]} nums* @return {boolean}*/
var canJump = function (nums) {let maxReach=0;for(let i=0;i<nums.length;i++){if(i>maxReach){return false;}maxReach=Math.max(maxReach,i+nums[i]);if(maxReach>=nums.length-1){return true;}}return true;
};

时间复杂度: O ( n ) O(n) O(n)

空间复杂度: O ( 1 ) O(1) O(1)

相关文章:

【面试经典150题】跳跃游戏

题目链接 给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 1 < nums…...

【Rust】003-基础语法:流程控制

【Rust】003-基础语法&#xff1a;流程控制 文章目录 【Rust】003-基础语法&#xff1a;流程控制一、概述二、if 表达式1、语法格式2、多个3、获取表达式的值 三、循环1、loop&#xff1a;无限循环&#xff0c;可跳出无限循环跳出循环返回值 2、while&#xff1a;条件循环&…...

0829【综述】面向时空数据的区块链研究综述

摘要:时空数据包括时间和空间2个维度,常被应用于物流、供应链等领域。传统的集中式存储方式虽然具有一定的便捷性,但不能充分满足时空数据存储及查询等要求,而区块链技术采用去中心化的分布式存储机制,并通过共识协议来保证数据的安全性。研究现有区块链1.0、2.0和以Block-DAG为…...

MySQL高级篇(SQL优化、索引优化、锁机制、主从复制)

目录 0 存储引擎介绍1 SQL性能分析2 常见通用的JOIN查询 SQL执行加载顺序七种JOIN写法3 索引介绍 3.1 索引是什么3.2 索引优劣势3.3 索引分类和建索引命令语句3.4 索引结构与检索原理3.5 哪些情况适合建索引3.6 哪些情况不适合建索引4 性能分析 4.1 性能分析前提知识4.2 Expla…...

YOLOV8模型使用-检测-物体追踪

这个最新的物体检测模型&#xff0c;很厉害的样子&#xff0c;还有物体追踪的功能。 有官方的Python代码&#xff0c;直接上手试试就好&#xff0c;至于理论&#xff0c;有想研究在看论文了╮(╯_╰)╭ 简单介绍 YOLOv8 中可用的模型 YOLOv8 模型的每个类别中有五个模型用于检…...

springmvc:设置后端响应给前端的json数据转换成String格式

设置spring-mvc.xml: xml <?xml version"1.0" encoding"UTF-8"?> <beans xmlns"http://www.springframework.org/schema/beans"xmlns:context"http://www.springframework.org/schema/context"xmlns:xsi"http://www.w…...

Mac安装brew、mysql、redis

mac安装brew mac安装brewmac安装mysql并配置开机启动mac安装redis并配置开机启动 mac安装brew 第一步&#xff1a;执行. /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"第二步&#xff1a;输入开机密码 第三…...

MLC-LLM 部署RWKV World系列模型实战(3B模型Mac M2解码可达26tokens/s)

0x0. 前言 我的 ChatRWKV 学习笔记和使用指南 这篇文章是学习RWKV的第一步&#xff0c;然后学习了一下之后决定自己应该做一些什么。所以就在RWKV社区看到了这个将RWKV World系列模型通过MLC-LLM部署在各种硬件平台的需求&#xff0c;然后我就开始了解MLC-LLM的编译部署流程和…...

Unity 之 参数类型之值类型参数的用法

文章目录 基本数据类型结构体结构体的进一步补充 总结&#xff1a; 当谈论值类型参数时&#xff0c;我们可以从基本数据类型和结构体两个方面详细解释。值类型参数指的是以值的形式传递给函数或方法的数据&#xff0c;而不是引用。 基本数据类型 基本数据类型的值类型参数&…...

VScode远程连接主机

一、前期准备 1、Windows安装VSCode&#xff1b; 2、在VSCode中安装PHP Debug插件&#xff1b; 3、安装好Docker 4、在容器中安装Xdebug ①写一个展现phpinfo的php文件 <?php phpinfo(); ?>②在浏览器上打开该文件 ③复制所有信息丢到Xdebug: Installation instr…...

【iOS】属性关键字

文章目录 前言一、深拷贝与浅拷贝1、OC的拷贝方式有哪些2. OC对象实现的copy和mutableCopy分别为浅拷贝还是深拷贝&#xff1f;3. 自定义对象实现的copy和mutableCopy分别为浅拷贝还是深拷贝&#xff1f;4. 判断当前的深拷贝的类型&#xff1f;(区别是单层深拷贝还是完全深拷贝…...

【计算机基础】Git从安装到使用,详细每一步!扩展Github\Gitlab

&#x1f4e2;&#xff1a;如果你也对机器人、人工智能感兴趣&#xff0c;看来我们志同道合✨ &#x1f4e2;&#xff1a;不妨浏览一下我的博客主页【https://blog.csdn.net/weixin_51244852】 &#x1f4e2;&#xff1a;文章若有幸对你有帮助&#xff0c;可点赞 &#x1f44d;…...

深入了解Docker镜像操作

Docker是一种流行的容器化平台&#xff0c;它允许开发者将应用程序及其依赖项打包成容器&#xff0c;以便在不同环境中轻松部署和运行。在Docker中&#xff0c;镜像是构建容器的基础&#xff0c;有些家人们可能在服务器上对docker镜像的操作命令不是很熟悉&#xff0c;本文将深…...

嵌入式开发-单片机学习介绍

一、单片机入门篇 单片机的定义和历史 单片机是一种集成了微处理器、存储器、输入输出接口和其他功能于一体的微型计算机&#xff0c;具有高度的集成性和便携性。单片机的历史可以追溯到20世纪70年代&#xff0c;随着微电子技术的不断发展&#xff0c;单片机逐渐成为了工业控…...

5、Spring之Bean生命周期源码解析(销毁)

Bean的销毁过程 Bean销毁是发送在Spring容器关闭过程中的。 在Spring容器关闭时,比如: AnnotationConfigApplicationContext context = new AnnotationConfigApplicationContext(AppConfig.class); UserService userService = (UserService) context.getBean("userSe…...

开发多点触控MFC应用程序

当下计算机变得越来越智能化&#xff0c;越来越无所不能&#xff0c;触摸屏的普及只是时间问题了。 虽然鼠标和键盘不会很快就离开人们的视野&#xff0c;毕竟人们使用鼠标跟键盘已经成为一种习惯&#xff0c;但是处理信息或者说操作计算机的其他方法也层出不穷——比如触控技术…...

使用nlohmann json库进行序列化与反序列化

nlohmann源码仓库&#xff1a;https://github.com/nlohmann/json使用方式&#xff1a;将其nlohmann文件夹加入&#xff0c;包含其头文件json.hpp即可demo #include <iostream> #include "nlohmann/json.hpp" #include <vector>using json nlohmann::js…...

高教社杯数模竞赛特辑论文篇-2012年A题:葡萄酒的评价(附获奖论文)

目录 摘 要 一、问题重述 二、问题分析 2.1 问题一的分析 2.2 问题二的分析...

手写RPC——数据序列化工具protobuf

手写RPC——数据序列化工具protobuf Protocol Buffers&#xff08;protobuf&#xff09;是一种用于结构化数据序列化的开源库和协议。下面是 protobuf 的一些优点和缺点&#xff1a; 优点&#xff1a; 高效的序列化和反序列化&#xff1a;protobuf 使用二进制编码&#xff0c…...

【MATLAB第70期】基于MATLAB的LightGbm(LGBM)梯度增强决策树多输入单输出回归预测及多分类预测模型(全网首发)

【MATLAB第70期】基于MATLAB的LightGbm(LGBM)梯度增强决策树多输入单输出回归预测及多分类预测模型&#xff08;全网首发&#xff09; 一、学习资料 (LGBM)是一种基于梯度增强决策树(GBDT)算法。 本次研究三个内容&#xff0c;分别是回归预测&#xff0c;二分类预测和多分类预…...

3个突破限制步骤:res-downloader让网络资源获取变得无拘无束

3个突破限制步骤&#xff1a;res-downloader让网络资源获取变得无拘无束 【免费下载链接】res-downloader 视频号、小程序、抖音、快手、小红书、直播流、m3u8、酷狗、QQ音乐等常见网络资源下载! 项目地址: https://gitcode.com/GitHub_Trending/re/res-downloader 在数…...

CasADi实战:用Python搞定机器人路径规划中的数值优化问题(附IPOPT配置)

CasADi实战&#xff1a;用Python搞定机器人路径规划中的数值优化问题&#xff08;附IPOPT配置&#xff09; 机器人路径规划的核心在于如何在复杂环境中找到一条既安全又高效的轨迹。这本质上是一个带约束的数值优化问题——我们需要最小化某种代价函数&#xff08;如路径长度或…...

告别Swagger注解污染:用smart-doc + Maven插件5分钟生成整洁API文档(SpringBoot实战)

零侵入API文档革命&#xff1a;smart-doc在SpringBoot项目中的极致实践 如果你曾经被Swagger注解污染代码所困扰&#xff0c;或是厌倦了在业务逻辑中嵌入大量文档相关注解&#xff0c;那么smart-doc可能会成为你API文档管理的新选择。作为一款基于源码解析的文档生成工具&#…...

Axure 9.0 原生组件:绘制折线图

引言在原型设计中&#xff0c;数据可视化是传递核心信息的关键手段&#xff0c;而折线图凭借 “清晰展示数据趋势” 的优势&#xff0c;广泛应用于销售波动、用户增长、指标变化等场景。Axure 9.0 作为主流原型工具&#xff0c;虽未内置现成折线图组件&#xff0c;但通过「形状…...

无噪音RS1 ROSAHL 电解式除湿器 3D 打印耗材盒/户外摄像头/激光器精准除湿设备

RS1 是 ROSAHL&#xff08;日本 Ryosai Technica 生产&#xff09;推出的一款超紧凑型电解式除湿器&#xff0c;采用全球领先的固体聚合物电解质&#xff08;SPE&#xff09;膜技术&#xff0c;通过电化学原理主动将密闭空间内的水分子分解并以气态形式排出。它具备无噪音、无振…...

颠覆中文字体困境:思源宋体CN 7字重开源方案深度解析

颠覆中文字体困境&#xff1a;思源宋体CN 7字重开源方案深度解析 【免费下载链接】source-han-serif-ttf Source Han Serif TTF 项目地址: https://gitcode.com/gh_mirrors/so/source-han-serif-ttf 价值主张&#xff1a;破解中文字体的"三重枷锁" 在数字设计…...

GPEN肖像增强使用技巧:自然、强力、细节三种模式适用场景解析

GPEN肖像增强使用技巧&#xff1a;自然、强力、细节三种模式适用场景解析 1. 认识GPEN的三种处理模式 GPEN作为当前最先进的肖像增强工具之一&#xff0c;其核心价值在于提供了三种差异化的处理模式&#xff1a;自然、强力和细节。这三种模式不是简单的强度差异&#xff0c;而…...

Palo Alto PAN-OS 12.1.5 VM-Series for ESXi, KVM - 基于机器学习的下一代防火墙操作系统

Palo Alto PAN-OS 12.1.5 Orion 发布 - 基于机器学习的下一代防火墙操作系统 PAN-OS 12.1 Orion delivers industry firsts including quantum readiness, unified multi-cloud protection, and more. 请访问原文链接&#xff1a;https://sysin.org/blog/pan-os-12/ 查看最新…...

如何用Captum实现多任务学习解释:复杂模型的归因策略终极指南

如何用Captum实现多任务学习解释&#xff1a;复杂模型的归因策略终极指南 【免费下载链接】captum Model interpretability and understanding for PyTorch 项目地址: https://gitcode.com/gh_mirrors/ca/captum Captum是一个基于PyTorch的模型可解释性库&#xff0c;专…...

如何通过Crowbar实现游戏模组开发全流程效率提升

如何通过Crowbar实现游戏模组开发全流程效率提升 【免费下载链接】Crowbar Crowbar - GoldSource and Source Engine Modding Tool 项目地址: https://gitcode.com/gh_mirrors/crow/Crowbar 在游戏开发领域&#xff0c;技术门槛常成为创意落地的阻碍。Crowbar作为针对Go…...