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

代码随想录算法训练营Day56 || ● 583. 两个字符串的删除操作 ● 72. 编辑距离

今天接触到了真正的距离,但可以通过增删改操作来逼近。

问题1:583. 两个字符串的删除操作 - 力扣(LeetCode)

给定两个单词 word1 和 word2 ,返回使得 word1 和  word2 相同所需的最小步数

每步 可以删除任意一个字符串中的一个字符。

思路:该题关键在于理解删除,删除操作即多走一步,由之前的状态进行推导。首先dp[i][j]还是表示从s[i]到t[j]需要的步数,初始化时是从0到s[i]所需删除元素,故为i。通过观察易发现dp可由dp[i-1]j-1],dp[i-1][j],p[i][j-1]得出,代码如下:

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));for(int i = 0;i <= word1.size();i++) dp[i][0] = i;for(int j = 0;j <= word2.size();j++) dp[0][j] = j;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][j-1]+1,dp[i-1][j]+1);}}return dp[word1.size()][word2.size()]; }};

问题2:72. 编辑距离 - 力扣(LeetCode)

给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

思路:该题一上来我就去寻找规律,并没有尝试去真正理解增删改操作怎么去替代,并且在绘制例子矩阵时也较为粗心,导致最后找出来的规律是错误的。其实这类题目并没有什么套路,想想怎样将题目允许的变化做相应操作即可,具体代码如下:

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));for(int i = 0;i < word1.size();i++) dp[i][0] = i;for(int j = 0;j <= word2.size();j++) dp[0][j] = j;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][j-1],dp[i-1][j],dp[i-1][j-1]}) + 1;}}return dp[word1.size()][word2.size()];}
};

相关文章:

代码随想录算法训练营Day56 || ● 583. 两个字符串的删除操作 ● 72. 编辑距离

今天接触到了真正的距离&#xff0c;但可以通过增删改操作来逼近。 问题1&#xff1a;583. 两个字符串的删除操作 - 力扣&#xff08;LeetCode&#xff09; 给定两个单词 word1 和 word2 &#xff0c;返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字…...

chrome_elf.dll丢失怎么办?修复chrome_elf.dll文件的方法

Chrome是目前最受欢迎的网络浏览器之一&#xff0c;然而有时用户可能会遇到Chrome_elf.dll丢失的问题。该DLL文件是Chrome浏览器的一个重要组成部分&#xff0c;负责启动和管理程序的各种功能。当Chrome_elf.dll丢失时&#xff0c;用户可能无法正常启动Chrome或执行某些功能。本…...

代码随想录32|738.单调递增的数字,968.监控二叉树,56. 合并区间

