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

代码随想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.判断子序列 第一种思路是双指针&#xff0c;详细代码如下&#xff1a; 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 可视化&#xff0c;自主研发 2D&3D 图形渲染引擎、数据孪生应用开发平台和开发工具&#xff0c;广泛应用于 2D&3D 可视化、工业组态与数字孪生领域&#xff0c;图扑软件为工业物联网、楼宇、场馆、园区、数据中心、工厂、电…...

C语言之scanf浅析

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

Java商城 免 费 搭 建:鸿鹄云商实现多种商业模式,VR全景到SAAS,应有尽有

鸿鹄云商 b2b2c产品概述 【b2b2c平台】&#xff0c;以传统电商行业为基石&#xff0c;鸿鹄云商支持“商家入驻平台自营”多运营模式&#xff0c;积极打造“全新市场&#xff0c;全新 模式”企业级b2b2c电商平台&#xff0c;致力干助力各行/互联网创业腾飞并获取更多的收益。从消…...

Cypress安装与使用教程(3)—— 软测大玩家

&#x1f60f;作者简介&#xff1a;博主是一位测试管理者&#xff0c;同时也是一名对外企业兼职讲师。 &#x1f4e1;主页地址&#xff1a;【Austin_zhai】 &#x1f646;目的与景愿&#xff1a;旨在于能帮助更多的测试行业人员提升软硬技能&#xff0c;分享行业相关最新信息。…...

Dryad数据库学习

从一篇science论文中看到数据存储在了这个平台&#xff0c;这里分享一下&#xff1a;datadryad.org 亲测无需注册&#xff0c;可以直接下载&#xff0c;从一个数据测试看&#xff0c;数据存储在亚马逊云&#xff0c;下载速度还可以&#xff0c;6M/s的样子。 Dryad 是一个开放的…...

TypeScript 的基础语法

书接上上文&#xff1a;关于vue3的知识点 和 上文 &#xff1a;TypeScript的安装与报错 我们来接着看TypeScript 的基础语法 TypeScript 语法 1. 类型注解 类型注解是 变量后面约定类型的语法&#xff0c;用来约定类型&#xff0c;明确提示 // 约定变量 age 的类型为 numbe…...

FA模板制作

1、链接克隆模板的制作 &#xff08;1&#xff09;安装一个全新的Windows 10&#xff0c;挂载并安装tools&#xff0c;关闭防火墙 &#xff08;2&#xff09;挂载FusionAccess_WindowsDestop_Install_6.5.1.iso后启用本地Administrator本地超管&#xff0c;切换为本地超管&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 直方图均衡化&#xff08;大题计算&#xff09; …...

51单片机中TCON, IE, PCON等寄存器的剖析

在单片机中&#xff0c;如何快速通过名字记忆IQ寄存器中每一个控制位的作用呢&#xff1f; IE&#xff08;interrupt enable&#xff09;寄存器中&#xff0c;都是中断的使能位置。 其中的EA&#xff08;enable all&#xff09;是总使能位&#xff0c;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&#xff0c;还要用CSS和JAVASCRIPT等技术完成,这里暂时简单了解一下Bootstrap。 一、Bootstrap简介 这是一个开源的前端框架&#xff0c;由Twitter的前端工程师Ma…...

抖店和商品橱窗有什么区别?新手应该选哪个?

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

在Adobe Acrobat上如何做PDF文档签名

Adobe Acrobat如何做PDF文档签名&#xff1f;PDF文档签名是指对PDF文档进行基于证书的数字签名&#xff0c;类似于传统的手写签名&#xff0c;可标识签名文档的人员。与手写签名不同&#xff0c;数字签名难以伪造&#xff0c;因为其包含签名者唯一的加密信息。为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) 此博客解决&#xff0c;redis加入集群后&#xff0c;是用于停掉后重启&#xff0c;将nodes.conf中的旧的Ip替换为新的IP&#xff0c;从而达到不会因为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 | 机器学习之数据清洗

机器学习前的数据清洗&#xff08;异常值检验&#xff0c;标准化处理&#xff0c;哑变量处理&#xff09; Python | 机器学习之数据清洗 机器学习 - 基础概念 - scikit-learn - 数据预处理​​​​​​​ 数据的标准化&#xff08;离差标准化、log函数转换、atan函数转换、z…...

力扣:509. 斐波那契数(动态规划,附带递归版本) 详细讲解动态规划的思路

题目&#xff1a; 斐波那契数 &#xff08;通常用 F(n) 表示&#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始&#xff0c;后面的每一项数字都是前面两项数字的和。也就是&#xff1a; F(0) 0&#xff0c;F(1) 1 F(n) F(n - 1) F(n - 2)&#xff0c;其中…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

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…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...