代码随想录训练营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], 1.利用第i个和第j个匹配,在j-1中寻找i-1. 2.不适用这两个进行匹配,在j-1中寻找i 如果s[i]!…...
椋鸟C++笔记#7:标准模板库STL初识
文章目录 标准模板库(Standard Template Library)STL的版本P.J.版RW版SGI版 STL的组成部分 萌新的学习笔记,写错了恳请斧正。 标准模板库(Standard Template Library) 标准模板库STL,是C标准库的一个非常重…...
滴滴嘀嗒,出行行业响起Robotaxi“倒计时”
文:互联网江湖 作者:刘致呈 前几天,各大出行平台的半年报陆续披露完毕,有的还在亏损,但也有人开始盈利。 如祺出行上市后的首份半年报营收10.37亿,同比增长13.6%。上半年运营亏损为2.56亿元,同…...
【MATLAB源码-第264期】基于matlab的跳频通信系统仿真,采用MSK调制方式,差分解调;输出误码率曲线和各节点波形图。
操作环境: MATLAB 2022a 1、算法描述 跳频通信系统是一种能够提高通信抗干扰能力的技术,它通过在传输过程中不断地改变载波频率来避开干扰或者窃听。在这套跳频通信系统中,我们采用了最小频移键控(MSK)作为调制方式…...
如何在多台电脑上同步 VSCode配置和插件
上一篇文章最新前端开发VSCode高效实用插件推荐清单总结了前端开发实用的插件,换电脑的时候怎么同步这些配置与插件呢,难道又要重新安装一遍吗😱 现在就来聊聊要在多台电脑上同步 VSCode配置和插件的几种方法: 方法一࿱…...
深度优先算法,广度优先算法,hill climbing,贪心搜索,A*算法,启发式搜索算法是什么,比起一般搜索法算法有什么区别
深度优先算法(Depth-First Search, DFS) 深度优先搜索是一种用于遍历或搜索树或图的算法。它沿着树的深度遍历树的节点,尽可能深地搜索树的分支。当节点v的所在边都已被探寻过,搜索将回溯到发现节点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 直接下一步 点击完成 【图的类型】改为“有向的” 点击确认 会弹出报错,直接clos…...
演化式原型开发-系统架构师(六十五)
1快速迭代式的原型开发能够有效控制成本,()是指开发过程中逐步改进和细化原型直到产生目标系统。 A可视化原型开发 B抛弃式原型开发 C演化式原型开发 D增量式原型开发 解析: 原型开发分为两大类:快速原型开发(抛弃…...
初识爬虫4
1.理解代理ip,正向代理和反向代理 2.代理ip分类,根据匿名度分类:透明,匿名,高匿 3.防止频繁向同一个域名发送请求被封ip,需使用代理ip # -*- coding: utf-8 -*- import requestsurl https://www.baidu.comproxies {…...
Golang | Leetcode Golang题解之第387题字符串中的第一个唯一字符
题目: 题解: 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站视频链接:已做成合集 抖音链接:已做成合集 人体检测 人体检测是判断摄像头画面中有无出现人体,常用于人体数量检测,人流量监控以及安防监控等。…...
解决浏览器自动将http网址转https
删除浏览器自动使用https的方式 在浏览器地址栏输入:chrome://net-internals/#hsts PS:如果是edge浏览器可输入:edge://net-internals/#hsts 在Delete domain security policies搜索框下,输入要删除的域名,然后点击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实现的乒乓球预约管理系统(源码数据库部署视频) ### 主要技术 SpringBoot、LayUI、Vue、MySQL ### 系统角色 用户、管理员 ### 系统功能 前台: 首页、乒乓球场、公告信息、留言反馈、个人中心 后台: …...
Linux 基础命令-文件权限与所有权
1. 文件权限概述 在Linux中,每个文件和目录都有与之关联的权限和所有权,来控制谁可以访问、修改或执行文件。文件权限与所有权可以防止未经授权的用户对文件进行访问或修改。 1.1 文件权限的组成 每个文件在Linux系统中都有三种类型的权限:…...
气压测试实验(用IIC)
I2C: 如果没有I2c这类总线,连接方法可能会如下图: 单片机所有的通讯协议,无非是建立在引脚(高低电平的变换高低电平持续的时间)这二者的组合上,i2c 多了一个clock线,负责为数据传输打节拍。 (i2…...
C++ lambda闭包消除类成员变量
原文链接:https://blog.csdn.net/qq_51470638/article/details/142151502 一、背景 在面向对象编程时,常常要添加类成员变量。 然而类成员一旦多了之后,也会带来干扰。 拿到一个类,一看成员变量好几十个,就问你怕不…...
等待唤醒机制和阻塞队列
1. 等待唤醒机制 由于线程的随机调度,可能会出现“线程饿死”的问题:也就是一个线程加锁执行,然后解锁,其他线程抢不到,一直是这个线程在重复操作 void wait() 当前线程等待,直到被其他线程唤醒 void no…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
