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

代码随想录训练营day45|115.不同的子序列,583. 两个字符串的删除操作,72. 编辑距离

115.不同的子序列

题目
dp[i][j]表示的是在以是s[j]为结尾的字符串中最多可以找到几种组成以t[i]为结尾的字符串的方式。
如果s[i]==t[j],
1.利用第i个和第j个匹配,在j-1中寻找i-1.
2.不适用这两个进行匹配,在j-1中寻找i
如果s[i]!=t[j]
则只能在j-1中寻找i

 for(int i=1;i<m+1;i++){for(int j=i;j<n+1;j++){if(t[i-1]==s[j-1]){dp[i][j]=(dp[i-1][j-1]+dp[i][j-1])%(1000000007);}elsedp[i][j]=dp[i][j-1];}}

完整代码:

class Solution {
public:int numDistinct(string s, string t) {int m=t.size();int n=s.size();vector<vector<int>> dp(m+1,vector<int>(n+1,0));for(int j=0;j<n+1;j++)dp[0][j]=1;for(int i=1;i<m+1;i++){for(int j=i;j<n+1;j++){if(t[i-1]==s[j-1]){dp[i][j]=(dp[i-1][j-1]+dp[i][j-1])%(1000000007);}elsedp[i][j]=dp[i][j-1];}}return dp[m][n];}
};

583. 两个字符串的删除操作

方法一

找出两个字符串的最长公共子序列,然后用两个字符串的长度之和减去2*dp[m][n]

方法二

dp[i][j]代表以word1[i]和word2[j]为结尾的字符串删成相同的字符串需要的最小步数
if(word1[i]==word2[j]){
dp[i][j]=dp[i-1][j-1];
}
else{
dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
//分别删除第i个和第j个后剩余字符串的最小步数,再加上前面删除的一个步数。
}

class Solution {
public:int minDistance(string word1, string word2) {int m=word1.size();int n=word2.size();vector<vector<int>> dp(m+1,vector<int>(n+1,0));for(int i=1;i<m+1;i++){dp[i][0]=i;}for(int j=1;j<n+1;j++)dp[0][j]=j;for(int i=1;i<m+1;i++){for(int j=1;j<n+1;j++){if(word1[i-1]==word2[j-1]){dp[i][j]=dp[i-1][j-1];}elsedp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);//分别删除第i个和第j个后剩余字符串的最小步数,再加上前面删除的一个步数。}}return dp[m][n];}
};

72. 编辑距离

如果word1[i]和word2[j]不相同,有三种方式:
1.修改第i个使他与j相同,要dp[i-1][j-1]+1步
2.删除第i个,要dp[i-1][j]+1
3.删除第j个,要dp[i][j-1]+1

插入一个和另一个相等的字符和删除另一个的步数一样,所以可以只用讨论删除的。

if(word1[i-1]!=word2[j-1]){	dp[i][j]=min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1;
}
elsedp[i][j]=dp[i-1][j-1];

注意:是i-1和j-1,因为i的长度比m多一个。

完整代码:

class Solution {
public:int minDistance(string word1, string word2) {int m=word1.size();int n=word2.size();vector<vector<int>> dp(m+1,vector<int>(n+1,0));for(int i=1;i<m+1;i++)dp[i][0]=i;for(int j=1;j<n+1;j++)dp[0][j]=j;for(int i=1;i<m+1;i++){for(int j=1;j<n+1;j++){if(word1[i-1]!=word2[j-1]){	dp[i][j]=min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1));}elsedp[i][j]=dp[i-1][j-1];}}return dp[m][n];}
};

相关文章:

代码随想录训练营day45|115.不同的子序列,583. 两个字符串的删除操作,72. 编辑距离

