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

LeetCode1871 跳跃游戏VII

news 来源：原创 2025/8/21 15:36:16

LeetCode 跳跃游戏 IV：二进制字符串的跳跃问题

题目描述

给定一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump。初始时，你位于下标 0 处（保证该位置为 '0'）。你需要判断是否能到达字符串的最后一个位置（下标为 s.length - 1）。移动规则如下：

从位置 i 移动到 j，需满足 i + minJump ≤ j ≤ min(i + maxJump, s.length - 1)。
目标位置 j 必须为 '0'。

解题思路分析

动态规划 + 前缀和优化

核心思想

动态规划数组 dp：dp[i] 表示是否能到达位置 i。
前缀和数组 pre：记录从 0 到当前位置的可达状态总和，用于快速计算区间和。
有效区间：对于位置 j，其可跳跃的起始位置范围为 [j - maxJump, j - minJump]。通过前缀和数组快速判断该区间内是否有可达的位置。

关键步骤

初始化：
- 若最后一个字符为 '1'，直接返回 false。
- dp[0] = true（初始位置可达）。
- 前缀和数组 pre 记录可达位置的累计数量。
遍历每个位置 j：
- 若当前位置为 '1'，跳过。
- 计算可跳跃的起始位置范围 [left, right]。
- 利用前缀和数组快速查询该区间内是否有可达位置。
- 更新 dp[j] 和前缀和数组 pre。

代码实现

方法一：标准动态规划 + 前缀

