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

代码随想录训练营第五十六天| 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. 两个字符串的删除操作 题目链接/文章讲解/视频讲解&#xff1a;代码随想录 1.代码展示 //583.两个字符串的删除操作 int minDistance(string word1, string word2) {//step1 构建dp数组&#xff0c;dp[i][j]的含义是要使以i-1为结尾的word1和以j-1为结尾的word2//删除其元…...

hive解决了什么问题

hive出现的原因 Hive 出现的原因主要有以下几个&#xff1a; 传统数据仓库无法处理大规模数据&#xff1a;传统的数据仓库通常采用关系型数据库作为底层存储&#xff0c;这种数据库在处理大规模数据时效率较低。MapReduce 难以使用&#xff1a;MapReduce 是一种分布式计算框架…...

Lumion 和 Enscape 应该选择怎样的笔记本电脑?

Lumion 和 Enscape实时渲染对配置要求高&#xff0c;本地配置不够&#xff0c;如何快速解决&#xff1a; 本地普通电脑可一键申请高性能工作站&#xff0c;资产安全保障&#xff0c;供软件中心&#xff0c;各种软件插件一键获取&#xff0c;且即开即用&#xff0c;使用灵活&am…...

ICCV 2023 | MoCoDAD:一种基于人体骨架的运动条件扩散模型,实现高效视频异常检测

论文链接&#xff1a; https://arxiv.org/abs/2307.07205 视频异常检测&#xff08;Video Anomaly Detection&#xff0c;VAD&#xff09;扩展自经典的异常检测任务&#xff0c;由于异常情况样本非常少见&#xff0c;因此经典的异常检测通常被定义为一类分类问题&#xff08;On…...

Mac电脑怎么使用NTFS磁盘管理器 NTFS磁盘详细使用教程

Mac是可以识别NTFS硬盘的&#xff0c;但是macOS系统虽然能够正确识别NTFS硬盘&#xff0c;但只支持读取&#xff0c;不支持写入。换句话说&#xff0c;Mac不支持对NTFS硬盘进行编辑、创建、删除等写入操作&#xff0c;比如将Mac里的文件拖入NTFS硬盘&#xff0c;在NTFS硬盘里新…...

Java设计模式-结构性设计模式(代理设计模式)

简介 为其他对象提供⼀种代理以控制对这个对象的访问&#xff0c;属于结构型模式。客户端并不直接调⽤实际的对象&#xff0c;⽽是通过调⽤代理&#xff0c;来间接的调⽤实际的对象应用场景 各⼤数码专营店&#xff0c;代理⼚商进⾏销售对应的产品&#xff0c;代理商持有真正的…...

线性空间、子空间、基、基坐标、过渡矩阵

线性空间的定义 满足加法和数乘封闭。也就是该空间的所有向量都满足乘一个常数后或者和其它向量相加后仍然在这个空间里。进一步可以理解为该空间中的所有向量满足加法和数乘的组合封闭。即若 V 是一个线性空间&#xff0c;则首先需满足&#xff1a; 注&#xff1a;线性空间里面…...

【MySQL】CRUD (增删改查) 基础

CRUD&#xff08;增删改查&#xff09;基础 一. CRUD二. 新增 &#xff08;Create&#xff09;1. 单行数据 全列插入2. 多行数据 指定列插入 三. 查询&#xff08;Retrieve&#xff09;1. 全列查询2. 指定列查询3. 查询字段为表达式4. 别名5. 去重&#xff1a;DISTINCT6. 排序…...

Socks5代理IP:保障跨境电商的网络安全

在数字化时代&#xff0c;跨境电商已成为全球商业的重要一环。然而&#xff0c;随着其发展壮大&#xff0c;网络安全问题也逐渐浮出水面。为了确保跨境电商的安全和隐私&#xff0c;Socks5代理IP技术成为了一项不可或缺的工具。本文将深入探讨Socks5代理IP在跨境电商中的应用&a…...

macOS通过钥匙串访问找回WiFi密码

