代码随想录训练营第五十六天| 583. 两个字符串的删除操作 、72. 编辑距离
583. 两个字符串的删除操作
题目链接/文章讲解/视频讲解:代码随想录
1.代码展示
//583.两个字符串的删除操作
int minDistance(string word1, string word2) {//step1 构建dp数组,dp[i][j]的含义是要使以i-1为结尾的word1和以j-1为结尾的word2//删除其元素后相同所需最小的删除步数vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));//step2 状态转移方程//if (word1[i - 1] == word[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, dp[i - 1][j - 1] + 2);//对应着三种情况,删除word1[i - 1]或者word2[j - 1]或者同时删除//step3 初始化for (int i = 0; i <= word1.size(); i++) {dp[i][0] = i;}for (int j = 0; j <= word2.size(); j++) {dp[0][j] = j;}//step4 开始遍历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, dp[i - 1][j - 1] + 2 });}}}return dp[word1.size()][word2.size()];
}
2.本题小节
思考: 首先明确dp[i][j]的含义是下标以i-1为结尾的word1和以下标为j-1结尾的word2删除元素相等所需的最少步骤。当word1[i - 1] == word2[j - 1]时,此时不需要删除元素,因此dp[i][j] = dp[i - 1][j - 1];当不相等时,此时既可以删除word1下标i-1处的元素,对应的是dp[i - 1][j] + 1,也可以删除word2下标j-1处的元素,对应的是dp[i][j-1] + 1,也可以是同时删除掉,对应的是dp[i - 1][j - 1] + 2,因此dp[i][j]从上面三种情况中选择最小的。初始化时要注意,dp[i][0]对应的位置初始化为i,dp[0][j]对应位置初始化为j,这个很好想。
步骤:注意思考的内容,按照步骤来即可。
72. 编辑距离
题目链接/文章讲解/视频讲解:代码随想录
1.代码展示
//72.编辑距离
int minDistance(string word1, string word2) {//step1 构建dp数组,dp[i][j]的含义是要使以i-1为结尾的word1和以j-1为结尾的word2//相同需要操作(增加、删减、替换)的次数vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));//step2 状态转移方程//if (word1[i - 1] == word[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, dp[i - 1][j - 1] + 1);//对应着三种情况,删掉word1[i - 1](删除),删掉word2[j - 1](增加),替换//step3 初始化for (int i = 0; i <= word1.size(); i++) {dp[i][0] = i;}for (int j = 0; j <= word2.size(); j++) {dp[0][j] = j;}//step4 开始遍历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, dp[i - 1][j - 1] + 1 });}}}return dp[word1.size()][word2.size()];
}
2.本题小节
思考:dp[i][j]的含义是以下标i-1为结尾的word1通过增加,删除,替换能够变成以下标j-1为结尾的word2所需要的最小步骤。当word1[i - 1] == word2[j - 1]时,此时不需要操作,则dp[i][j] = dp[i - 1][j - 1];当不相等时,可以通过删除(删除word1[i - 1])、增加(删除word2[j - 1])、和替换(word1[i - 1]替换为word[j - 1])来操作,分别对应的时dp[i - 1][j] + 1、dp[i][j - 1] + 1、dp[i - 1][j - 1] + 1,选择最小情况,初始化和上题一样。
基本步骤:根据思考和动态规划的步骤来即可。
编辑距离总结:代码随想录
相关文章:
代码随想录训练营第五十六天| 583. 两个字符串的删除操作 、72. 编辑距离
583. 两个字符串的删除操作 题目链接/文章讲解/视频讲解:代码随想录 1.代码展示 //583.两个字符串的删除操作 int minDistance(string word1, string word2) {//step1 构建dp数组,dp[i][j]的含义是要使以i-1为结尾的word1和以j-1为结尾的word2//删除其元…...
hive解决了什么问题
hive出现的原因 Hive 出现的原因主要有以下几个: 传统数据仓库无法处理大规模数据:传统的数据仓库通常采用关系型数据库作为底层存储,这种数据库在处理大规模数据时效率较低。MapReduce 难以使用:MapReduce 是一种分布式计算框架…...
Lumion 和 Enscape 应该选择怎样的笔记本电脑?
Lumion 和 Enscape实时渲染对配置要求高,本地配置不够,如何快速解决: 本地普通电脑可一键申请高性能工作站,资产安全保障,供软件中心,各种软件插件一键获取,且即开即用,使用灵活&am…...
ICCV 2023 | MoCoDAD:一种基于人体骨架的运动条件扩散模型,实现高效视频异常检测
论文链接: https://arxiv.org/abs/2307.07205 视频异常检测(Video Anomaly Detection,VAD)扩展自经典的异常检测任务,由于异常情况样本非常少见,因此经典的异常检测通常被定义为一类分类问题(On…...
Mac电脑怎么使用NTFS磁盘管理器 NTFS磁盘详细使用教程
Mac是可以识别NTFS硬盘的,但是macOS系统虽然能够正确识别NTFS硬盘,但只支持读取,不支持写入。换句话说,Mac不支持对NTFS硬盘进行编辑、创建、删除等写入操作,比如将Mac里的文件拖入NTFS硬盘,在NTFS硬盘里新…...
Java设计模式-结构性设计模式(代理设计模式)
简介 为其他对象提供⼀种代理以控制对这个对象的访问,属于结构型模式。客户端并不直接调⽤实际的对象,⽽是通过调⽤代理,来间接的调⽤实际的对象应用场景 各⼤数码专营店,代理⼚商进⾏销售对应的产品,代理商持有真正的…...
线性空间、子空间、基、基坐标、过渡矩阵
线性空间的定义 满足加法和数乘封闭。也就是该空间的所有向量都满足乘一个常数后或者和其它向量相加后仍然在这个空间里。进一步可以理解为该空间中的所有向量满足加法和数乘的组合封闭。即若 V 是一个线性空间,则首先需满足: 注:线性空间里面…...
【MySQL】CRUD (增删改查) 基础
CRUD(增删改查)基础 一. CRUD二. 新增 (Create)1. 单行数据 全列插入2. 多行数据 指定列插入 三. 查询(Retrieve)1. 全列查询2. 指定列查询3. 查询字段为表达式4. 别名5. 去重:DISTINCT6. 排序…...
Socks5代理IP:保障跨境电商的网络安全
在数字化时代,跨境电商已成为全球商业的重要一环。然而,随着其发展壮大,网络安全问题也逐渐浮出水面。为了确保跨境电商的安全和隐私,Socks5代理IP技术成为了一项不可或缺的工具。本文将深入探讨Socks5代理IP在跨境电商中的应用&a…...
macOS通过钥匙串访问找回WiFi密码
如果您忘记了Mac电脑上的WiFi密码,可以通过钥匙串访问来找回它。具体步骤如下: 1.打开Mac电脑的“启动台”,然后在其他文件中找到“钥匙串访问”。 2.运行“钥匙串访问”应用程序,点击左侧的“系统”,然后在右侧找到…...
Debian11之稳定版本Jenkins安装
官方网址 系统要求 机器要求 256 MB 内存,建议大于 512 MB 10 GB 的硬盘空间(用于 Jenkins 和 Docker 镜像)软件要求 Java 8 ( JRE 或者 JDK 都可以) Docker (导航到网站顶部的Get Docker链接以访问适合您平台的Docker下载安装…...
kakfa 3.5 kafka服务端处理消费者客户端拉取数据请求源码
一、服务端接收消费者拉取数据的方法二、遍历请求中需要拉取数据的主题分区集合,分别执行查询数据操作,1、会选择合适的副本读取本地日志数据(2.4版本后支持主题分区多副本下的读写分离) 三、会判断当前请求是主题分区Follower发送的拉取数据请求还是消费…...
【Linux】进程概念I --操作系统概念与冯诺依曼体系结构
Halo,这里是Ppeua。平时主要更新C语言,C,数据结构算法…感兴趣就关注我吧!你定不会失望。 本篇导航 1. 冯诺依曼体系结构为什么这样设计? 2. 操作系统概念为什么我们需要操作系统呢?操作系统怎么进行管理? 计算机是由两部分组…...
BRAM/URAM资源介绍
BRAM/URAM资源简介 Bram和URAM都是FPGA(现场可编程门阵列)中的RAM资源。 Bram是Block RAM的缩写,是Xilinx FPGA中常见的RAM资源之一,也是最常用的资源之一。它是一种单独的RAM模块,通常用于存储大量的数据࿰…...
分享一个基于python的个性推荐餐厅系统源码 餐厅管理系统代码
💕💕作者:计算机源码社 💕💕个人简介:本人七年开发经验,擅长Java、Python、PHP、.NET、Node.js、微信小程序、爬虫、大数据等,大家有这一块的问题可以一起交流! …...
Mysql5.7开启SSL认证且支持Springboot客户端验证
Mysql5.7开启SSL认证 一、查看服务端mysql环境 1.查看是否开启了ssl,"have_ssl" 为YES的时候,数据库是开启加密连接方式的。 show global variables like %ssl%;2.查看数据库版本 select version();3.查看数据库端口 show variables like port;4.查看数据库存放…...
微信小程序的页面滚动事件监听
微信小程序中可以通过 Page 的 onPageScroll 方法来监听页面滚动事件。具体步骤如下: 在页面的 onLoad 方法中注册页面滚动事件监听器: Page({onLoad: function () {wx.pageScrollTo({scrollTop: 0,duration: 0});wx.showLoading({title: 加载中,});wx…...
数据可视化:四大发明的现代转化引擎
在科技和工业的蓬勃发展中,中国的四大发明——造纸术、印刷术、火药和指南针,早已不再是古代创新的象征,而是催生了众多衍生行业的崭新可能性。其中,数据可视化技术正成为这些行业的一颗璀璨明珠,开启了全新的时代。 1…...
HarmonyOS实现几种常见图片点击效果
一. 样例介绍 HarmonyOS提供了常用的图片、图片帧动画播放器组件,开发者可以根据实际场景和开发需求,实现不同的界面交互效果,包括:点击阴影效果、点击切换状态、点击动画效果、点击切换动效。 相关概念 image组件:图片…...
3D视觉测量:计算两个平面之间的夹角(附源码)
文章目录 1. 基本内容2. 代码实现文章目录:形位公差测量关键内容:通过视觉方法实现平面之间夹角的计算1. 基本内容 要计算两个平面之间的夹角,首先需要知道这两个平面的法向量。假设有两个平面,它们的法向量分别为 N 1 和 N 2 N_1 和 N_2...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
逻辑回归暴力训练预测金融欺诈
简述 「使用逻辑回归暴力预测金融欺诈,并不断增加特征维度持续测试」的做法,体现了一种逐步建模与迭代验证的实验思路,在金融欺诈检测中非常有价值,本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG
TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码:HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...
java高级——高阶函数、如何定义一个函数式接口类似stream流的filter
java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用(Math::max) 2 函数接口…...
