【LeetCode】392. 判断子序列(简单)——代码随想录算法训练营Day54
题目链接:392. 判断子序列
题目描述
给定字符串 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 <= s.length <= 1000 <= t.length <= 10^4- 两个字符串都只由小写字符组成。
文章讲解:代码随想录
视频讲解:动态规划,用相似思路解决复杂问题 | LeetCode:392.判断子序列_哔哩哔哩_bilibili
题解1:动态规划
思路:使用动态规划法求解子序列问题,本题判断 s 和 t 的最长公共子序列长度是否为 s 的长度。
动态规划分析:
- dp 数组以及下标的含义:dp[i][j] 表示以 s[i] 结尾和 t[j] 结尾的最长公共子序列长度。
- 递推公式:当 s[i - 1] 等于 t[j - 1] 时,dp[i][j] = dp[i - 1][j - 1] + 1;否则,dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])。
- dp 数组初始化:全部初始化为0。
- 遍历顺序:从上往下,从左往右。
- 打印 dp 数组:以输入 s = "abc"、t = "ahbgdc" 为例,dp 数组为 [ [ 0, 0, 0, 0, 0, 0, 0 ], [ 0, 1, 1, 1, 1, 1, 1 ], [ 0, 1, 1, 2, 2, 2, 2 ], [ 0, 1, 1, 2, 2, 2, 3 ] ]。
/*** @param {string} s* @param {string} t* @return {boolean}*/
var isSubsequence = function(s, t) {const dp = new Array(s.length + 1).fill().map(() => new Array(t.length + 1).fill(0));for (let i = 1; i <= s.length; i++) {for (let j = 1; j <= t.length; j++) {if (s[i - 1] === t[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[s.length][t.length] === s.length;
};
分析:时间复杂度为 O(m * n),空间复杂度为 O(m * n)。
题解2:双指针
思路:
/*** @param {string} s* @param {string} t* @return {boolean}*/
var isSubsequence = function(s, t) {let index = 0;for (let i = 0; i < t.length; i++) {if (t[i] === s[index]) {index++;}}return index === s.length;
};
分析:时间复杂度为 O(n),空间复杂度为 O(1)。
收获
练习使用动态规划法求解子序列问题。
相关文章:
【LeetCode】392. 判断子序列(简单)——代码随想录算法训练营Day54
题目链接:392. 判断子序列 题目描述 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"…...
1. Typescript入门
TS 基础 Typescript 在线编译平台 基础类型 boolean、number 和 string 类型 boolean let isHandsome: boolean true赋值与定义的不一致,会报错,静态类型语言的优势就体现出来了,可以帮助我们提前发现代码中的错误。 let isHandsome: …...
【Git】merge时报错:refusing to merge unrelated histories
文章目录 一、问题二、解决办法1、将feature分支的东西追加到master分支中2、将feature里的东西直接覆盖到master分支中 一、问题 今天将feature分支合并到master时报错:refusing to merge unrelated histories(拒绝合并无关历史) 报错原因&…...
树状数组+离散化求逆序对超详细讲解!
树状数组离散化求逆序对 用一个数组 w [ ] w[] w[]来记录遍历到当前数时,每个数出现的次数 由于只关心每个数前边有多少个数比他大,遍历到 i i i时,求大于 a [ i ] a[i] a[i]的数有多少个,就是对 [ a [ i ] , n ] [a[i], n] [a[i…...
《解密云计算:企业之选》
前言 在当今数字化时代,企业面临着巨大的数据处理压力和信息化需求,传统的IT架构已经无法满足日益增长的业务需求。在这样的背景下,越来越多的企业开始转向云计算,以实现灵活、高效和可扩展的IT资源管理和利用。 云计算 云计算是…...
地址分词 | EXCEL批量进行地址分词,标准化为十一级地址
一 需求 物流需要对用户输入地址进行检查,受用户录入习惯地址可能存在多种问题。 地址标准化是基于地址引擎和地址大数据模型,自动将地址信息标准化为省、市、区市县、街镇、小区、楼栋、单元、楼层、房屋、房间等元素,补充层级缺失数据、构建…...
KubeSphere平台安装系列之二【Linux单节点部署KubeSphere】(2/3)
**《KubeSphere平台安装系列》** 【Kubernetes上安装KubeSphere(亲测–实操完整版)】(1/3) 【Linux单节点部署KubeSphere】(2/3) 【Linux多节点部署KubeSphere】(3/3) **《KubeS…...
网络安全: Kali Linux 使用 docker-compose 部署 openvas
目录 一、实验 1.环境 2.Kali Linux 安装docker与docker-compose 3.Kali Linux 使用docker-compose方式部署 openvas 4. KaliLinux 使用openvas 二、问题 1. 信息安全漏洞库 2.信息安全漏洞共享平台 3.Windows 更新指南与查询 4.CVE 查询 5.docker-compose 如何修改o…...
【学习考试心得】在誉天学习考试RHCE9.0的体验
作为华中第一位参加RHCE9.0线上考试的考生,很荣幸能来写这个心得,和大家分享一下线上的考试的一些体验。 一、学习体验 首先在红帽课程的学习中,跟着杨峰老师的脚步,整个学习过程中都非常有意思。杨峰老师充满磁性的声音和小王老师…...
Flip Clock(not good)
最近体验了一下iOS的翻页时钟app,很想自己做一个,但是效果不好 public class main {public static void main(String[] args) {//psvmnew MyFrame();} }import javax.swing.*; import java.awt.*; import java.io.File; import java.io.IOException; im…...
目标检测——摩托车头盔检测数据集
一、简介 首先,摩托车作为一种交通工具,具有高速、开放和稳定性差的特点,其事故发生率高,伤亡率排在机动车辆损伤的首位。因此,摩托车乘员头盔对于保护驾乘人员头部安全至关重要。在驾乘突发状况、人体受冲击时&#…...
Windows 安装 Xinference
Windows 安装 Xinference 0. 引言1. 创建虚拟环境2. 安装 pytorch3. 安装 llama_cpp_python4. 安装 chatglm-cpp5. 安装 Xinference6. 设置 model 路径7. 启动 Xinference8. 查看 Cluster Information 0. 引言 Xorbits Inference(Xinference)是一个性能…...
静态时序分析:SDC约束命令set_case_analysis详解
相关阅读 静态时序分析https://blog.csdn.net/weixin_45791458/category_12567571.html?spm1001.2014.3001.5482 目录 指定值 指定端口/引脚列表 简单使用 set_case_analysis命令用于对电路进行特定模式的设定,例如对于一个工作在正常模式下的芯片,…...
C++ · 代码笔记4 ·继承与派生
目录 前言010继承与派生简单例程020多级继承030使用using关键词更改访问权限040隐藏050派生类与基类成员函数同名时不构成重载060使用多级继承展示成员变量在内存中的分布情况071派生类在函数头调用基类构造函数072构造函数调用顺序080构造函数与析构函数的调用顺序091多重继承…...
解决uni-app中使用webview键盘弹起遮挡input输入框问题
这个平平无奇的回答,可能是全网最靠谱的解决方案。 这里我用的是vue3 setup .vue文件的方式 <view> <web-view :fullscreen"false" :webview-styles"{top: statusBarHeight40,height:height,progress: {color: green,height:1px } }"…...
Java注解介绍
Java注解 注解介绍元注解RetentionTargetDocumentedInherited接口类测试结果 注解介绍 Java注解(Annotation)是一种元数据(Metadata)的形式,它可以被添加到Java代码中的类、方法、变量、参数等元素上,以提…...
万字详解,Java实现低配版线程池
文章目录 1.什么是线程池2.线程池的优势3.原理4.代码编写4.1 阻塞队列4.2 ThreadPool线程池4.3 Worker工作线程4.4 代码测试 5. 拒绝策略5.1 抽象Reject接口5.2 BlockingQueue新增tryPut方法5.3 修改ThreadPool的execute方法5.4 ThreadPool线程池构造函数修改5.5 拒绝策略实现1…...
挂耳式蓝牙耳机哪家的好用?购买耳机前必须了解的几大要点
随着健康意识的提升,越来越多的人开始热衷于运动。运动不仅能够增强体质,对于我们这些忙碌的上班族而言,它也是一种极佳的减压方式。经过一天的辛勤工作,能够在户外跑步,让汗水带走压力,实在是一种享受。在…...
CSS文本属性
CSS文本属性 1.文本颜色2.文本间距3. 文本修饰4 .文本缩进5.文本对齐_水平6.行高7. vertical-align 1.文本颜色 属性名:color作用:控制文字的颜色。可选值: 颜色名rgb或rgbaHEX或HEXA (十六进制)HSL或HSLA 开发中常用…...
MySQL篇—执行计划之覆盖索引Using index和条件过滤Using where介绍(第三篇,总共三篇)
☘️博主介绍☘️: ✨又是一天没白过,我是奈斯,DBA一名✨ ✌✌️擅长Oracle、MySQL、SQLserver、Linux,也在积极的扩展IT方向的其他知识面✌✌️ ❣️❣️❣️大佬们都喜欢静静的看文章,并且也会默默的点赞收藏加关注❣…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
