代码随想录训练营Day51
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 前言
- 一、不同的子序列
- 二、两个字符串的删除操作
- 三、编辑距离
前言
提示:这里可以添加本文要记录的大概内容:
今天是跟着代码随想录刷题的第51天,主要学习了不同的子序列、两个字符串的删除操作、编辑距离
提示:以下是本篇文章正文内容,下面案例可供参考
一、不同的子序列
思路:
这道题的dp[i][j]是[0,i-1]的s最多能有多少种方式组合成[0,j-1],初始化dp[0][i]空字符串组成不了,所以是0,dp[i][0]是字符串中找多少个方式是空字符串,那就是全部删除掉就可以了,所以只有这一种,至于dp[0][0]空字符串本身就是空字符串不用删减所以也是一种,递推公式如果s[i-1]==t[j-1],则dp[i][j]=dp[i-1][j-1]+dp[i-1][j]中, dp[i-1][j-1]是最后一个i来的时候,一共多了多少种组合,dp[i-1][j]是上一个有多少种组合,所以合理,如果最后一个元素不相等,就说明加不加最后一个元素没区别,直接等于dp[i-1][j]
代码:
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<=t.size();i++) dp[0][i]=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]+dp[i-1][j];//dp[i-1][j-1]是最后一个i来的时候,一共多了多少种组合,dp[i-1][j]是上一个有多少种组合}else{dp[i][j]=dp[i-1][j];}}}return dp[s.size()][t.size()];}
};
二、两个字符串的删除操作
思路:
关键是dp数组的定义,dp[i][j]表示[0,i-1]和[0,j-1]两个字符串如果要变成相同所需要的最小步数,这里i-1和j-1是因为初始化比较简单,递推公式推导见文中的注释
代码:
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<uint64_t>> dp(word1.size()+1,vector<uint64_t>(word2.size()+1,0));//dp[i][j]表示[0,i-1]和[0,j-1]两个字符串如果要变成相同所需要的最小步数for(int i=0;i<=word1.size();i++)//初始化{dp[i][0]=i;}for(int i=0;i<=word2.size();i++)//初始化{dp[0][i]=i;}for(int i=1;i<=word1.size();i++){for(int j=1;j<=word2.size();j++){if(word1[i-1]==word2[j-1]){dp[i][j]=dp[i-1][j-1]; //如果最后两个是一样的就说明变成一样需要的步数和去掉这两个没区别 }else{dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);//如果最后两个不一样,就看到底是哪个变动需要的步数,变动的那个把那行给去掉一个加上去掉需要的步数1}}}return dp[word1.size()][word2.size()];}
};
三、编辑距离
思路:
如果最后两个不一样,可能是增加删减或者替换,先讲一下删除元素,删除元素就是,我要删除的那个元素不管,上面缺一个元素i-1和下面j先操作,操作完以后,把上面那个元素删除就好了,增加和删减其实一样,因为我增加去迎合你,是不是就相当于你减去一个迎合我的操作是一样的,如果是替换,那么我结尾的元素都不用管了,把i-1,j-1的元素操作完成,然后最后一对两个元素换成一样的一步骤就可以,所以是dp[i-1][j-1]+1
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<uint64_t>> dp(word1.size()+1,vector<uint64_t>(word2.size()+1,0));//dp[i][j]表示[0,i-1]和[0,j-1]两个字符串如果要变成相同所需要的最小步数for(int i=0;i<=word1.size();i++)//初始化{dp[i][0]=i;}for(int i=0;i<=word2.size();i++)//初始化{dp[0][i]=i;}for(int i=1;i<=word1.size();i++){for(int j=1;j<=word2.size();j++){if(word1[i-1]==word2[j-1]){dp[i][j]=dp[i-1][j-1]; //如果最后两个是一样的就说明变成一样需要的步数和去掉这两个没区别 }else{dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);//如果最后两个不一样,可能是增加删减或者替换}}}return dp[word1.size()][word2.size()];}
};相关文章:
代码随想录训练营Day51
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、不同的子序列二、两个字符串的删除操作三、编辑距离 前言 提示:这里可以添加本文要记录的大概内容: 今天是跟着代码随想录刷题的第…...
C#上位机与PLC
在工业自动化的舞台上,C#上位机与PLC之间的通信是一曲精妙绝伦的交响乐。今天,我们将一起揭开C#上位机与PLC通信的三种神秘实现方法,探索它们如何共同谱写出高效、稳定、灵活的工业自动化乐章。 序幕:通信的“前奏” 在深入了解…...
CVE-2018-8120漏洞提权:Windows 7的安全剖析与实战应用
CVE-2018-8120漏洞提权:Windows 7的安全剖析与实战应用 在网络安全的世界里,漏洞利用常常是攻击者用来获取系统控制权的捷径。2018年发现的CVE-2018-8120漏洞,针对Windows 7操作系统,提供了一个这样的途径。本文将深入分析这一漏…...
Python-正则表达式
目录 一、打开正则表达式 二、正则表达式的使用 1、限定符 (1)x*:*表示它前面的字符y 可以有0个或多个; (2)x:表示它前面的字符可以出现一次以上;(只可以匹配多次&…...
教程:在 Kubernetes 集群上部署 WordPress 网站
WordPress 是专为每个人设计的开源软件,强调创建网站、博客或应用程序的可访问性、性能、安全性和易用性。WordPress 是一个基于 PHP 的内容管理系统(CMS),使用 MySQL 作为数据存储,目前很多网站、电商独立站、个人博客…...
聊一聊 C# 弱引用 底层是怎么玩的
一:背景 1. 讲故事 最近在分析dump时,发现有程序的卡死和WeakReference有关,在以前只知道怎么用,但不清楚底层逻辑走向是什么样的,借着这个dump的契机来简单研究下。 二:弱引用的玩法 1. 一些基础概念 …...
蜘蛛池规矩采集优化与运用技巧 什么是蜘蛛池/SEO蜘蛛池怎么养?(蜘蛛池新手入门虚良SEO)
作为一名网络内容修改,我常常需求从各种网站上收集文章并转载到咱们的网站上。而在这个过程中,我深深感受到了蜘蛛池对我的帮助。今日,我就来共享一下我对蜘蛛池收集规矩的亲自感受。 归纳 本文将分9个方面具体介绍蜘蛛池收集规矩的长处和运…...
SerDes介绍以及原语使用介绍(1)OSERDESE2
文章目录 前言:为什么需要serdes一、OSERDESE2框图二、OSERDESE2端口信号二、OSERDESE2原语参数三、OSERDESE2时序3.1、SDR模式3.2、DDR模式3.3、DDR模式下三态传输 前言:为什么需要serdes 需要 SerDes(串行器/解串器)主要是为了…...
基于单片机和组态王的温度监控系统的设计
摘 要 : 介绍了以 MSP430 单片机为核心 , 建立基于 DS18B20 和组态王的温度采集和监控系统。主要研究了单片机和组态王的通用通讯协议。按照 KingView 提供的通信协议 , 设计组态王与单片机的通信程序 , 实现了组态王与M SP430 单片机的直接串行通讯。在中药提取装置的…...
unity 导入的模型设置讲解
咱们先讲Model这一栏 Model Scene:场景级属性,例如是否导入灯光和照相机,以及使用什么比例因子。 Scale Factor:缩放因子(也就是模型导入后大小如果小了或者大了在这里直接改是相当于该模型的大小的,而且在…...
汽车 vSOC安全运营管理平台开发解决方案
汽车 vSOC 安全解决方案 一、引言 随着汽车行业的快速发展,汽车的智能化和互联化程度越来越高,汽车网络安全问题也日益凸显。汽车 vSOC(Vehicle Security Operations Center)作为汽车网络安全的重要组成部分,其作用越来越受到重视。本方案旨在提供一套可实施落地的汽车 vS…...
python 第三方库
一、什么是第三方库 python的三方库指的是,需要通过pip install 安装后才能使用的 python 工具 三方库有很多: 做web自动化测试的库:selenium单元测试框架:pytest、unittest做app自动化测试:Python-Appium-Client做接…...
VMware Workstation环境下,DHCP服务的安装配置,用ubuntu来测试
需求说明: 某企业信息中心计划使用IP地址17216.11.0用于虚拟网络测试,注册域名为xyz.net.cn.并将172.16.11.2作为主域名的服务器(DNS服务器)的IP地址,将172.16.11.3分配给虚拟网络测试的DHCP服务器,将172.16.11.4分配给虚拟网络测试的web服务器,将172.16.11.5分配给FTP服务器…...
CSS实现文字颜色渐变
直接上代码和效果图: <p class"linecolor">文字颜色渐变</p><style type"text/css">.linecolor{font-size: 30px;background-image:-webkit-linear-gradient(bottom,red,#fd8403,yellow);-webkit-background-clip:text;-web…...
《每天5分钟用Flask搭建一个管理系统》第4章:模板渲染
第4章:模板渲染 4.1 模板的概念和使用 模板是一种用于生成输出的方法,它允许您将Python代码和HTML标记混合在一起,从而创建动态网页。 示例代码:基本模板 <!-- templates/home.html --> <!DOCTYPE html> <html…...
逆向学习汇编篇:指令的操作
本节课在线学习视频(网盘地址,保存后即可免费观看): https://pan.quark.cn/s/660c759dea95 在逆向工程中,深入理解汇编语言的指令操作是至关重要的。汇编指令是计算机硬件与软件之间的桥梁,它们直…...
VB.net实战(VSTO):VSTOwpf体验框架打包教程
如果是考虑到Wps用户较多,就不建议采用侧边栏的形式 只是个体验框架,界面未作美化,office的用户可以用任意一种窗体,喜欢那个界面就写那个界面,wps的侧边栏只能弹出一部分,每次需要的手动拖动。 打包了案例…...
Jquery 获得Form下的所有text、checkbox等表单的值
Jquery使用表单我主要是想获得某一个表单下的所有text获得checkbox的值: 可以这样写: var parameter{}; $("input[typetext]",document.forms[0]).each(function(){ alert(this.name); }); 获得所有名为hobby的选中的checkbox的值和form2下的所有text的值 function s…...
stl之string
构造函数 void test1() {string s1;//不传参cout << s1 << endl;string s2("123456");cout << s2 << endl;string s3(s2);cout << s3 << endl;string s4(s2, 1, 5);cout << s4 << endl;string s5("123456&quo…...
Vue3学习笔记<->nginx部署vue项目
安装nginx vue项目通常部署到nginx上,所以先安装一个nginx。为了方便安装的是windows版nginx,解压就能用。 项目参考上一篇文章《Vue3学习笔记<->创建第一个vue项目》《Vue3学习笔记<->创建第一个vue项目》…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
