动态规划编译距离
583. 两个字符串的删除操作
方法:dp
状态表示:以i-1和j-1为结尾的字符串world1和world2,抵达相同的字符串所需的最少操作数
属性:最小值
状态计算:world1[i-1]和world2[j-1]相同dp[i][j] = dp[i-1][j-1];
world1[i-1]和world2[j-1]不相同,删去world1:dp[i-1][j] + 1,就变为以i-2和j-1为结尾的字符串world1和world2,抵达相同的字符串所需的最少操作数;同理删除world2:dp[i][j-1] + 1;同时删除world1和world2:dp[i-1][j-1] + 2;
细心的话可以发现dp[i-1][j] + 1 = dp[i-1][j-1] = dp[i][j-1] + 1
所以递推公式dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1)
class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size(), m = word2.size();vector<vector<int>> dp(n + 1, vector<int> (m + 1, 0));for (int i = 0; i <= n; ++i) dp[i][0] = i;for (int i = 0; i <= m; ++i) dp[0][i] = i;for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++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);}return dp[n][m];}
};$时间复杂度O(n*m),空间复杂度O(n*m);
方法2:dp
状态表示:以i-1和j-1为结尾的字符串world1和world2,最大的相同子序列的集合为dp[i][j]
class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size(), m = word2.size();vector<vector<int>> dp(n + 1, vector<int> (m + 1, 0));for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j) {if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}return n + m - dp[n][m] * 2;}
};$时间复杂度O(n*m),空间复杂度O(n*m);
72. 编辑距离
方法:dp
简单说一下增加和删除的效果是一样的所以就统一删除了
替换就是在dp[i-1][j-1]的基础上加一个操作
其他的都差不多
class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size(), m = word2.size();vector<vector<int>> dp(n + 1, vector<int> (m + 1, 0));for (int i = 0; i <= n; ++i) dp[i][0] = i;for (int i = 0; i <= m; ++i) dp[0][i] = i;for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++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], dp[i][j-1], dp[i-1][j-1]}) + 1;}return dp[n][m];}
};$时间复杂度O(n*m),空间复杂度O(n*m);
相关文章:
动态规划编译距离
583. 两个字符串的删除操作方法:dp状态表示:以i-1和j-1为结尾的字符串world1和world2,抵达相同的字符串所需的最少操作数属性:最小值状态计算:world1[i-1]和world2[j-1]相同dp[i][j] dp[i-1][j-1];world1[i-1]和world…...
Netty 教程 – 解码器详解
TCP以流的方式进行数据传输,上层的应用为了对消息进行区分,往往采用如下方式 固定消息长度,累计读取到长度和定长LEN的报文后,就认为读取到了个完整的消息,然后将计数器位置重置在读取下一个报文内容将回车换行符作为…...
Allegro如何自动添加测试点操作指导
Allegro如何自动添加测试点操作指导 在做PCB设计的时候,在一些应用场合下需要给PCB上的网络添加测试点,如下图 测试点除了可以手动逐个添加之外,Allegro还支持自动添加测试点,具体操作如下 点击Manufacture点击Testprep...
【CSS】CSS 背景设置 ③ ( 背景位置-长度值设置 | 背景位置-长度值方位值同时设置 )
文章目录一、背景位置-长度值设置二、背景位置-长度值方位值同时设置三、完整代码示例一、背景位置-长度值设置 长度值设置 效果展示 : 设置背景位置为具体值 10px 50px : 粉色区域是盒子的区域 , 图片背景位于盒子位置 x 轴方向 10 像素 , y 轴方向 50 像素 ; 在水平方向上 ,…...
AbTest —— 不同场景下的应用模式
文章目录不同人群眼中的 AbTestAbTest 不同的功能倚重用户关联性弱,经典场景为 Feed - 部门组织形式大多非垂直业务用户关联性强,经典场景为 垂类/工具类APP;部门组织形式大多为垂直业务康为定律-组织决定产品形态不同应用模式下服务构建开机…...
fast-api 一款快速将spring的bean发布成接口并生产对应swagger文档调试的轻量级工具
fast-api简介背景开发痛点:分析需求实战fast-api快速上手1. 引入依赖2. FastApiMapping标记service对象3. swagger2/knife4j 在线测试进阶使用开启调试模式支持指定类或包目录发布如何关闭fast-api自定义fast-api的前缀写在最后简介 fast-api 一款快速将spring的bean(service)发…...
以公益之名 让人类发现数学之美
目录 1.品牌理念高举高打 2.创新赛制 赋能品牌 3.全球化的品牌传播 9月26日,2022阿里巴巴全球数学竞赛获奖名单公布,4座金杯分别由平均年龄25岁,来自美国麻省理工学院、美国布朗大学、北京大学在读数学博士斩获。77位获奖者中00后超五成引热…...
JUC并发编程之HashMap(jdk1.7版本)-底层源码探究
目录 JUC并发编程之HashMap(jdk1.7版本)-底层源码探究 HashMap底层源码 - jdk1.7 基本概念 -采取层层递进,问答式 存储Key-Value的结构 常量和成员变量 构造方法 put方法 inflateTable方法 hash方法 indexFor方法 addEntry方法 resize方法 createEntry…...
QT Q_OBJECT 和 signals/slots
Q_OBJECT宏展开 #define Q_OBJECT \ public: \QT_WARNING_PUSH \Q_OBJECT_NO_OVERRIDE_WARNING \static const QMetaObject staticMetaObject; \virtual const QMetaObject *metaObject() const; \virtual void *qt_metacast(const char *); \virtual int qt_metacall(QMetaOb…...
APM新添加UAVCAN设备
简介 UAVCAN是一种轻量级协议,旨在通过CAN总线在航空航天和机器人应用中实现可靠通信。要实现通信,最基本需要data_type_ id, signature、数据结构、设备程序初始化。 添加设备数据结构文件(.uavcan格式) 1.在以下路径添加设备数据结构文件,根据设备类…...
【C++】string类基本用法
文章目录string类基本用法1. 为什么要学习string类?1.1 C语言中的字符串2. 标准库中的string类2.1 string类2.2 string类的常用接口说明小试牛刀1. 仅仅反转字母2. 字符串中第一个唯一字符3. 字符串中最后一个单词的长度string类基本用法 1. 为什么要学习string类&…...
KDZD耐电压高压击穿强度测试仪
一、技术参数 01、输入电压: 交流 220 V。 02、输出电压: 交流 0--50KV ; 直流 0—50kv 。 03、电器容量:3KVA。 04、高压分级:0—50KV,(全程可调)。 05、升压速率:0.1KV/s-…...
数组和指针面试题的补充(细的抠jio)
生命是一条艰险的峡谷,只有勇敢的人才能通过。 ——米歇潘 说明:用的vs都是x86的环境,也就是32位平台。 建议:对于难题来说,一定要配合画图来解决问题。 第一题: #include<stdio.h> int…...
Java多线程基础
文章目录Java多线程基础一、什么是进程与线程?二、线程和进程的区别【重点】三、线程的创建方式【重点】1. 继承Thread类2. 实现Runnable接口3. lambda 表达式四、Thread的常见属性线程中断自己定义一个标志位Thread类提供的静态方法线程的状态Java多线程基础 一、…...
爆品分析第5期 | 一条视频带货3700+,这款斋月不锈钢厨具套装火了!
俗话说民以食为天,吃在任何一种文化中都占据重要的位置,要做出一道美味佳肴,除了食材、烹饪者的自身厨艺之外,还少不了一口好锅。新冠疫情以来,全世界范围内的封闭让很多人养成了居家做饭的习惯,不仅为厨具…...
团队管理的七个要点
要掌握团队管理的要点和做好团队管理工作,不是一件容易的事,但也远非想象中那么难。首先,我个人比较推荐所有团队管理者都能阅读下《经理人参阅:团队管理》(注意该书仅可其官网获得)这本佳作。相信会为你带…...
Go语言容器之map、list和nil
一、map map和C中map一样,里面存放的是key-value键值对在Go中map是引用类型,声明语法:var map变量名 map[key的类型]value的类型package mainimport "fmt"func main() {var mp map[string]intmpls : map[string]int{"one&quo…...
软件测试的案例分析 - 闰年1
(这是关于博客质量分的测试 https://www.csdn.net/qc) 我们谈了不少测试的名词, 软件是人写的, 测试计划和测试用例也是人写的, 人总会犯错误。错误发生之后, 总有人问: 为什么这个bug 没有测出来啊?! 我们看看一类简单的bug是如何发生的,以及如何预防…...
【强化学习】强化学习数学基础:值函数近似
值函数近似Value Function ApproximationMotivating examples: curve fittingAlgorithm for state value estimationObjective functionOptimization algorithmsSelection of function approximatorsIllustrative examplesSummary of the storyTheoretical analysisSarsa with …...
JVM系列——Java与线程,介绍线程原理和操作系统的关系
并发不一定要依赖多线程(如PHP中很常见的多进程并发)。 但是在Java里面谈论并发,基本上都与线程脱不开关系。因此我们讲一下从Java线程在虚拟机中的实现。 线程的实现 线程是比进程更轻量级的调度执行单位。 线程的引入,可以把一个进程的资源分配和执行调…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践
前言:本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中,跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南,你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案,并结合内网…...