115.不同的子序列 题目 dp[i][j]表示的是在以是s[j]为结尾的字符串中最多可以找到几种组成以t[i]为结尾的字符串的方式。 如果s[i]t[j]&#xff0c; 1.利用第i个和第j个匹配&#xff0c;在j-1中寻找i-1. 2.不适用这两个进行匹配&#xff0c;在j-1中寻找i 如果s[i]&#xff01;…...

椋鸟C++笔记#7:标准模板库STL初识

文章目录 标准模板库&#xff08;Standard Template Library&#xff09;STL的版本P.J.版RW版SGI版 STL的组成部分 萌新的学习笔记&#xff0c;写错了恳请斧正。 标准模板库&#xff08;Standard Template Library&#xff09; 标准模板库STL&#xff0c;是C标准库的一个非常重…...

滴滴嘀嗒,出行行业响起Robotaxi“倒计时”

文&#xff1a;互联网江湖 作者&#xff1a;刘致呈 前几天&#xff0c;各大出行平台的半年报陆续披露完毕&#xff0c;有的还在亏损&#xff0c;但也有人开始盈利。 如祺出行上市后的首份半年报营收10.37亿&#xff0c;同比增长13.6%。上半年运营亏损为2.56亿元&#xff0c;同…...

【MATLAB源码-第264期】基于matlab的跳频通信系统仿真,采用MSK调制方式,差分解调;输出误码率曲线和各节点波形图。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 跳频通信系统是一种能够提高通信抗干扰能力的技术&#xff0c;它通过在传输过程中不断地改变载波频率来避开干扰或者窃听。在这套跳频通信系统中&#xff0c;我们采用了最小频移键控&#xff08;MSK&#xff09;作为调制方式…...

如何在多台电脑上同步 VSCode配置和插件

上一篇文章最新前端开发VSCode高效实用插件推荐清单总结了前端开发实用的插件&#xff0c;换电脑的时候怎么同步这些配置与插件呢&#xff0c;难道又要重新安装一遍吗&#x1f631; 现在就来聊聊要在多台电脑上同步 VSCode配置和插件的几种方法&#xff1a; 方法一&#xff1…...

深度优先算法,广度优先算法,hill climbing,贪心搜索,A*算法,启发式搜索算法是什么,比起一般搜索法算法有什么区别

深度优先算法&#xff08;Depth-First Search, DFS&#xff09; 深度优先搜索是一种用于遍历或搜索树或图的算法。它沿着树的深度遍历树的节点&#xff0c;尽可能深地搜索树的分支。当节点v的所在边都已被探寻过&#xff0c;搜索将回溯到发现节点v的那条边的起始节点。这一过程…...

《python语言程序设计》2018版第8章第14题金融:信用卡号合法性 利用6.29题

一、之前6.29题我做的代码 这是用数字来进行分辨的 is_txt 4383576018402626 #合法def split_the_data_even(vis_n):current_a1 vis_n // 10000a_t1 vis_n % 10000# print("1th", a_t1)a_t2 current_a1 % 10000# print("2th", a_t2)current_a3 curre…...

QT 基础学习

1> 使用绘制事件完成钟表的绘制 头文件 #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QPainter> #include <QDebug> #include <QTime> #include <QTimer> #include <QDateTime> //#include <string> #includ…...

【Gephi】可视化教程

此教程专供欣欣向荣及其舍友使用 文章目录 导入数据上色改变布局设置节点大小统计拓扑结构输出图形保存文件 导入数据 点击【文件】-【导入电子表格】 先选择csv格式的network 直接下一步 点击完成 【图的类型】改为“有向的” 点击确认 会弹出报错&#xff0c;直接clos…...

演化式原型开发-系统架构师(六十五)

1快速迭代式的原型开发能够有效控制成本&#xff0c;&#xff08;&#xff09;是指开发过程中逐步改进和细化原型直到产生目标系统。 A可视化原型开发 B抛弃式原型开发 C演化式原型开发 D增量式原型开发 解析&#xff1a; 原型开发分为两大类:快速原型开发&#xff08;抛弃…...

初识爬虫4

