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

45 55跳跃游戏解题记录

先是55跳跃游戏,暴力解法会怎样?会超出时间限制,而且有很多细节要注意:

func canJump(nums []int) bool {// 处理空数组情况,当nums只剩一个元素时,nums[i:]导致越界。if len(nums) == 0 {return false}// 如果只有一个元素,已经到达终点if len(nums) == 1 {return true}i := nums[0]if i == 0 { // 如果第一步就不能跳,且不是终点,则失败return false}// 尝试所有可能的跳跃步数for ; i>0; i-- {// 确保不会越界if i < len(nums) {if canJump(nums[i:]) { // 将剩余没判断的切片递归return true}}}return false
}

时间复杂度是O(n^n)。对于这个问题,更高效的解法是贪心算法。但是为什么是贪心呢,需要想我们只管跳得更远,比它近的地方一定是可以到达的。于是我需要遍历数组每个值,去维护一个能到达的最大长度。

func canJump(nums []int) bool {sum := 0for i, v := range nums {if sum < i { // sum已经是最远距离了,还不可达当前indexreturn false}if sum >= len(nums)-1 { // 已经到达或者超出最后一个index了return true }if sum < i+v {sum = i+v // 更新最长长度}}return false
}

45跳跃游戏二说的是一定可以到达,但是求最少跳几次。那不也是贪心贪的每一跳尽量远吗?那我记录一下上次贪心的次数。

func jump(nums []int) int {count := 0sum := 0for i, v := range nums {if sum >= len(nums)-1 { // 已经到达或者超出最后一个index了return count}if sum < i+v {sum = i+v // 更新最长长度count++}}return count
}

**然后错了。**我才反应过来,我不是要贪总的距离,这次我要贪每一跳尽量远。也就是每一跳都选择那一跳覆盖范围内的跳最远的,就能实现最少次数。

func jump(nums []int) int {count := 0i := 0for i < len(nums)-1 {// 避免越界, 如果当前位置本身就能从起点跳到终点if i+nums[i] >= len(nums)-1 {count += 1return count}// 还要找一个有潜力的落脚点,找到能去的落脚点中最远的那个maxi := i+1for j:=2; j<=nums[i]; j++ {if maxi+nums[maxi] < i+j+nums[i+j]{maxi = i+j}}i = maxi count += 1}return count
}

相关文章:

45 55跳跃游戏解题记录

先是55跳跃游戏&#xff0c;暴力解法会怎样&#xff1f;会超出时间限制&#xff0c;而且有很多细节要注意&#xff1a; func canJump(nums []int) bool {// 处理空数组情况&#xff0c;当nums只剩一个元素时&#xff0c;nums[i:]导致越界。if len(nums) 0 {return false}// 如…...

一个简单的用C#实现的分布式雪花ID算法

雪花ID是一个依赖时间戳根据算法生成的一个Int64的数字ID&#xff0c;一般用来做主键或者订单号等。以下是一个用C#写的雪花ID的简单实现方法 using System; using System.Collections.Concurrent; using System.Diagnostics;public class SnowflakeIdGenerator {// 配置常量p…...

16个气象数据可视化网站整理分享

好的&#xff01;以下是关于“16个气象数据可视化网站整理分享”的软文&#xff1a; 16个气象数据可视化网站整理分享 气象数据可视化已成为现代气象研究、决策支持以及公众天气服务的重要组成部分。从天气预报到气候变化监测&#xff0c;全球许多气象数据可视化平台为专业人士…...

一周学会Flask3 Python Web开发-SQLAlchemy数据迁移migrate

锋哥原创的Flask3 Python Web开发 Flask3视频教程&#xff1a; 2025版 Flask3 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili 模型类(表)不是一成不变的&#xff0c;当你添加了新的模型类&#xff0c;或是在模型类中添加了新的字段&#xff0c;甚至是修改…...

[原创](Modern C++)现代C++的关键性概念: 如何利用多维数组的指针安全地遍历所有元素

[作者] 常用网名: 猪头三 出生日期: 1981.XX.XX 企鹅交流: 643439947 个人网站: 80x86汇编小站 编程生涯: 2001年~至今[共24年] 职业生涯: 22年 开发语言: C/C、80x86ASM、Object Pascal、Objective-C、C#、R、Python、PHP、Perl、 开发工具: Visual Studio、Delphi、XCode、C …...

本地化智能运维助手:基于 LangChain 数据增强 和 DeepSeek-R1 的K8s运维文档检索与问答系统 Demo

写在前面 博文内容为基于 LangChain 数据增强 和 Ollams 本地部署 DeepSeek-R1实现 K8s运维文档检索与问答系统 Demo通过 Demo 对 LEDVR 工作流&#xff0c; 语义检索有基本认知理解不足小伙伴帮忙指正 &#x1f603;,生活加油 我看远山&#xff0c;远山悲悯 持续分享技术干货…...

中间件框架漏洞攻略

中间件&#xff08;英语&#xff1a;Middleware&#xff09;是提供系统软件和应⽤软件之间连接的软件&#xff0c;以便于软件各部件之间的沟通。 中间件处在操作系统和更⾼⼀级应⽤程序之间。他充当的功能是&#xff1a;将应⽤程序运⾏环境与操作系统隔离&#xff0c;从⽽实…...

在 Ubuntu 上安装 Docker 的完整指南

1. 卸载旧版本(如有) 在安装新版本前,建议先卸载旧版本: sudo apt remove docker docker-engine docker.io containerd runc 2. 安装依赖包 更新软件包索引并安装必要的依赖: sudo apt update sudo apt install -y ca-certificates curl gnupg lsb-release 3. 添加 Do…...

Another Redis Desktop Manager下载安装使用

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Another Redis Desktop Manager下载安装使用…...

GitLab 中文版17.10正式发布,27项重点功能解读【一】

GitLab 是一个全球知名的一体化 DevOps 平台&#xff0c;很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab 是 GitLab 在中国的发行版&#xff0c;专门为中国程序员服务。可以一键式部署极狐GitLab。 学习极狐GitLab 的相关资料&#xff1a; 极狐GitLab 官网极狐…...

mysql慢查询日志

在 MySQL 中&#xff0c;慢查询日志&#xff08;Slow Query Log&#xff09;用于记录执行时间超过指定阈值的 SQL 语句。通过分析慢查询日志&#xff0c;可以优化数据库性能。以下是查看和配置 MySQL 慢查询日志的详细步骤&#xff1a; 1. 检查慢查询日志是否已启用 登录 MySQ…...

unity 截图并且展现在UI中

using UnityEngine; using UnityEngine.UI; using System.IO; using System.Collections.Generic; using System; using System.Collections;public class ScreenshotManager : MonoBehaviour {[Header("UI 设置")]public RawImage latestScreenshotDisplay; // 显示…...

Linux上位机开发实践(MPP平台的核心构成)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 芯片行业是一个赢者通吃的行业。也就是说细分领域的前两名&#xff0c;相比较后来者而言&#xff0c;拥有很多无可比拟的优势。以安防市场的soc来说…...

Hosts文件与DNS的关系:原理、应用场景与安全风险

目录 引言 Hosts文件与DNS的基本概念 2.1 什么是Hosts文件&#xff1f; 2.2 什么是DNS&#xff1f; Hosts文件与DNS的关系 Hosts文件的应用场景 4.1 本地开发与测试 4.2 屏蔽广告与恶意网站 4.3 绕过DNS污染或劫持 Hosts文件的优势 5.1 解析速度快 5.2 不受DNS缓存影…...

Stable Diffusion vue本地api接口对接,模型切换, ai功能集成开源项目 ollama-chat-ui-vue

1.开启Stable Diffusion的api服务 编辑webui-user.bat 添加 –api 开启api服务&#xff0c;然后保存启动就可以了 2.api 文档地址 http://127.0.0.1:7860/docs3. 文生图 接口 地址 /sdapi/v1/txt2img //post 请求入参 {enable_hr: false, // 开启高清hrdenoising_stre…...

【含文档+源码】基于SpringBoot的过滤协同算法之网上服装商城设计与实现

项目介绍 本课程演示的是一款 基于SpringBoot的过滤协同算法之网上服装商城设计与实现&#xff0c;主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的 Java 学习者。 1.包含&#xff1a;项目源码、项目文档、数据库脚本、软件工具等所有资料 2.带你从零开始部署…...

优化 Docker 构建之方法(Methods for Optimizing Docker Construction)

优化 Docker 构建之方法 优化 Docker 构建不仅是为了提高效率&#xff0c;它还是降低部署成本、确保安全性和保持跨环境一致性的有效方法。每个层、依赖项和配置选择都会影响镜像的大小、安全性和可维护性。大型镜像部署速度较慢且消耗更多资源&#xff0c;这会增加成本&#…...

谈谈空间复杂度考量,特别是递归调用栈空间消耗?

空间复杂度考量是算法设计的核心要素之一&#xff0c;递归调用栈的消耗问题在前端领域尤为突出。 以下结合真实开发场景进行深度解析&#xff1a; 一、递归调用栈的典型问题 1. 深层次DOM遍历的陷阱 // 危险操作&#xff1a;递归遍历未知层级的DOM树 function countDOMNode…...

四川省汽车加气站操作工备考题库及答案分享

1.按压力容器的设计压力分为&#xff08; &#xff09;个压力等级。 A. 三 B. 四 C. 五 D. 六 答案&#xff1a;B。解析&#xff1a;按压力容器的设计压力分为低压、中压、高压、超高压四个压力等级。 2.缓冲罐的安装位置在天然气压缩机&#xff08; &#xff09;。 A. 出口处 …...

《探秘SQL的BETWEEN:解锁数据范围查询的深度奥秘》

在数据的广袤宇宙中&#xff0c;结构化查询语言&#xff08;SQL&#xff09;宛如一座精密的导航系统&#xff0c;引导我们穿越数据的浩瀚星河&#xff0c;精准定位所需信息。其中&#xff0c;BETWEEN作为SQL的关键工具之一&#xff0c;以其独特的能力&#xff0c;在数据的海洋里…...

AppArmor 使用说明

目录 一&#xff1a;AppArmor 功能介绍二&#xff1a;AppArmor 配置介绍1、AppArmor 配置文件存放路径2、AppArmor 配置文件命名规则 三&#xff1a; AppArmor 工作模式1、AppArmor 两种工作模式2、查看当前进程的工作模式3、给指定进程切换工作模式4、重新加载配置文件生效 四…...

Linux的一些常见指令

一、ls指令 语法&#xff1a; ls (选项) 功能&#xff1a; ls可以查看当前目录下的所有文件和目录。 常用选项&#xff1a; -a:列出目录下的所有文件&#xff0c;包括以点&#xff08;.&#xff09;开头的隐含文件 。-d:将目录像文件一样显示&#xff0c;不显示其下的文件。…...

MATLAB中getfield函数用法

目录 语法 说明 示例 访问标量结构体的字段 嵌套结构体的字段 结构体数组元素的字段 嵌套结构体数组的索引 字段的元素 getfield函数的功能是结构体数组字段。 语法 value getfield(S,field) value getfield(S,field1,...,fieldN) value getfield(S,idx,field1,..…...

算法 | 河马优化算法原理,公式,应用,算法改进及研究综述,matlab代码

以下是关于河马优化算法(Hippopotamus Optimization Algorithm, HO)的完整综述,包含原理、公式、应用场景、改进方向及可直接运行的 Matlab 完整代码。一、算法原理 河马优化算法(HO)由Amiri等人于2024年提出,是受河马群体行为启发的元启发式算法,其核心基于以下三阶段行…...

Oracle到MySQL实时数据互通:透明网关跨库查询终极方案

技术架构概述 节点类型IP示例Oracle数据库172.18.0.11透明网关节点192.168.5.20MySQL数据库10.10.8.100 提示&#xff1a;透明网关支持部署在Oracle服务器实现集中式管理 一、MySQL环境准备 1. ODBC驱动部署 从MySQL官网获取对应版本的ODBC驱动&#xff1a; # 企业版推荐使…...

BAPLIE船图文件:EDI 核心字段与应用场景解析

BAPLIE&#xff08;Bay Plan/Stowage Plan Occupied and Empty Locations Message&#xff09;作为EDIFACT国际报文标准&#xff08;D96A版本&#xff09;的核心成员&#xff0c;是集装箱海运领域实现船舶配载数字化的关键工具。其通过结构化数据精确描述集装箱在船舶上的物理位…...

C#中获取字节数据的高字节和低字节

字节顺序(Endianness)&#xff1a; 1.小端序(Little-Endian)&#xff1a;低字节在前&#xff08;x86架构&#xff09; 2.大端序(Big-Endian)&#xff1a;高字节在前&#xff08;网络字节序&#xff09; 特性小端序&#xff08;Little-Endian&#xff09;大端序&#xff08;B…...

26考研——查找_树形查找_二叉排序树(BST)(7)

408答疑 文章目录 三、树形查找二叉排序树&#xff08;BST&#xff09;二叉排序树中结点值之间的关系二叉树形查找二叉排序树的查找过程示例 向二叉排序树中插入结点插入过程示例 构造二叉排序树的过程构造示例 二叉排序树中删除结点的操作情况一&#xff1a;被删除结点是叶结点…...

OpenCV图像拼接(5)图像拼接模块的用于创建权重图函数createWeightMap()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 cv::detail::createWeightMap 是 OpenCV 库中用于图像拼接模块的一个函数&#xff0c;主要用于创建权重图。这个权重图在图像拼接过程中扮演着重…...

【Unity】 鼠标拖动物体移动速度跟不上鼠标,会掉落

错误示范&#xff1a; 一开始把移动的代码写到update里去了&#xff0c;发现物体老是掉(总之移动非常不流畅&#xff0c;体验感很差&#xff09; void Update(){Ray ray Camera.main.ScreenPointToRay(Input.mousePosition);if (Physics.Raycast(ray, out RaycastHit hit, M…...

docker网桥问题导致ldap组件安装失败分析解决

使用pass_install_x86_64_0124版部署k8s底座、kem&#xff1b; 问题&#xff1a;一台kem节点部署ldap组件失败 解决&#xff1a;恢复问题主机的docker0网卡&#xff0c;重新部署kem相关组件 二、问题详情 现象描述 ansible部署kem组件 TASK [kem : start ldap] **********…...

如何保障kafka的数据不会重复消费呢,如何防止漏掉呢

在 Kafka 中保障数据不重复消费且不丢失&#xff0c;需要从生产者、消费者和 Kafka 自身配置三个层面综合设计。以下是具体实现方案&#xff1a; 一、防止数据重复消费 1. 消费者端控制 手动提交 Offset 禁用自动提交&#xff08;enable.auto.commitfalse&#xff09;&#x…...

mac vim命令快捷键

目录 移动光标插入模式复制/粘贴删除搜索/替换退出 移动光标 快捷键说明0 / ^跳到行首&#xff0c;移动到光标所在行的"行首"$跳到行末&#xff0c;移动到光标所在行的"行尾"gg跳到文件第一行G移动到文章的最后[n]G跳到第n行w光标跳到下个字的开头e光标跳…...

【01】噩梦终结flutter配安卓android鸿蒙harmonyOS 以及next调试环境配鸿蒙和ios真机调试环境-flutter项目安卓环境配置

噩梦终结&#xff1a;Flutter 配安卓、鸿蒙、iOS 真机调试环境 问题背景 很多开发者在配置 Flutter 项目环境时遇到困难&#xff0c;尤其是在处理 Android、鸿蒙和 iOS 真机调试环境时。卓伊凡最近接手了一个项目&#xff0c;发现很多“专业程序员”在环境搭建上花费了大量时…...

React 中React.memo的作用,如何利用它进行组件性能优化?

大白话React 中React.memo的作用&#xff0c;如何利用它进行组件性能优化&#xff1f; React.memo 是啥玩意儿 在 React 里&#xff0c;组件渲染是很频繁的事儿。每次父组件状态变了&#xff0c;子组件就可能会重新渲染&#xff0c;哪怕子组件的 props 压根儿没变化。这就好比…...

Python实现图片文字识别-OCR

PaddleOCR是由百度飞桨&#xff08;PaddlePaddle&#xff09;团队开发的OCR工具库&#xff0c;它包含超轻量级的中文OCR模型&#xff0c;支持多种语言和复杂情况下的文字识别。 pip install paddlepaddle paddleocr使用&#xff1a;已知我的图片是 img.png from paddleocr imp…...

MCP Server 实现一个 天气查询

​ Step1. 环境配置 安装 uv curl -LsSf https://astral.sh/uv/install.sh | shQuestion: 什么是 uv 呢和 conda 比有什么区别&#xff1f; Answer: 一个用 Rust 编写的超快速 (100x) Python 包管理器和环境管理工具&#xff0c;由 Astral 开发。定位为 pip 和 venv 的替代品…...

第38周:文献阅读

目录 摘要 Abstract 文献阅读 问题引入 研究背景 研究意义 研究目的 相关工作 自回归循环网络 基于 GAN 的序列生成方法 时间序列表示学习 创新点 提出模型 基本原理 代码实现 实验研究 实验1——基准和评估 实验2——不同类型的时间序列数据 实验3——…...

CD19.【C++ Dev】类和对象(10) 日期类对象的成员函数(日期+天数)

目录 日期天数 需要考虑的几个问题 1.天数加在日上,有可能会溢出,需要进位 2.对月进位,也有可能导致月会溢出,需要进位 3.对年进位,需要考虑是否为闰年 代码设计 取得指定月的天数GetMonthDay函数 方法1:if判断或switch/case 方法2:查表 版本1 版本2 operator 初始…...

Linux安装MySQL数据库并使用C语言进行数据库开发

目录 一、前言 二、安装VMware运行Ubuntu 1.安装VMware 2.使用VMware打开Ubuntu 三、配置VMware使用网卡 1.添加NAT网卡 四、Linux下安装MySQL数据库 五、安装MySQL开发库 六、演示代码 sql_connect.c sql_connect.h main.c中数据库相关代码 结尾 一、前言 由于最…...

GStreamer —— 3.1、Qt+GStreamer制作多功能播放器,支持本地mp4文件、rtsp流、usb摄像头等(可跨平台,附源码)

🔔 GStreamer 相关音视频技术、疑难杂症文章合集(掌握后可自封大侠 ⓿_⓿)(记得收藏,持续更新中…) 运行效果...

如何在根据名称或id找到json里的节点以及对应的所有的父节点?

函数如下&#xff1a; 数据如下&#xff1a; [{ "name": "数据看板", "id": "data", "pageName": "tableeauData", "list": [] }, { "name": "审计模块", "id": &quo…...

IP第一次笔记

一、TCP协议 第0步&#xff1a;如果浏览器和host文件存在域名对应的P地址记录关系 则直接封装HTTP数据报文&#xff0c;如果没有记录则触发DNS解析获 取目标域名对应的P地址 第一步&#xff1a;终端主机想服务器发起TCP三次握手 1.TCP的三次握手 2.传输网页数据 HTTP --应用层…...

手机硬件检测详解:从版本信息到相机功能的全面指南

手机硬件检测概述 接下来&#xff0c;我们将为您提供一份详尽的手机硬件检测指南&#xff0c;涵盖三十项关键内容&#xff0c;助您轻松掌握手机硬件的检测技巧。对于开发者而言&#xff0c;在测试手机硬件性能时&#xff0c;可以结合使用克魔开发助手&#xff08;Keymob&#…...

大数据学习(86)-Zookeeper去中心化调度

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

05-SpringBoot3入门-整合SpringMVC(配置静态资源、拦截器)

1、说明 在01-SpringBoot3入门-第一个项目-CSDN博客中&#xff0c;其实就已经整合了SpringMVC。下面讲解怎么配置静态资源和拦截器 2、配置静态资源 命名&#xff1a;static&#xff08;文件夹&#xff09; 位置&#xff1a;src/main/resources 编写一个html文件 访问 http:/…...

大数据学习(88)-zookeeper实现的高可用(HA)

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

自然语言处理(5)—— 中文分词

中文分词的基本原理及实现 1. 什么是词2. 基本原理3. 发展趋势&#xff1a;多数场景无需显式分词 信息处理的目标是使用计算机能够理解和产生自然语言。而自然语言理解和产生的前提是对语言能够做出全面的解析。 汉语词汇是语言中能够独立运用的最小的语言单位&#xff0c;是语…...

MP4音视频格式

1.MP4 MP4是一种用于封装音视频/字幕/图片/章节信息等数据的多媒体容器格式&#xff0c;是MPEG-4系列的成员之一 2.文件结构 MP4由一层层的嵌套Box&#xff08;atom&#xff09;组成 [ size (4 bytes) ][ type (4 bytes)][ payload (嵌套box或者数据) ] 3.常见Box 类型名称…...

NO.59十六届蓝桥杯备战|基础算法-前缀和|一维前缀和|最大子段和|二维前缀和|激光炸弹(C++)

前缀和与差分的核⼼思想是预处理&#xff0c;可以在暴⼒枚举的过程中&#xff0c;快速给出查询的结果&#xff0c;从⽽优化时间复杂度。 是经典的⽤空间替换时间的做法 前缀和 解法1&#xff1a;暴力模拟&#xff0c;q有几次&#xff0c;就套几次for循环 解法2&#xff1a;前…...