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

1.6 面试经典150题 - 跳跃游戏



跳跃游戏

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

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

class Solution(object):def canJump(self, nums):""":type nums: List[int]:rtype: bool"""if not nums or len(nums) == 1: return True# 定义左右指针left = 0right = left + 1while right < len(nums):tmp_right = left# 计算本轮最有可以到达的位置for i in range(left, right):pos = i + nums[i]# 可以到达最后一个元素,提前返回if pos >= len(nums) - 1: return Trueif pos > tmp_right: tmp_right = pos# 本轮不能再向右了,返回falseif tmp_right < right: return False# 更新两个指针值left = rightright = tmp_right + 1return True

本题解题思路:

记录两个值:当前位置left,和目前可以到达的最右位置right

每次对区间内的位置进行遍历,找到新的 可以到达的最右位置

如果不能继续向右,则无法到达最后一个节点

如果可以,则更新left 和 right位置,继续遍历

 跳跃游戏II

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

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

  • 0 <= j <= nums[i] 
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]

class Solution(object):def jump(self, nums):""":type nums: List[int]:rtype: int"""if not nums or len(nums) == 1: return 0count = 0left = 0right = left + 1while right < len(nums):count += 1tmp_right = leftfor i in range(left, right):pos = i + nums[i]if pos >= len(nums) - 1: return countif pos > tmp_right: tmp_right = posif tmp_right < right: return -1left = rightright = tmp_right + 1return count

本题对上题略加修改,每次遍历都将计数加1,在上一题返回return的位置,变为返回计数即可。

相关文章:

1.6 面试经典150题 - 跳跃游戏

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

Apache安全及优化

配置第一台虚拟机 VM1网卡 yum仓库 挂载磁盘 上传3个软件包到/目录 到/目录下进行解压缩 tar xf apr-1.6.2.tar.gz tar xf apr-util-1.6.0.tar.gz tar -xjf httpd-2.4.29.tar.bz2 mv apr-1.6.2 httpd-2.4.29/srclib/apr mv apr-util-1.6…...

【话题】边缘计算的挑战和机遇

边缘计算是一种新的计算范式&#xff0c;其核心是在网络边缘处理数据&#xff0c;而不是传统的中心式云计算模式。这种计算方式的兴起得益于物联网&#xff08;IoT&#xff09;的普及和丰富的云服务的成功。 机遇&#xff1a; 响应时间优化&#xff1a;由于数据处理更接近数据…...

react之unpkg.com前端资源加载慢、加载不出

文章目录 react之unpkg.com前端资源加载慢什么是unpkg.com加载慢原因解决方案替换国内cdn在 package.json 中打包进来 react之unpkg.com前端资源加载慢 什么是unpkg.com unpkg 是一个内容源自 npm 的全球快速 CDN。 作为前端开发者&#xff0c;我们对 unpkg 都不陌生&#x…...

C++类与对象【对象模型和this指针】

&#x1f308;个人主页&#xff1a;godspeed_lucip &#x1f525; 系列专栏&#xff1a;C从基础到进阶 &#x1f384;1 C对象模型和this指针&#x1f336;️1.1 成员变量和成员函数分开存储&#x1f336;️1.2 this指针概念&#x1f336;️1.3 空指针访问成员函数&#x1f336;…...

策略模式在工作中的运用

前言 在不同的场景下&#xff0c;执行不同的业务逻辑&#xff0c;在日常工作中是很寻常的事情。比如&#xff0c;订阅系统。在收到阿里云的回调事件、与收到AWS的回调事件&#xff0c;无论是收到的参数&#xff0c;还是执行的逻辑都可能是不同的。为了避免&#xff0c;每次新增…...

【go】依赖倒置demo

文章目录 前言1 项目目录结构&#xff1a;2 初始化函数3 router4 api5 service6 dao7 Reference 前言 为降低代码耦合性&#xff0c;采用依赖注入的设计模式。原始请求路径&#xff1a;router -> api -> service -> dao。请求的为实际方法&#xff0c;具有层层依赖的…...

C++ //练习 2.5 指出下述字面值的数据类型并说明每一组内几种字面值的区别:

C Primer&#xff08;第5版&#xff09; 练习 2.5 练习 2.5 指出下述字面值的数据类型并说明每一组内几种字面值的区别&#xff1a; ( a ) ‘a’, L’a’, “a”, L"a" ( b ) 10, 10u, 10L, 10uL, 012, 0xC ( c ) 3.14, 3.14f, 3.14L ( d ) 10, 10u, 10., 10e-2…...

必示科技助力中国联通智网创新中心通过智能化运维(AIOps)通用能力成熟度3级评估

