代码随想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),其中…...

CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验
Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...