1.理解代理ip&#xff0c;正向代理和反向代理 2.代理ip分类&#xff0c;根据匿名度分类&#xff1a;透明&#xff0c;匿名&#xff0c;高匿 3.防止频繁向同一个域名发送请求被封ip,需使用代理ip # -*- coding: utf-8 -*- import requestsurl https://www.baidu.comproxies {…...

Golang | Leetcode Golang题解之第387题字符串中的第一个唯一字符

题目&#xff1a; 题解&#xff1a; type pair struct {ch bytepos int }func firstUniqChar(s string) int {n : len(s)pos : [26]int{}for i : range pos[:] {pos[i] n}q : []pair{}for i : range s {ch : s[i] - aif pos[ch] n {pos[ch] iq append(q, pair{ch, i})} e…...

【CanMV K230 AI视觉】 人体检测

【CanMV K230 AI视觉】 人体检测 人体检测 动态测试效果可以去下面网站自己看。 B站视频链接&#xff1a;已做成合集 抖音链接&#xff1a;已做成合集 人体检测 人体检测是判断摄像头画面中有无出现人体&#xff0c;常用于人体数量检测&#xff0c;人流量监控以及安防监控等。…...

解决浏览器自动将http网址转https

删除浏览器自动使用https的方式 在浏览器地址栏输入&#xff1a;chrome://net-internals/#hsts PS:如果是edge浏览器可输入&#xff1a;edge://net-internals/#hsts 在Delete domain security policies搜索框下&#xff0c;输入要删除的域名,然后点击delete 解决方法&#…...

linux邮件配置

1. 非加密邮件配置 cat <<EOF > smtp.sh #!/bin/bash providerqq account3282941991 passwordzqdtygmmndsgb22i3ee echo "Waiting For A Moment..." rpm -qa sendmail &> /dev/null|| yum install sendmail -y >/dev/null echo " set from$…...

基于springboot+vue乒乓球预约管理系统

基于springbootvuemysql实现的乒乓球预约管理系统&#xff08;源码数据库部署视频&#xff09; ### 主要技术 SpringBoot、LayUI、Vue、MySQL ### 系统角色 用户、管理员 ### 系统功能 前台&#xff1a; 首页、乒乓球场、公告信息、留言反馈、个人中心 后台&#xff1a; …...

Linux 基础命令-文件权限与所有权

1. 文件权限概述 在Linux中&#xff0c;每个文件和目录都有与之关联的权限和所有权&#xff0c;来控制谁可以访问、修改或执行文件。文件权限与所有权可以防止未经授权的用户对文件进行访问或修改。 1.1 文件权限的组成 每个文件在Linux系统中都有三种类型的权限&#xff1a…...

气压测试实验(用IIC)

I2C: 如果没有I2c这类总线&#xff0c;连接方法可能会如下图&#xff1a; 单片机所有的通讯协议&#xff0c;无非是建立在引脚&#xff08;高低电平的变换高低电平持续的时间&#xff09;这二者的组合上&#xff0c;i2c 多了一个clock线&#xff0c;负责为数据传输打节拍。 (i2…...

C++ lambda闭包消除类成员变量

原文链接&#xff1a;https://blog.csdn.net/qq_51470638/article/details/142151502 一、背景 在面向对象编程时&#xff0c;常常要添加类成员变量。 然而类成员一旦多了之后&#xff0c;也会带来干扰。 拿到一个类&#xff0c;一看成员变量好几十个&#xff0c;就问你怕不…...

等待唤醒机制和阻塞队列

1. 等待唤醒机制 由于线程的随机调度&#xff0c;可能会出现“线程饿死”的问题&#xff1a;也就是一个线程加锁执行&#xff0c;然后解锁&#xff0c;其他线程抢不到&#xff0c;一直是这个线程在重复操作 void wait() 当前线程等待&#xff0c;直到被其他线程唤醒 void no…...

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

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

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...