代码随想Day55 | 392.判断子序列、115.不同的子序列
392.判断子序列
第一种思路是双指针,详细代码如下:
class Solution {
public:bool isSubsequence(string s, string t) {//双指针if(s.empty()&&t.empty()) return true;int i=0,j=0;while(i<t.size()){if(s[j]==t[i]) j++;if(j==s.size()) return true;i++;}return false;}
};
按照动态规划的思路:
这道题和最长公共子序列(不连续)几乎相同,找的是两个字符的最长公共部分,但是这道题是s已经是子序列了,所以不相等的时候s序列不需要进行删除,只需要删除s的元素,如果最长公共部分长度和s的长度相同,则返回true,否则返回false,不再详细进行动态规划的分析。
详细代码如下:
class Solution {
public:bool isSubsequence(string s, string t) {if(s.empty()&&t.empty()) return true;vector<vector<int>>dp(s.size()+1,vector<int>(t.size()+1,0));for(int i=1;i<=s.size();i++){for(int j=1;j<=t.size();j++){if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=dp[i][j-1];}}if(dp[s.size()][t.size()]==s.size()) return true;else return false;}
};
115.不同的子序列
这道题的需要延续判断子序列的思路:
dp[i][j]:以s[i-1]结尾的t[j-1]结尾的子序列个数;
递推:
这一类问题,基本是要分析两种情况
- s[i - 1] 与 t[j - 1]相等
- s[i - 1] 与 t[j - 1] 不相等
当s[i - 1] 与 t[j - 1]相等时,dp[i][j]可以有两部分组成。一部分是用s[i - 1]来匹配,那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母,所以只需要 dp[i-1][j-1]。一部分是不用s[i - 1]来匹配,个数为dp[i - 1][j]。
初始化:
从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j] 是从上方和左上方推导而来,如图:,那么 dp[i][0] 和dp[0][j]是一定要初始化的。
每次当初始化的时候,都要回顾一下dp[i][j]的定义,不要凭感觉初始化。
dp[i][0]表示什么呢?
dp[i][0] 表示:以i-1为结尾的s可以随便删除元素,出现空字符串的个数。
那么dp[i][0]一定都是1,因为也就是把以i-1为结尾的s,删除所有元素,出现空字符串的个数就是1。
再来看dp[0][j],dp[0][j]:空字符串s可以随便删除元素,出现以j-1为结尾的字符串t的个数。
那么dp[0][j]一定都是0,s如论如何也变成不了t。
最后就要看一个特殊位置了,即:dp[0][0] 应该是多少。
dp[0][0]应该是1,空字符串s,可以删除0个元素,变成空字符串t。
详细代码如下:
class Solution {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>>dp(s.size()+1,vector<uint64_t>(t.size()+1,0));for(int i=0;i<=s.size();i++) dp[i][0]=1;for(int i=1;i<=s.size();i++){for(int j=1;j<=t.size();j++){if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+dp[i-1][j]; //使用s[i-1]和不else dp[i][j]=dp[i-1][j];}}return dp[s.size()][t.size()];}
};
相关文章:

代码随想Day55 | 392.判断子序列、115.不同的子序列
392.判断子序列 第一种思路是双指针,详细代码如下: class Solution { public:bool isSubsequence(string s, string t) {//双指针if(s.empty()&&t.empty()) return true;int i0,j0;while(i<t.size()){if(s[j]t[i]) j;if(js.size()) return t…...

电缆厂 3D 可视化管控系统 | 图扑数字孪生
图扑软件(Hightopo)专注于 Web 的 2D&3D 可视化,自主研发 2D&3D 图形渲染引擎、数据孪生应用开发平台和开发工具,广泛应用于 2D&3D 可视化、工业组态与数字孪生领域,图扑软件为工业物联网、楼宇、场馆、园区、数据中心、工厂、电…...

C语言之scanf浅析
前言: 当有了变量,我们需要给变量输入值就可以使用scanf函数,如果需要将变量的值输出在屏幕上的时候可以使用printf函数,如: #include <stdio.h> int main() {int score 0;printf("请输⼊成绩:");sc…...

Java商城 免 费 搭 建:鸿鹄云商实现多种商业模式,VR全景到SAAS,应有尽有
鸿鹄云商 b2b2c产品概述 【b2b2c平台】,以传统电商行业为基石,鸿鹄云商支持“商家入驻平台自营”多运营模式,积极打造“全新市场,全新 模式”企业级b2b2c电商平台,致力干助力各行/互联网创业腾飞并获取更多的收益。从消…...

Cypress安装与使用教程(3)—— 软测大玩家
😏作者简介:博主是一位测试管理者,同时也是一名对外企业兼职讲师。 📡主页地址:【Austin_zhai】 🙆目的与景愿:旨在于能帮助更多的测试行业人员提升软硬技能,分享行业相关最新信息。…...

Dryad数据库学习
从一篇science论文中看到数据存储在了这个平台,这里分享一下:datadryad.org 亲测无需注册,可以直接下载,从一个数据测试看,数据存储在亚马逊云,下载速度还可以,6M/s的样子。 Dryad 是一个开放的…...
TypeScript 的基础语法
书接上上文:关于vue3的知识点 和 上文 :TypeScript的安装与报错 我们来接着看TypeScript 的基础语法 TypeScript 语法 1. 类型注解 类型注解是 变量后面约定类型的语法,用来约定类型,明确提示 // 约定变量 age 的类型为 numbe…...

FA模板制作
1、链接克隆模板的制作 (1)安装一个全新的Windows 10,挂载并安装tools,关闭防火墙 (2)挂载FusionAccess_WindowsDestop_Install_6.5.1.iso后启用本地Administrator本地超管,切换为本地超管&am…...
国科大2023.12.28图像处理0854最后一节划重点
国科大图像处理2023速通期末——汇总2017-2019 图像处理 王伟强 作业 课件 资料 第1、2章不考 第3章 空间域图像增强 3.2 基本灰度变换(考过填空) 3.2.1 图像反转 3.2.2 对数变换 3.2.3 幂次变换 3.3 直方图处理 3.3.1 直方图均衡化(大题计算) …...

51单片机中TCON, IE, PCON等寄存器的剖析
在单片机中,如何快速通过名字记忆IQ寄存器中每一个控制位的作用呢? IE(interrupt enable)寄存器中,都是中断的使能位置。 其中的EA(enable all)是总使能位,ES(enable serial)是串口…...
2023.12.28 Python高级-正则表达式
目录 re正则表达式,一种专门用来匹配目标字符串的规则 re.match(),从头匹配一个,无则none re.search(), 不从头匹配返回一个,无则none re.findall(), 不从头匹配,用list返回所有 re分组 re匹配修饰符 re贪婪非贪婪 re切割和替换 re正则表达式,一种专门用来匹配目标字符串…...
编程笔记 html5cssjs 014 网页布局框架
编程笔记 html5&css&js 014 网页布局框架 一、Bootstrap简介二、使用Bootstrap布局 网页布局不只用HTML,还要用CSS和JAVASCRIPT等技术完成,这里暂时简单了解一下Bootstrap。 一、Bootstrap简介 这是一个开源的前端框架,由Twitter的前端工程师Ma…...

抖店和商品橱窗有什么区别?新手应该选哪个?
我是电商珠珠 临近年底了,有的人已经开始为下一年筹谋,有的去抖音做账号做直播带货,不会直播带货的就想尝试做下抖店,来为以后的经济打基础。 刚想要接触却对这类有些迷糊,发现商品橱窗和抖店都可以卖货,…...

在Adobe Acrobat上如何做PDF文档签名
Adobe Acrobat如何做PDF文档签名?PDF文档签名是指对PDF文档进行基于证书的数字签名,类似于传统的手写签名,可标识签名文档的人员。与手写签名不同,数字签名难以伪造,因为其包含签名者唯一的加密信息。为PDF文档进行基于…...
Leetcode 988. Smallest String Starting From Leaf (二叉树遍历好题)
Smallest String Starting From Leaf Medium 1.6K 227 Companies You are given the root of a binary tree where each node has a value in the range [0, 25] representing the letters ‘a’ to ‘z’. Return the lexicographically smallest string that starts at a le…...

redis 三主六从高可用docker(不固定ip)
redis集群(cluster)笔记 redis 三主三从高可用集群docker swarm redis 三主六从高可用docker(不固定ip) 此博客解决,redis加入集群后,是用于停掉后重启,将nodes.conf中的旧的Ip替换为新的IP,从而达到不会因为IP变化导致集群无法…...

12.26
key_it.c #include"key_it.h" void led_init() {// 设置GPIOE/GPIOF时钟使能RCC->MP_AHB4ENSETR | (0x3 << 4);// 设置PE10/PE8/PF10为输出模式GPIOE->MODER & (~(0x3 << 20));GPIOE->MODER | (0x1 << 20);GPIOE->MODER & (~…...

2022年全国职业院校技能大赛高职组云计算正式赛卷第三场-公有云
2022 年全国职业院校技能大赛高职组云计算赛项试卷 【赛程名称】云计算赛项第三场-公有云 目录 2022 年全国职业院校技能大赛高职组云计算赛项试卷 【赛程名称】云计算赛项第三场-公有云 【任务 1】公有云服务搭建[10 分] 【任务 2】公有云服务运维[10 分] 【任务 3】公有云运维…...
Python | 机器学习之数据清洗
机器学习前的数据清洗(异常值检验,标准化处理,哑变量处理) Python | 机器学习之数据清洗 机器学习 - 基础概念 - scikit-learn - 数据预处理 数据的标准化(离差标准化、log函数转换、atan函数转换、z…...
力扣:509. 斐波那契数(动态规划,附带递归版本) 详细讲解动态规划的思路
题目: 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) 0,F(1) 1 F(n) F(n - 1) F(n - 2),其中…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...

大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...

工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...