class Solution {public boolean canReach(String s, int minJump, int maxJump) {int n = s.length();if (s.charAt(n - 1) != '0') return false;boolean[] dp = new boolean[n];dp[0] = true;int[] pre = new int[n + 1]; // pre[i] 表示前i个位置的可达数pre[1] = 1;for (int j = 1; j < n; j++) {if (s.charAt(j) != '0') {pre[j + 1] = pre[j];continue;}int left = j - maxJump;int right = j - minJump;left = Math.max(left, 0);right = Math.min(right, j - 1);if (left > right) {pre[j + 1] = pre[j];continue;}int sum = pre[right + 1] - pre[left];dp[j] = sum > 0;pre[j + 1] = pre[j] + (dp[j] ? 1 : 0);}return dp[n - 1];}
}

方法二：简化前缀和处理

class Solution {public boolean canReach(String s, int minJump, int maxJump) {int n = s.length();if (s.charAt(n - 1) != '0') return false;boolean[] dp = new boolean[n];dp[0] = true;int pre = 0; // 当前窗口内的可达数for (int i = 1; i < n; i++) {if (i >= minJump) pre += dp[i - minJump] ? 1 : 0;if (i > maxJump) pre -= dp[i - maxJump - 1] ? 1 : 0;dp[i] = s.charAt(i) == '0' && pre > 0;}return dp[n - 1];}
}

代码解释

方法一关键点

前缀和数组 pre：
- pre[i] 表示前 i 个位置（即索引 0 到 i-1）的可达数。
- 通过 pre[right+1] - pre[left] 快速计算区间 [left, right] 的可达数。
有效区间计算：
- left = j - maxJump，right = j - minJump，确保区间不越界。
- 若区间为空（left > right），则当前位置不可达。

方法二优化

滚动窗口优化：
- 直接维护当前窗口内的可达数 pre，无需额外数组。
- 当 i 超过 minJump 时，将 dp[i - minJump] 加入窗口。
- 当 i 超过 maxJump 时，将 dp[i - maxJump - 1] 移出窗口。

复杂度分析

时间复杂度： $O(n)$ ，每个位置仅遍历一次。
空间复杂度： $O(n)$ ，需存储 dp 数组和前缀和数组（方法一）或仅 dp 数组（方法二）。

总结与优化

动态规划是核心：通过 dp 数组记录状态，避免重复计算。
前缀和优化：将区间查询复杂度从 $O(n)$ 降至 $O(1)$ ，大幅提升效率。
空间优化：方法二中仅需维护一个 pre 变量，进一步减少空间消耗。

扩展思考：若题目允许跳跃到 '1' 位置，但需额外条件（如跳跃次数限制），如何调整算法？

希望这篇博客对您有所帮助！如果需要进一步优化或补充细节，可以随时告诉我～

LeetCode1871 跳跃游戏VII

LeetCode 跳跃游戏 IV：二进制字符串的跳跃问题题目描述给定一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump。初始时，你位于下标 0 处（保证该位置为 0）。你需要判断是否能到达字符串的最后一个位置&#xf…...

编程日记 2025/8/21 15:36:16

ResNet50深度解析：原理、结构与PyTorch实现

ResNet50深度解析：原理、结构与PyTorch实现 1. 引言 ResNet（残差网络）是深度学习领域的一项重大突破，它巧妙解决了深层神经网络训练中的梯度消失/爆炸问题，使得构建和训练更深的网络成为可能。作为计算机视觉领域的里…...

编程日记 2025/8/21 15:32:42

MATLAB 控制系统设计与仿真 - 24

PID 控制器分析- 控制器的形式连续控制器的结构： 为滤波时间常数，这类PID控制器在MATLAB系统控制工具箱称为并联PID控制器，可由MATLAB提供的pid函数直接输入，格式为： 其他类型的控制器也可以由该函数直接输入&#x…...

编程日记 2025/8/21 15:22:40

数字IC后端设计实现教程 |Innovus ICC2 Routing Pin Access Setting设置方法

默认情况下routing 引擎可以在标准单元可以打孔的任何地方（via region）打孔，甚至工具还会先拉出一块metal，然后再打孔过渡到高层。随之工艺节点越做越小，标准单元内部的结构也越来越复杂。此时如果还沿用传统工艺的走…...

编程日记 2025/8/21 15:29:39

1、准备数据 -- drop drop table if exists dept; drop table if exists emp; drop table if exists salgrade;-- CREATE CREATE TABLE dept (deptno int NOT NULL COMMENT 部门编号,dname varchar(14) CHARACTER SET utf8mb4 COLLATE utf8mb4_0900_ai_ci DEFAULT NULL COMM…...

编程日记 2025/8/21 13:52:03

网络编程-----服务器（多路复用IO 和 TCP并发模型）

一、单循环服务器模型 1. 核心特征 while(1){newfd accept();recv();close(newfd);}2. 典型应用场景 HTTP短连接服务（早期Apache）CGI快速处理简单测试服务器 3. 综合代码 #include <stdio.h> #include <sys/types.h> /* See NO…...

编程日记 2025/8/21 15:32:44

GitHub 项目版本管理与 Release 发布流程记录

GitHub 项目版本管理与 Release 发布流程记录 1. 项目环境设置 1.1 打开 VS Code 并进入项目目录 E:\adb\Do>code .1.2 配置 Git 用户信息 E:\adb\Do>git config --global user.name "n" E:\adb\Do>git config --global user.email "**gmail.com&q…...

编程日记 2025/8/20 8:59:52

GStreamer —— 2.15、Windows下Qt加载GStreamer库后运行 - “播放教程 1：Playbin 使用“（附：完整源码）

运行效果介绍我们已经使用了这个元素，它能够构建一个完整的播放管道，而无需做太多工作。本教程介绍如何进一步自定义，以防其默认值不适合我们的特定需求。将学习： • 如何确定文件包含多少个流，以及如何切换其中。…...

编程日记 2025/8/21 15:30:35

Python+DeepSeek：开启AI编程新次元——从自动化到智能创造的实战指南

文章核心价值技术热点：结合全球最流行的编程语言与国产顶尖AI模型实用场景：覆盖代码开发/数据分析/办公自动化等高频需求流量密码：揭秘大模型在编程中的创造性应用目录结构环境搭建：5分钟快速接入DeepSeek场景一：AI辅助代码开发（智能补全+调试）场景二：数据分析超级助…...

编程日记 2025/8/21 15:32:43

使用OpenCV和MediaPipe库——驼背检测（姿态监控）

目录驼背检测的运用 1. 驾驶姿态与疲劳关联分析 2. 行业应用案例 1. 教育场景痛点分析 2. 智能教室系统架构代码实现思路 1. 初始化与配置 2. MediaPipe和摄像头设置 3. 主循环 4. 资源释放 RGB与BGR的区别一、本质区别二、OpenCV的特殊性内存结构示意图&…...

编程日记 2025/8/21 6:43:14

maven的项目构建

常用构建命令命令说明mvn clean清理编译结果（删掉target目录）mvn compile编译核心代码，生成target目录mvn test-compile编译测试代码，生成target目录mvn test执行测试方法mvn package打包，生成jar或war文件mvn insta…...

编程日记 2025/8/19 8:58:23

光电感知赋能智能未来灵途科技护航新质生产力发展

2024年《政府工作报告》将大力推进现代化产业体系建设，加快发展新质生产力作为首要工作任务。这是“新质生产力”首次出现在《政府工作报告》中。发展新质生产力具体包括新兴产业 ：推动商业航天、低空经济等新兴产业实现安全健康发展。未来产业 &a…...

编程日记 2025/8/21 15:26:22

文件上传靶场（10--20）

目录实验环境： 具体内容实现： 第十关（双写绕过）： 第十一关：（%00截断，此漏洞在5.2版本中） 正确用法错误用法思路： 操作过程： 第十二关…...

编程日记 2025/8/19 5:22:48

deepseek在pycharm中的配置和简单应用

对于最常用的调试python脚本开发环境pycharm，如何接入deepseek是我们窥探ai代码编写的第一步，熟悉起来总没坏处。 1、官网安装pycharm社区版（免费），如果需要安装专业版，需要另外找破解码。 2、安装Ollama…...

编程日记 2025/8/21 15:34:09

Linux 生成静态库

文章目录前提小知识生成和使用.a库操作步骤在应用程序中，有一些公共的代码需要反复使用的，可以把这些代码制作成“库文件”；在链接的步骤中，可以让链接器在“库文件”提取到我们需要使用到的代码，复制到生成的可执行…...

编程日记 2025/8/21 15:23:12

yolo-TensorRT相关代码逐步详解-pt转engine

基于TensorRT 的推论运行速度会比仅使用CPU 快40倍，提供精度INT8 和FP16 优化，支援TensorFlow、Caffe、Mxnet、Pytorch 等深度学习框架，其中Mxnet、Pytorch 需先转换为ONNX 格式。 TensorRT的构建流程大致分为几个步骤：创建构建器和网络、解析模型、配置构建参数、构建引擎…...

编程日记 2025/8/21 15:22:40

简记_ MCU管脚的防静电处理

一、分析（一） 接口处的信号要先过 ESD/TVS 管，然后拉到被保护器件； 建个 ESD 电路发生器的模型，代入到我们的电路中去分析： 继电器实现这两个“开关”，并且还会感应出一些额外的RLC寄生。 ES…...

编程日记 2025/8/21 15:24:28

C语言实现算法（二）

以下是 “10个不重复的C语言经典算法案例“，包含可运行代码、开发环境配置及系统要求。所有代码基于标准C语法，已在GCC 9.3.0环境下测试通过。开发环境配置编译器：GCC（推荐） Windows：安装 MinGW 或 Visual Studio Linux：sudo apt-get install gcc macOS：通过Xcode Co…...

编程日记 2025/8/21 15:26:21

transformer模型介绍——大语言模型 LLMBook 学习（二）

1. transformer模型 1.1 注意力机制 **注意力机制（Attention Mechanism）**在人工智能中的应用，实际上是对人类认知系统中的注意力机制的一种模拟。它主要模仿了人类在处理信息时的选择性注意（Selective Attention）&a…...

编程日记 2025/8/21 15:23:14

K8s 1.27.1 实战系列（十一）ConfigMap

ConfigMap 是 Kubernetes 中管理非敏感配置的核心资源，通过解耦应用与配置实现灵活性和可维护性。一、ConfigMap 的核心功能及优势 1、配置解耦将配置文件（如数据库地址、日志级别）与容器镜像分离，支持动态更新而无需重建镜像。 2、多形式注入环境变量：将键值…...

编程日记 2025/8/21 15:34:10

下降路径最⼩和（medium）

题目描述： 给你一个 n x n 的方形整数数组 matrix ，请你找出并返回通过 matrix 的下降路径的最小和。下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列&#xff08…...

编程日记 2025/8/16 10:02:25

数据结构--【顺序表与链表】笔记

顺序表 template <class T> class arrList :public List<T> //表示 arrList 类以公有继承的方式继承自 List<T> 类 //公有继承意味着 List<T> 类的公共成员在 arrList 类中仍然是公共成员，受保护成员在 arrList 类中仍然是受保护成员。 { …...

编程日记 2025/8/17 12:31:14

使用AI一步一步实现若依前端(9)

功能9：退出登录功能功能8：页面权限控制功能7：路由全局前置守卫功能6：动态添加路由记录功能5：侧边栏菜单动态显示功能4：首页使用Layout布局功能3：点击登录按钮实现页面跳转功能2&#xf…...

编程日记 2025/8/17 21:27:59

Excel两列和依次相减

Excel实现左列依次行数的和减去右列依次行数的和： 举例：结余SUM(预付款)-SUM(开支) 公式：SUM($B$2:B2)-SUM($C$2:C2)...

编程日记 2025/8/16 11:48:40

智能合约中权限管理不当

权限管理不当 ： 权限管理不当是智能合约中常见的安全问题之一，尤其是在管理员或特定账户被过度赋予权限的情况下。如果合约中的关键功能，如转移资产、修改合约状态或升级合约逻辑，可以被未经授权的实体随意操作，这将构…...

编程日记 2025/8/16 11:23:57

Java糊涂包（Hutool）的安装教程并进行网络爬虫

Hutool的使用教程 1：在官网下载jar模块文件 Central Repository: cn/hutool/hutool-all/5.8.26https://repo1.maven.org/maven2/cn/hutool/hutool-all/5.8.26/ 下载后缀只用jar的文件 2：复制并到idea当中，右键这个模块点击增加到库 3&…...

编程日记 2025/8/19 16:48:51

ubuntu软件

视频软件，大部分的编码都能适应 sudo apt install vlc图片软件 sudo apt install gwenview截图软件 sudo apt install flameshot设置快捷键 flameshot flameshot gui -p /home/cyun/Pictures/flameshot也就是把它保存到一个自定义的路径菜单更换 sudo apt r…...

编程日记 2025/8/21 12:59:14

python高效试用17---两个字符串组成一个新的字符串和两个字符串组成元组作为key哪个更高效

在 Python 中，使用字符串连接 (str1 str2) 作为 key 和使用元组 ((str1, str2)) 作为 key 的效率差异，主要受以下因素影响： 哈希计算速度： 字符串连接 (str1 str2)：会创建一个新的字符串对象，并计算哈希…...

编程日记 2025/8/18 14:32:06

【C++模板】：开启泛型编程之门（函数模版，类模板）

📝前言： 在上一篇文章C内存管理中我们介绍了C的内存管理，重点介绍了与C语言的区别，以及new和delete。这篇文章我们将介绍C的利器——模板。在C编程世界里，模板是一项强大的特性，它为泛型编程奠定了坚实基础…...

编程日记 2025/8/20 9:38:14

华为eNSP:2.配置OSPF报文分析和验证

一、OSPF的5种数据包 Hello包：用于发现和维护邻居关系。定期发送，确保邻居路由器在线。数据库描述包（DBD, Database Description Packet）：在邻居关系建立后，用于交换链路状态数据库的摘要信息。链路状…...

编程日记 2025/8/18 3:03:40

一学就会的深度学习基础指令及操作步骤（3）模型训练验证

文章目录模型训练验证损失函数和优化器模型优化训练函数验证函数模型保存模型训练验证损失函数和优化器 loss_function nn.CrossEntropyLoss() # 损失函数 optimizer Adam(model.parameters()) # 优化器，优化参数模型优化获得模型所有的可训练参数&#x…...

编程日记 2025/8/18 12:25:18

【病毒分析】熊猫烧香病毒分析及其查杀修复

目录前言一、样本概况 1.1 样本信息 1.2 测试环境及工具 1.3 分析目标二、具体行为分析 2.1 主要行为 2.1.1 恶意程序对用户造成的危害 2.2 恶意代码分析 2.2.1 加固后的恶意代码树结构图(是否有加固) 2.2.2 恶意程序的代码分析片段三、解决方案(或总结) 3.1 …...

编程日记 2025/8/16 9:54:41

K8s 1.27.1 实战系列（九）Volume

一、Volume介绍 Volume 指的是存储卷，包含可被Pod中容器访问的数据目录。容器中的文件在磁盘上是临时存放的，当容器崩溃时文件会丢失，同时无法在多个Pod中共享文件，通过使用存储卷可以解决这两个问题。 1、Volume 的核心作用数据持久化与生命周期管理 Volume 的核心目标…...

编程日记 2025/8/19 18:14:01

火绒企业版V2.0全面支持Linux与国产化系统！免费试用助力国产化终端安全升级

国产化浪潮下的安全新挑战随着信创产业的加速推进，国产操作系统（统信UOS、麒麟OS等）和ARM架构服务器逐步成为政企核心业务的基础设施。然而，针对国产化系统的勒索攻击、网页篡改、供应链漏洞等威胁频发，传统安全方案…...

编程日记 2025/8/17 13:31:51

黑色RGB是什么

>好的，用户现在问的是“黑色rgb是什么”。我需要先理解用户的问题。之前用户在使用MATLAB调整网格线颜色时，可能看到了默认颜色是黑色，或者之前我提到过默认颜色是[0.15 0.15 0.15]，而用户可能现在想知道黑色的RGB值具体是什么…...

编程日记 2025/8/18 1:44:12

基于springboot+vue的佳途旅行分享预约平台

编程日记 2025/8/15 17:18:42

Nuxt3 ssr build/dev时区分不同的环境

package.json "scripts": {"build": "nuxt build --dotenv .env.prod","build:dev": "nuxt build --dotenv .env.dev","postbuild": "mv -f .output ./dist/.output", //支持自定义文件名"dev&quo…...

编程日记 2025/8/19 7:15:00

利用OpenResty拦截SQL注入

需求客户的一个老项目被相关部门检测不安全，报告为sql注入。不想改代码，改项目，所以想到利用nginx去做一些数据校验拦截。也就是前端传一些用于sql注入的非法字符或者数据库的关键字这些，都给拦截掉，从而实现拦截sql…...

编程日记 2025/8/15 13:28:42

保姆级别使用Python实现“机器学习“案例

从安装到运行手把手教学，保证不迷路～ 🌈 零基础友好版教程 📦 第一步：安装必备工具包别慌！这里有两种安装方式，选你顺手的方式1：用代码自动安装（推荐新手）直接在你的Python代码最前面加这几行，运行时会自动安装： # 把这坨代码贴在文件最前面！ import sys im…...

编程日记 2025/8/16 9:57:19

【最新】DeepSeek 实用集成工具有那些？

deepseek 系列github仓库地址【主页】deepseek-aiDeepSeek-R1DeepSeek-V3DeepSeek-VL2【本文重点介绍】awesome-deepseek-integration 注意：以下内容来自awesome-deepseek-integration DeepSeek 实用集成（awesome-deepseek-integration） 将…...

编程日记 2025/8/20 5:23:45

【前端面试题】Vu3常见的面试题

1.Vue3与 Vue2的核心区别有哪些？ ‌ 响应式系统 ‌： ‌ Vue2：通过Object.defineProperty 实现响应式。这种方式在处理对象属性的添加和删除时存在局限性，且无法直接监控数组的变化 ‌;‌Vue3：采用Proxy 实现响应式&…...

编程日记 2025/8/20 18:12:45

论文阅读分享——UMDF（AAAI-24）

概述题目：A Unified Self-Distillation Framework for Multimodal Sentiment Analysis with Uncertain Missing Modalities 发表：The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24) 年份：2024 Github：暂…...

编程日记 2025/8/15 23:03:03

JavaWeb——Mybatis、JDBC、数据库连接池、lombok

一、Mybatis 目录一、Mybatis 二、JDBC 三、数据库连接池 1.概述 2.优势 3.标准接口 4.常见产品四、lombok 1.概述 2.导入依赖 3.注解创建步骤: 1.准备工作（创建springboot工程、数据库表user、实体类User） 2.引入Mybatis的相关依赖&am…...

编程日记 2025/8/16 11:45:42

【网络安全工程】任务12：网络安全设备

目录一、防火墙 1、作用 2、配置方式 3、存在的漏洞二、入侵检测系统（IDS）和入侵防御系统（IPS） 1、作用 2、配置方式 3、存在的漏洞三、防病毒网关 1、作用 2、配置方式 3、存在的漏洞 …...

编程日记 2025/8/19 16:25:16

【学习笔记】《逆向工程核心原理》02.小段标记法、IA-32寄存器、栈、abex‘crackme、栈帧

文章目录 1. 字节序1.1. 大端序与小端序1.2. 在OllyDbg中查看小端序 2.IA-32寄存器2.1. 什么是CPU寄存器2.2. IA-32寄存器2.2.1. 通用寄存器2.2.2. 段寄存器2.2.3. 程序状态与控制寄存器2.2.4. 指令指针寄存器 3. 栈1.1. 栈的特征3.1.2. 栈操作实例 4. abexcrackme4.1. 开始调试…...

编程日记 2025/8/19 15:47:21

固定表头、首列 —— uniapp、vue 项目

项目实地：也可以在【微信小程序】搜索体验：xny.handbook 另一个体验项目：官网一、效果展示二、代码展示 （1）html 部分 <view class"table"><view class"tr"><view class&quo…...

编程日记 2025/8/16 9:54:50

用友U9二次开发-问题记录

学习资料：链接: https://pan.baidu.com/s/13JbKSSRkSn2V6-dYX5zKFQ 提取码: p9at 页面 &__dmtrue 客开插件 &Admintrue 开发者使用查看代码插件 UI插件配置项 1.关闭热插拔 2.在configuration节点下加配置，多个在Web…...

编程日记 2025/8/16 1:37:23

python---pickle库

pickle库 pickle 是 Python 标准库中的一个模块，它可以将 Python 对象（如列表、字典、类实例等）转换为字节流，这个过程称为“序列化”；反之，也可以将字节流转换回 Python 对象，这个过程称为“反…...

编程日记 2025/8/21 11:18:21

如何调用 DeepSeek 的自然语言处理 API 接口并集成到在线客服系统

我在业余时间开发了一款自己的独立产品：升讯威在线客服与营销系统。陆陆续续开发了几年，从一开始的偶有用户尝试，到如今线上环境和私有化部署均有了越来越多的稳定用户。随时近来 AI 大模型的火热，越来越多的客户，问…...

编程日记 2025/8/21 5:42:44

论文阅读 GMM-JCSFE Model（EEG Microstate）

Motor Imagery Recognition Based on GMM-JCSFE Model 1.问题与困境 1.1 微状态将连续的EEG信号分解为一系列短暂的、稳定的“微状态”，每个微状态代表了大脑在特定时间窗口内的特定功能。微状态模型的核心思想是，大脑的活动可以看作是由一系列离散的…...

编程日记 2025/8/16 12:22:14