738.单调递增的数字 链接地址 class Solution { public:int monotoneIncreasingDigits(int n) {string str to_string(n);int flag str.size();for (int i str.size() - 1; i > 0; i--) {if (str[i] < str[i - 1]) {str[i - 1] - 1;flag i;}}for (int j flag; j <…...

BIO NIO AIO演变

Netty是一个提供异步事件驱动的网络应用框架&#xff0c;用以快速开发高性能、高可靠的网络服务器和客户端程序。Netty简化了网络程序的开发&#xff0c;是很多框架和公司都在使用的技术。 Netty并非横空出世&#xff0c;它是在BIO&#xff0c;NIO&#xff0c;AIO演变中的产物…...

JVM GC垃圾回收

一、GC垃圾回收算法 标记-清除算法 算法分为“标记”和“清除”阶段&#xff1a;标记存活的对象&#xff0c; 统一回收所有未被标记的对象(一般选择这种)&#xff1b;也可以反过来&#xff0c;标记出所有需要回收的对象&#xff0c;在标记完成后统一回收所有被标记的对象 。它…...

【数据结构】队列知识点总结--定义;基本操作;队列的顺序实现;链式存储;双端队列;循环队列

欢迎各位看官^_^ 目录 1.队列的定义 2.队列的基本操作 2.1初始化队列 2.2判断队列是否为空 2.3判断队列是否已满 2.4入队 2.5出队 2.6完整代码 3.队列的顺序实现 4.队列的链式存储 5.双端队列 6.循环队列 1.队列的定义 队列&#xff08;Queue&#xff09;是一种先…...

嵌入式学习之链表

对于链表&#xff0c;要重点掌握链表和数组区别和实现&#xff0c;链表静态添加和动态遍历&#xff0c;链表中pointpoint-next,链表节点个数的查找&#xff0c;以及链表从指定节点后方插入新节点的知识。...

静态代理和动态代理笔记

总体分为: 1.静态代理: 代理类和被代理类需要实现同一个接口.在代理类中初始化被代理类对象.在代理类的方法中调 用被代理类的方法.可以选择性的在该方法执行前后增加功能或者控制访问 2.动态代理: 在程序执行过程中,实用JDK的反射机制,创建代理对象,并动态的指定要…...

[SM6225][Android13]user版本默认允许root和remount

开发平台基本信息 芯片: 高通SM6225版本: Android 13kernel: msm-5.15 问题描述 刚刚从Framework踏入性能的小殿堂&#xff0c;User版本默认是不会开启root权限的&#xff0c;而且一般调试需要设置一下CPU GPU DDR performance模式或者修改一些schedule util等调核调频节点去…...

pyinstaller打包exe,使用wexpect的问题

参考github首先打包wexpect 1.进入wexpect目录执行 pyinstaller __main__.py -n wexpect 会生成dist文件夹 2.python代码A.py中使用wexpect&#xff0c;注意wexpect.spawn前后必须按照下面添加代码 import sys,os,wexpect #spawn前 real_executable sys.executable try:if sy…...

OpenCV(三十三):计算轮廓面积与轮廓长度

1.介绍轮廓面积与轮廓长度 轮廓面积&#xff08;Contour Area&#xff09;是指轮廓所包围的区域的总面积。通常情况下&#xff0c;轮廓面积的单位是像素的平方。 轮廓长度&#xff08;Contour Length&#xff09;又称周长&#xff08;Perimeter&#xff09;&#xff0c;表示轮廓…...

9.11作业

实现一个对数组求和的函数&#xff0c;数组通过实参传递给函数 sum0 arr(11 22 33 44 55) Sum() {for i in ${arr[*]}do$((sumi))donereturn $sum } Sum ${arr[*]} var$? echo $var写一个函数&#xff0c;输出当前用户的uid和gid&#xff0c;并使用变量接收结果 Sum() {aid -…...

AI伦理与未来社会:探讨人工智能的道德挑战与机会

引言 引出AI伦理和社会影响的主题&#xff0c;强调AI的快速发展和广泛应用。 概述博客的主要内容&#xff1a;探讨AI的伦理挑战以及它对社会的影响。 第一部分&#xff1a;AI的伦理挑战 算法偏见&#xff1a; 解释什么是算法偏见&#xff0c;以及它为何在AI中成为一个重要问题。…...

Android窗口层级(Window Type)分析

前言 Android的窗口Window分为三种类型&#xff1a; 应用Window&#xff0c;比如Activity、Dialog&#xff1b;子Window&#xff0c;比如PopupWindow&#xff1b;系统Window&#xff0c;比如Toast、系统状态栏、导航栏等等。 应用Window的Z-Ordered最低&#xff0c;就是在系…...

微信小程序基础加强总结

本篇文章给大家带来了关于微信小程序的相关问题&#xff0c;其中主要介绍了一些基础内容&#xff0c;包括了自定义组件、样式隔离、数据、方法和属性等等内容&#xff0c;下面一起来看一下&#xff0c;希望对大家有帮助。 1、自定义组件 1.1、创建组件 在项目的根目录中&…...

【JAVA - List】差集removeAll() 四种方法实现与优化

一、场景&#xff1a; 二、结论&#xff1a; 1. 四种方法耗时 三、代码&#xff1a; 一、场景&#xff1a; 求差集 List1 - Lsit2 二、结论&#xff1a; 1. 四种方法耗时 初始条件方法名方法思路耗时 List1.size319418 List2.size284900 List..removeAll(Lsit2)1036987ms…...

sql注入基本概念

死在山野的风里&#xff0c;活在自由的梦里 sql注入基本概念 MYSQL基本语法union合并查询2个特性&#xff1a;order by 排序三个重要的信息 Sql Server MYSQL 基本语法 登录 mysql -h ip -u user -p pass基本操作 show databases; 查看数据库crea…...

AIGC系列:1.chatgpt可以用来做哪些事情?

上图的意思&#xff1a;神器轩辕剑 那么&#xff0c;在现在AI盛行的信息时代&#xff0c; 你是否知道如何获得和利用ChatGPT这一把轩辕剑来提升你的攻击力和生存能力呢&#xff1f; 故事 程序员小张&#xff1a; 刚毕业&#xff0c;参加工作1年左右&#xff0c;日常工作是C…...

End-to-End Object Detection with Transformers(论文解析)

End-to-End Object Detection with Transformers 摘要介绍相关工作2.1 集合预测2.2 transformer和并行解码2.3 目标检测 3 DETR模型3.1 目标检测集设置预测损失3.2 DETR架构 摘要 我们提出了一种将目标检测视为直接集合预测问题的新方法。我们的方法简化了检测流程&#xff0c…...

生成多样、真实的评论(2019 IEEE International Conference on Big Data )

论文题目&#xff08;Title&#xff09;&#xff1a;Learning to Generate Diverse and Authentic Reviews via an Encoder-Decoder Model with Transformer and GRU 研究问题&#xff08;Question&#xff09;&#xff1a;评论生成&#xff0c;由上下文评论->生成评论 研…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

Maven 概述、安装、配置、仓库、私服详解

目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...