当前位置: 首页 > 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;其中…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

大话软工笔记—需求分析概述

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

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...