2023年12月15日&#xff0c;中国信息通信研究院隆重公布了智能化运维AIOps系列标准最新批次评估结果。 必示科技与中国联通智网创新中心合作的“智能IT故障监控定位分析能力建设项目”通过了中国信息通信研究院开展的《智能化运维能力成熟度系列标准 第1部分&#xff1a;通用能…...

python数字图像处理基础(九)——特征匹配

目录 蛮力匹配&#xff08;ORB匹配&#xff09;RANSAC算法全景图像拼接 蛮力匹配&#xff08;ORB匹配&#xff09; Brute-Force匹配非常简单&#xff0c;首先在第一幅图像中选取一个关键点然后依次与第二幅图像的每个关键点进行&#xff08;描述符&#xff09;距离测试&#x…...

k8s的对外服务ingress

1、service的作用体现在两个方面 &#xff08;1&#xff09;集群内部&#xff1a;不断跟踪pod的变化&#xff0c;更新deployment中的pod对象&#xff0c;基于pod的ip地址不断变化的一种服务发现机制 &#xff08;2&#xff09;集群外部&#xff1a;类似于负载均衡器&#xff…...

[足式机器人]Part2 Dr. CAN学习笔记- Kalman Filter卡尔曼滤波器Ch05-3+4

本文仅供学习使用 本文参考&#xff1a; B站&#xff1a;DR_CAN Dr. CAN学习笔记 - Kalman Filter卡尔曼滤波器 Ch05-34 3. Step by step : Deriation of Kalmen Gain 卡尔曼增益/因数 详细推导4. Priori/Posterrori error Covariance Martix 误差协方差矩阵 3. Step by step :…...

关于前端面试中forEach方法的灵魂7问?

目录 前言 一、forEach方法支持处理异步函数吗&#xff1f; 二、forEach方法在循环过程中能中断吗&#xff1f; 三、forEach 在删除自己的元素后能重置索引吗&#xff1f; 四、forEach 的性能相比for循环哪个好&#xff1f; 五、使用 forEach 会不会改变原来的数组&#…...

AI小程序添加深度合成类目解决办法

基于文言一心和gpt等大模型做了一个ai助理小程序&#xff0c;在提交“一点AI助理”小程序时&#xff0c;审核如下&#xff1a; 失败原因1 审核失败原因 你好&#xff0c;你的小程序涉及提供提供文本深度合成技术 (如: AI问答) 等相关服务&#xff0c;请补充选择&#xff1a;深度…...

C/C++ BM6判断链表中是否有环

文章目录 前言题目解决方案一1.1 思路阐述1.2 源码 解决方案二2.1 思路阐述2.2 源码 总结 前言 做了一堆单链表单指针的题目&#xff0c;这次是个双指针题&#xff0c;这里双指针的作用非常明显。 题目 判断给定的链表中是否有环。如果有环则返回true&#xff0c;否则返回fal…...

【Java 设计模式】结构型之适配器模式

文章目录 1. 定义2. 应用场景3. 代码实现结语 适配器模式&#xff08;Adapter Pattern&#xff09;是一种结构型设计模式&#xff0c;用于将一个类的接口转换成客户端期望的另一个接口。这种模式使得原本由于接口不兼容而不能一起工作的类可以一起工作。在本文中&#xff0c;我…...

使用函数计算,数禾如何实现高效的数据处理?

作者&#xff1a;邱鑫鑫&#xff0c;王彬&#xff0c;牟柏旭 公司背景和业务 数禾科技以大数据和技术为驱动&#xff0c;为金融机构提供高效的智能零售金融解决方案&#xff0c;服务银行、信托、消费金融公司、保险、小贷公司等持牌金融机构&#xff0c;业务涵盖消费信贷、小…...

卷积和滤波对图像操作的区别

目录 问题引入 解释 卷积 滤波 问题引入 卷积和滤波是很相似的&#xff0c;都是利用了卷积核进行操作 那么他们之间有什么区别呢&#xff1f; 卷积&#xff1a;会影响原图大小 滤波&#xff1a;不会影响原图大小 解释 卷积 我们用这样一段代码来看 import torch.nn as …...

李沐深度学习-线性回归从零开始

# 核心Tensor&#xff0c;autograd import torch from IPython import display import numpy as np import random from matplotlib import pyplot as pltimport syssys.path.append(路径) from d2lzh_pytorch import * backward()函数:一次小批量执行完在进行反向传播 线性回归…...

CentOS 8.5 安装图解

特特特别的说明 CentOS发行版已经不再适合应用于生产环境&#xff0c;客观条件不得不用的话&#xff0c;优选7.9版本&#xff0c;8.5版本次之&#xff0c;最次6.10版本&#xff08;比如说Oracle 11GR2就建议在6版本上部署&#xff09;&#xff01; 引导和开始安装 选择倒计时结…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...