如果您忘记了Mac电脑上的WiFi密码&#xff0c;可以通过钥匙串访问来找回它。具体步骤如下&#xff1a; 1.打开Mac电脑的“启动台”&#xff0c;然后在其他文件中找到“钥匙串访问”。 2.运行“钥匙串访问”应用程序&#xff0c;点击左侧的“系统”&#xff0c;然后在右侧找到…...

Debian11之稳定版本Jenkins安装

官方网址 系统要求 机器要求 256 MB 内存&#xff0c;建议大于 512 MB 10 GB 的硬盘空间&#xff08;用于 Jenkins 和 Docker 镜像&#xff09;软件要求 Java 8 ( JRE 或者 JDK 都可以) Docker &#xff08;导航到网站顶部的Get Docker链接以访问适合您平台的Docker下载安装…...

kakfa 3.5 kafka服务端处理消费者客户端拉取数据请求源码

一、服务端接收消费者拉取数据的方法二、遍历请求中需要拉取数据的主题分区集合&#xff0c;分别执行查询数据操作&#xff0c;1、会选择合适的副本读取本地日志数据(2.4版本后支持主题分区多副本下的读写分离) 三、会判断当前请求是主题分区Follower发送的拉取数据请求还是消费…...

【Linux】进程概念I --操作系统概念与冯诺依曼体系结构

Halo&#xff0c;这里是Ppeua。平时主要更新C语言&#xff0c;C&#xff0c;数据结构算法…感兴趣就关注我吧&#xff01;你定不会失望。 本篇导航 1. 冯诺依曼体系结构为什么这样设计? 2. 操作系统概念为什么我们需要操作系统呢?操作系统怎么进行管理? 计算机是由两部分组…...

BRAM/URAM资源介绍

BRAM/URAM资源简介 Bram和URAM都是FPGA&#xff08;现场可编程门阵列&#xff09;中的RAM资源。 Bram是Block RAM的缩写&#xff0c;是Xilinx FPGA中常见的RAM资源之一&#xff0c;也是最常用的资源之一。它是一种单独的RAM模块&#xff0c;通常用于存储大量的数据&#xff0…...

分享一个基于python的个性推荐餐厅系统源码 餐厅管理系统代码

&#x1f495;&#x1f495;作者&#xff1a;计算机源码社 &#x1f495;&#x1f495;个人简介&#xff1a;本人七年开发经验&#xff0c;擅长Java、Python、PHP、.NET、Node.js、微信小程序、爬虫、大数据等&#xff0c;大家有这一块的问题可以一起交流&#xff01; &#x1…...

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 方法来监听页面滚动事件。具体步骤如下&#xff1a; 在页面的 onLoad 方法中注册页面滚动事件监听器&#xff1a; Page({onLoad: function () {wx.pageScrollTo({scrollTop: 0,duration: 0});wx.showLoading({title: 加载中,});wx…...

数据可视化:四大发明的现代转化引擎

在科技和工业的蓬勃发展中&#xff0c;中国的四大发明——造纸术、印刷术、火药和指南针&#xff0c;早已不再是古代创新的象征&#xff0c;而是催生了众多衍生行业的崭新可能性。其中&#xff0c;数据可视化技术正成为这些行业的一颗璀璨明珠&#xff0c;开启了全新的时代。 1…...

HarmonyOS实现几种常见图片点击效果

一. 样例介绍 HarmonyOS提供了常用的图片、图片帧动画播放器组件&#xff0c;开发者可以根据实际场景和开发需求&#xff0c;实现不同的界面交互效果&#xff0c;包括&#xff1a;点击阴影效果、点击切换状态、点击动画效果、点击切换动效。 相关概念 image组件&#xff1a;图片…...

3D视觉测量:计算两个平面之间的夹角(附源码)

文章目录 1. 基本内容2. 代码实现文章目录:形位公差测量关键内容:通过视觉方法实现平面之间夹角的计算1. 基本内容 要计算两个平面之间的夹角,首先需要知道这两个平面的法向量。假设有两个平面,它们的法向量分别为 N 1 和 N 2 N_1 和 N_2...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...