LeetCode392_判断子序列
LeetCode392_判断子序列
- 标签:#双指针 #字符串 #动态规划
- Ⅰ. 题目
- Ⅱ. 示例
- 0. 个人方法
- 官方题解一:双指针
- 官方题解二:动态规划
标签:#双指针 #字符串 #动态规划
Ⅰ. 题目
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
- 进阶:
如果有大量输入的 S,称作 S1, S2, … , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?
Ⅱ. 示例
· 示例 1:
输入:s = “abc”, t = “ahbgdc”
输出:true
· 示例 2:
输入:s = “axc”, t = “ahbgdc”
输出:false
0. 个人方法
遍历字符串 t,逐个和 s 字符串对比,如果相同就让cnt++(我的代码里写的是 position),不同就继续遍历字符串 t,如果 cnt == s.length(),那么就说明字符串 t 中有字符串 s 这个子序列
class Solution {
public:bool isSubsequence(string s, string t) {if (t.length() < s.length())return false;if (t.length() == 0 && s.length() == 0)return true;int position = 0;for (int i=0; i<t.length(); ++i){if (t[i] == s[position]){position++;}if (position == s.length()){return true;}}return false;}
};
官方题解一:双指针
大致思路与个人方法相同
class Solution {
public:bool isSubsequence(string s, string t) {int n = s.length(), m = t.length();int i = 0, j = 0;while (i < n && j < m) {if (s[i] == t[j]) {i++;}j++;}return i == n;}
};
官方题解二:动态规划
(如果需要多次查询 s 是否是 t 的子序列,DP方法更高效)
考虑到前面双指针的做法,我们注意到我们有大量的时间用于在 t 中找到下一个匹配字符。
因此,我们可以考虑对 t 进行预处理,记录从当前位置起,往后每一个字符第一次出现的位置。
class Solution {
public:bool isSubsequence(string s, string t) {int n = s.size(), m = t.size();// DP 表:f[i][j] 表示 t 从位置 i 开始,字符 j 第一次出现的位置vector<vector<int>> f(m + 1, vector<int>(26, 0));// 初始化边界:如果 t 的末尾之后的位置,所有字符都不可达(设为 m)for (int j = 0; j < 26; j++) {f[m][j] = m;}// 填充 DP 表for (int i = m - 1; i >= 0; i--) {for (int j = 0; j < 26; j++) {if (t[i] == j + 'a') // 当前字符匹配f[i][j] = i;else // 否则继承 i+1 的结果f[i][j] = f[i + 1][j];}}// 遍历 s,检查是否能在 t 中找到匹配的字符int add = 0; // 当前在 t 中的查找起始位置for (int i = 0; i < n; i++) {if (f[add][s[i] - 'a'] == m) { // 字符 s[i] 在 t 中不存在return false;}add = f[add][s[i] - 'a'] + 1; // 跳到匹配位置的下一个位置}return true; // 所有字符都匹配成功}
};
-
示例1:
-
输入:s = “abc”, t = “ahbgdc”
-
预处理 t 后,f 会记录每个字符的位置。
-
匹配 s:
-
‘a’ 在 t 的位置 0 → add = 1
-
‘b’ 在 t 的位置 2 → add = 3
-
‘c’ 在 t 的位置 5 → 匹配成功
-
-
-
输出:true
-
-
示例2:
-
输入:s = “axc”, t = “ahbgdc”
-
‘a’ 匹配 t[0] → add = 1
-
‘x’ 在 t 中不存在 → 返回 false
-
-
相关文章:
LeetCode392_判断子序列
LeetCode392_判断子序列 标签:#双指针 #字符串 #动态规划Ⅰ. 题目Ⅱ. 示例 0. 个人方法官方题解一:双指针官方题解二:动态规划 标签:#双指针 #字符串 #动态规划 Ⅰ. 题目 给定字符串 s 和 t ,判断 s 是否为 t 的子序…...
力扣第447场周赛
这次终于赶上力扣的周赛了, 赛时成绩如下(依旧还是三题 ): 1. 统计被覆盖的建筑 给你一个正整数 n,表示一个 n x n 的城市,同时给定一个二维数组 buildings,其中 buildings[i] [x, y] 表示位于坐标 [x, y] 的一个 唯一 建筑。 如…...
kotlin中Triple的作用
在 Kotlin 里,Triple 是标准库提供的一个类,其作用是创建一个包含三个元素的不可变容器。以下是关于它的详细介绍: 基本作用 Triple 类让你能够把三个不同类型的值组合成一个单一对象,方便在函数间传递或者存储这三个相关的值。…...
jmeter读取CSV文件中文乱码的解决方案
原因分析 CSV文件出现中文乱码通常是因为文件编码与JMeter读取编码不一致。常见场景: 文件保存为GBK/GB2312编码,但JMeter以UTF-8读取。文件包含BOM头(如Windows记事本保存的UTF-8),但JMeter未正确处理。脚本读取文…...
Mysql查询异常【Truncated incorrect INTEGER value】
文章目录 异常原因分析1、数据类型不一致2、数据长度超长3、数据格式要正确 处理方案模拟案例创建表数据查询 异常 在执行MySQL的语句时,在控制台报错如下所示。 Data truncation: Truncated incorrect INTEGER value 原因分析 1、数据类型不一致 必须要保证数据…...
vue+django农产品价格预测和推荐可视化系统[带知识图谱]
文章结尾部分有CSDN官方提供的学长 联系方式名片 文章结尾部分有CSDN官方提供的学长 联系方式名片 关注B站,有好处! ✅编号:D010 vue django 前后端分离架构搭建的系统带有推荐算法、价格预测、可视化、知识图谱数据从爬虫获取可以更新到最…...
2025年天梯题解(L1-8 + L2)
L1-112 现代战争 题目 既然是从大到小轰炸,将所有点存储为三元组(value, x, y)。 排序之后, 记录行列被轰炸的编号,进行 k 次挑选即可。 #include <bits/stdc.h> using namespace std;constexpr int MAXN 1000; struct …...
AndroidStudio生成AAR
Android Studio 2024.3 版本。如何生成 AAR 文件呢? 操作步骤 1、菜单栏,找到 Build 2、清除项目 Clean Project 3、构建项目 Assemble Project生成 AAR 路径 在 我们构建 lib 库下面。 build/outputs/aar/ xxxx下面截图为证: 我的…...
Vue3 后台管理系统模板
Vue3 后台管理系统模板 gie仓库地址 一个基于 Vue3 TypeScript Element Plus 的后台管理系统模板,集成了动态路由和权限管理功能。 技术栈 Vue 3.2TypeScript 4.5Vue Router 4Vuex 4Element Plus 2.9AxiosLess 功能特性 🚀 基于 Vue3 最新技术栈开…...
RPG4.设置角色输入
这一篇是进行玩家移动和视角移动的介绍。 1.在玩家内进行移动覆写 virtual void SetupPlayerInputComponent(UInputComponent* PlayerInputComponent) override; 2.创建增强输入资产的变量创建 UPROPERTY(EditDefaultsOnly, BlueprintReadOnly, Category "CharacterD…...
生产模块-备货生产
特点 从狭义的角度来看,备货生产场景主要出现在产品定制化需求低,产品工艺流程稳定可以大批生产,市场行情可预测的企业。为了实现订单快速交付,缩短交货周期,企业往往会结合公司历史订单数据和当前市场情况安排提前生产…...
GRE隧道
1.在锐捷网络设备中,tunnel mode gre ip 和 tunnel mode gre multipoint 是两种不同的 GRE(Generic Routing Encapsulation)隧道模式,主要区别在于连接拓扑和使用场景: 1. tunnel mode gre ip(点到点 GRE …...
ASP.NET MVC 入门与提高指南六
31. 事件驱动架构与 MVC 集成 31.1 事件驱动架构概念 事件驱动架构(Event - Driven Architecture,EDA)是一种软件设计模式,系统中的组件通过发布和订阅事件来进行通信。在这种架构中,当某个事件发生时,相…...
【MongoDB篇】MongoDB的文档操作!
目录 引言第一节:C - Create - 创建文档 (Insert) 👶➕第二节:R - Read - 读取文档 (Query) 📚👀第三节:U - Update - 更新文档 (Update) 🔄✍️第四节:D - Delete - 删除文档 (Dele…...
详解具身智能机器人开源数据集:RoboMIND
一、RoboMIND基础信息 RoboMIND 发布时间:2024年12月 创建方:国家地方共建具身智能机器人创新中心与北京大学计算机学院联合创建。 所使用的机器人:单臂机器人(Franka Emika Panda 、UR5e )、双臂机器人(…...
施磊老师rpc(一)
文章目录 mprpc项目**项目概述**:深入学习到什么**前置学习建议**:核心内容其他技术与工具**项目特点与要求**:**环境准备**: 技术栈集群和分布式理论单机聊天服务器案例分析集群聊天服务器分析分布式系统介绍多个模块的局限引入分…...
视觉问答大模型速递:Skywork-R1V2-38B
Skywork-R1V2-38B速读 一、模型概述 Skywork-R1V2-38B是一种最先进的开源多模态推理模型,在多项基准测试中表现卓越。它在MMMU测试中以73.6%的得分位居所有开源模型之首,在OlympiadBench测试中以62.6%的得分大幅领先于其他开源模型。此外,R…...
Spring Boot 中集成 Kafka 并实现延迟消息队列
在 Spring Boot 中集成 Kafka 并实现延迟消息队列,需要结合 Kafka 的基础功能与自定义逻辑来处理延迟投递。以下是完整的实现步骤和示例代码,涵盖配置、生产者、消费者、延迟队列设计和消息重试机制。 一、环境准备与依赖配置 添加依赖 在 pom.xml 中添加 Spring Kafka 依赖:…...
【算法学习】哈希表篇:哈希表的使用场景和使用方法
算法学习: https://blog.csdn.net/2301_80220607/category_12922080.html?spm1001.2014.3001.5482 前言: 在之前学习数据结构时我们就学习了哈希表的使用方法,这里我们主要是针对哈希表的做题方法进行讲解,都是leetcode上的经典…...
(51单片机)LCD显示红外遥控相关数据(Delay延时函数)(LCD1602教程)(Int0和Timer0外部中断教程)(IR红外遥控模块教程)
前言: 本次Timer0模块改装了一下,注意!!! 演示视频: 红外遥控 源代码: 如上图将9个文放在Keli5 中即可,然后烧录在单片机中就行了 烧录软件用的是STC-ISP,不知道怎么安…...
农产品园区展示系统——仙盟创梦IDE开发
<!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>农业大数据平台</title><style>* {margi…...
Copilot:您的AI伴侣-微软50周年系列更新
回顾微软五十年来持续创新带来的深远影响,比尔盖茨当年"让每张办公桌、每个家庭都拥有电脑"的宏伟愿景至今仍激励着我们。微软AI团队正秉承同样的精神,打造属于每个人的AI伙伴——Copilot。 这意味着什么?它是什么模样?…...
【人工智能】深入探索Python中的自然语言理解:实现实体识别系统
《Python OpenCV从菜鸟到高手》带你进入图像处理与计算机视觉的大门! 解锁Python编程的无限可能:《奇妙的Python》带你漫游代码世界 自然语言理解(NLU)是人工智能(AI)领域中的重要研究方向之一,其目标是让计算机理解和处理人类语言。在NLU的众多应用中,实体识别(Nam…...
Steam安装下载及新手注册
📢博客主页:肩匣与橘 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正! 📢本文由肩匣与橘编写,首发于CSDN🙉 📢生活依旧是美好而又温柔的,你也…...
Gradio全解20——Streaming:流式传输的多媒体应用(1)——流式传输音频:魔力8号球
Gradio全解20——Streaming:Streaming:流式传输的多媒体应用(1)——流式传输音频:魔力8号球 前言本篇摘要20. Streaming:流式传输的多媒体应用20.1 流式传输音频:魔力8号球20.1.1 工作原理20.1.…...
Netflix系统架构解析
Netflix系统架构解析 Netflix架构旨在高效可靠地同时为数百万用户提供内容。以下是其特性和组件的详细分析。 是否曾好奇Netflix如何让您目不转睛地享受无中断的流畅播放体验?幕后功臣正是Netflix架构,它负责提供吸引全球观众的无缝流媒体体验。Netflix的…...
宝塔面板运行docker的jenkins
1.在宝塔面板装docker,以及jenkins 2.ip:端口访问jenkins 3.获取密钥(点击日志) 4.配置容器内的jdk和maven环境(直接把jdk和maven文件夹放到jenkins容器映射的data文件下) 点击容器-->管理-->数据存储卷--.把相…...
【计算机视觉】目标检测:深度解析Detectron2:Meta开源目标检测与图像分割框架实战指南
深度解析Detectron2:Meta开源目标检测与图像分割框架实战指南 技术架构与设计哲学核心设计理念关键技术组件 环境配置与安装硬件建议配置详细安装步骤 实战流程详解1. 自定义数据集准备2. 模型配置与训练3. 模型评估与推理 核心功能扩展1. 自定义模型架构2. 混合精度…...
Notepad编辑器实现换行符替换
在不同的Note编辑器中,批量把换行替换为空的方法有所不同,以下是常见编辑器的操作方法: Notepad 打开文件后,按CtrlH打开“查找和替换”对话框,在“查找”字段中输入\r\n,在“替换为”字段中输入一个空格…...
【数据通信完全指南】从物理层到协议栈的深度解析
目录 1. 通信技术演进与核心挑战1.1 从电报到5G的技术变迁1.2 现代通信系统的三大瓶颈 2. 通信系统架构深度解构2.1 OSI七层模型运作原理2.2 TCP/IP协议栈实战解析 3. 物理层关键技术实现3.1 信号调制技术演进路线3.2 信道复用方案对比 4. 数据传输可靠性保障4.1 CRC校验算法数…...
SpringBoot多工程项目微服务install时如何不安装到本地仓库
在 Spring Boot 微服务项目中,比如各业务微服务模块由于不存在相互依赖度的问题,因此执行maven install时无需安装到本地仓库,但仍然需要参与构建(如 mvn compile 或 mvn package)。公共模块(如辅助工具…...
强化学习_Paper_2017_Curiosity-driven Exploration by Self-supervised Prediction
paper Link: ICM: Curiosity-driven Exploration by Self-supervised Prediction GITHUB Link: 官方: noreward-rl 1- 主要贡献 对好奇心进行定义与建模 好奇心定义:next state的prediction error作为该state novelty 如果智能体真的“懂”一个state,那…...
iview内存泄漏
iview在升级到view-design之前,是存在严重的内存泄漏问题的,而如果你在项目中大量使用了iview组件,就可能面临大量的升级工作要做,因为样式很多是不兼容的。 我们今天就看一下iview的源码,看看到底问题在哪里ÿ…...
【Hive入门】Hive高级特性:事务表与ACID特性详解
目录 1 Hive事务概述 2 ACID特性详解 3 Hive事务表的配置与启用 3.1 启用Hive事务支持 3.2 创建事务表 4 Hive事务操作流程 5 并发控制与隔离级别 5.1 Hive的锁机制 5.2 隔离级别 6 Hive事务的限制与优化 6.1 主要限制 6.2 性能优化建议 7 事务表操作示例 7.1 基本…...
Modbus转PROFIBUS网关:电动机保护新突破!
Modbus转PROFIBUS网关:电动机保护新突破! 在现代工业自动化领域,Modbus RTU和PROFIBUS DP是两种常见且重要的通讯协议。它们各自具有独特的优势和应用场景,但在实际工程中,我们常常需要将这两种不同协议的设备进行互联…...
大数据应用开发和项目实战-Seaborn
设计目标 seaborn 建立在 matplotlib 之上,专注于统计数据可视化,简化绘图过程,提供高级接口和美观的默认主题 Seaborn的安装: 1.pip install seaborn -i 2.conda install seaborn (清华源:https://pypi.t…...
弹窗探索鸿蒙之旅:揭秘弹窗的本质与奥秘
嘿,小伙伴们!👋 今天我们要一起探索那些在日常应用中无处不在的小精灵——弹窗!💬 🤔 弹窗到底是什么? 简单来说,弹窗就是应用程序中突然冒出来的交互元素,它们像…...
“技术创新+全球视野”良性驱动,首航新能的2025新征程正式起航
撰稿 | 行星 来源 | 贝多财经 近日,备受瞩目的“2025年光伏第一股”深圳市首航新能源股份有限公司(301658.SZ,下称“首航新能”)对外发布了上市后的首份年报,交出了一份量质齐升的业绩答卷,构筑更加强大的…...
黑群晖Moments视频无缩略图,安装第三方ffmpeg解决
黑群晖Moments视频无缩略图,安装第三方ffmpeg解决 1. 设置套件来源 黑群晖Moments视频无缩略图,安装第三方ffmpeg解决 基于这个文章,补充一下: 1. 设置套件来源 设置套件来源时(http://packages.synocommunity.com),…...
工业控制「混合架构」PK大战 —— 神经网络 + MPC vs 模糊 PID+MPC 的场景选型与实战指南
1. 引言 在工业控制领域,传统的 PID 控制器因其结构简单、稳定性好而被广泛应用,但面对复杂非线性系统时往往力不从心。模型预测控制(MPC)作为一种基于模型的先进控制策略,能够有效处理多变量、多约束问题,…...
树莓派智能摄像头实战指南:基于TensorFlow Lite的端到端AI部署
引言:嵌入式AI的革新力量 在物联网与人工智能深度融合的今天,树莓派这一信用卡大小的计算机正在成为边缘计算的核心载体。本文将手把手教你打造一款基于TensorFlow Lite的低功耗智能监控设备,通过MobileNetV2模型实现实时物体检测࿰…...
OpenCV 图形API(73)图像与通道拼接函数-----执行 查找表操作图像处理函数LUT()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 对矩阵执行查找表变换。 函数 LUT 使用来自查找表中的值填充输出矩阵。输入矩阵中的值作为查找表的索引。也就是说,函数对 src 中的…...
【MySQL】增删改查(CRUD)
目录 一. CRUD是什么 二. Create(新增数据) 2.1 单行数据全列插入 2.2 单行数据指定列插入 2.3 多行数据指定列插入 三. Retrieve (检索/查询) 3.1 全列查询 3.2 指定列查询 3.3 查询字段为表达式 3.4 为查询结果指定别名 3…...
iview 如何设置sider宽度
iview layout组件中,sider设置了默认宽度和最大宽度,在css样式文件中修改无效,原因是iview默认样式设置在了element.style中,只能通过行内样式修改 样式如下: image.png image.png 修改方式: 1.官方文档中写…...
Unity URP RenderTexture优化(二):深度图优化
目录 前言: 一、定位深度信息 1.1:k_DepthStencilFormat 1.2:k_DepthBufferBits 1.3:_CameraDepthTexture精度与大小 1.4:_CameraDepthAttachment数量 二、全代码 前言: 在上一篇文章:Un…...
iview表单提交验证时,出现空值参数被过滤掉不提交的问题解决
如图所示 有时候在表单提交的时候 个别参数是空值,但是看提交接口的反馈 发现空值的参数根本没传 这是因为表单验证给过滤掉了空值,有时候如果空值传不传都不无所谓,那可以不用管,但如果就算是空值也得传的吗,那就需要…...
GEO vs SEO:从搜索引擎到生成引擎的优化新思路
随着人工智能技术的快速发展,生成引擎优化(GEO)作为一种新兴的优化策略,逐渐成为企业和内容创作者关注的焦点。与传统的搜索引擎优化(SEO)相比,GEO不仅关注如何提升内容在搜索结果中的排名&…...
Python-pandas-操作csv文件(读取数据/写入数据)及csv语法详细分享
Python-pandas-操作csv文件(读取数据/写入数据) 提示:帮帮志会陆续更新非常多的IT技术知识,希望分享的内容对您有用。本章分享的是pandas的使用语法。前后每一小节的内容是存在的有:学习and理解的关联性。【帮帮志系列文章】:每个…...
如何在Windows上实现MacOS中的open命令
在MacOS的终端中,想要快速便捷的在Finder中打开当前目录,直接使用oepn即可。 open . 但是Windows中没有直接提供类似open这样的命令,既然没有直接提供,我们就间接手搓一个实现它。 步骤1:创建open.bat echo OFF expl…...
读论文笔记-LLaVA:Visual Instruction Tuning
读论文笔记-LLaVA:Visual Instruction Tuning 《Visual Instruction Tuning》 研究机构:Microsoft Research 发表于2023的NeurIPS Problems 填补指令微调方法(包括数据、模型、基准等)在多模态领域的空白。 Motivations 人工…...