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

LeetCode583:两个字符串的删除操作

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

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

在这里插入图片描述

代码
解法1

/*dp[i][j]:以i-1为结尾的wrod1中有以j-1为尾的word2的个数为了让word1和word2相同,最少操作次数为dp[i][j]递推公式:当word1[i - 1] 与 word2[j - 1]相同的时候,dp[i][j] = dp[i - 1][j - 1];   当word1[i - 1] 与 word2[j - 1]不相同的时候,有三种情况:情况一:删word1[i - 1],最少操作次数为dp[i - 1][j] + 1情况二:删word2[j - 1],最少操作次数为dp[i][j - 1] + 1情况三:同时删word1[i - 1]和word2[j - 1],操作的最少次数为dp[i - 1][j - 1] + 2因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2,所以递推公式可简化为:dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);初始化:dp[i][0] = i, 表示word1不为空,word2为空,需要删除i个元素dp[0][j] = j, 表示word1为空,word2不为空,需要删除j个元素递推公式for(int i=1;i<=word1.size();i++)for(int j=1;j<=word2.size();j++)*/
class Solution {
public:int minDistance(string word1, string word2) {int m = word1.size();int n = word2.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for (int i = 0; i <= m; i++) dp[i][0] = i;for (int j = 1; j <= n; j++) dp[0][j] = j;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; 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[m][n];}
};

解法2:利用最长公共子序列

/*使用最长公共子序列:求出最长公共子序列,然后使用两个字符串分别减去公共就可计算出每个字符串删除的元素return (word1.size()-dp[m][n]) + (word2.size()-dp[m][n])
*/class Solution {
public:int minDistance(string word1, string word2) {int m = word1.size();int n = word2.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; 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 (m - dp[m][n]) + (n - dp[m][n]);}
};

相关文章:

LeetCode583:两个字符串的删除操作

题目描述 给定两个单词 word1 和 word2 &#xff0c;返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 代码 解法1 /*dp[i][j]&#xff1a;以i-1为结尾的wrod1中有以j-1为尾的word2的个数为了让word1和word2相同&#xff0c;最少操作…...

LLama学习记录

学习前&#xff1a; 五大问题&#xff1a; 为什么SwiGLU激活函数能够提升模型性能&#xff1f;RoPE位置编码是什么&#xff1f;怎么用的&#xff1f;还有哪些位置编码方式&#xff1f;GQA&#xff08;Grouped-Query Attention, GQA&#xff09;分组查询注意力机制是什么&…...

如何克隆非默认分支

直接git clone下来的我们知道是默认分支&#xff0c;那如何克隆其他分支呢&#xff1a; 比如这个&#xff0c;我们想克隆AdvNet。 我们可以在本地文件夹打开Git Bash 依次输入&#xff1a; git clone --branch AdvNet https://github.com/wgcban/SemiCD.git cd SemiCD git b…...

数据结构——图

一 图论基本概念 Directed Acyclic Graph &#xff08;DAG&#xff09; 二 图的存储 ①邻接矩阵(适用于稠密图) ②邻接表(适用于稀疏图) 三、图的遍历 ①深度优先搜索 //(基于邻接表实现&#xff0c;以有向图为例) //DFS:Depth First Search 深度优先搜索 //1、访问起始顶点 …...

蓝桥杯—SysTick中断精准定时实现闪烁灯

在嵌入式系统中&#xff0c;SysTick_Handler 是一个中断服务例程&#xff08;Interrupt Service Routine, ISR&#xff09;&#xff0c;用于处理 SysTick 定时器的中断。SysTick 定时器通常用于提供一个周期性的定时中断&#xff0c;可以用来实现延时或者周期性任务。 SysTick…...

ML307R OpenCPU UDP使用

一、UDP通信流程 二、示例 三、UDP通信代码 一、UDP通信流程 ML307R UDP 是使用LWIP的标准的通信,具体UDP流程可以自行百度 二、示例 实验目的:实现把接收的数据再发送到服务端 测试网址:UDP电脑端测试网址 因为是4G,所以必须用外网的 /* 测试前请先补充如下参数 */…...

pod详解

目录 pod pod基本介绍 k8s集群中pod两种使用方式 pause容器使得Pod中所有容器共享两种资源&#xff1a;网络和存储 kubernetes中的pause容器主要为每个容器提供以下功能 k8s设计这样的pod概念和特殊组成结构有什么用意 pod分类 pod容器的分类 基础容器&#xff08;infr…...

免费插件集-illustrator插件-Ai插件-文本对象分行

文章目录 1.介绍2.安装3.通过窗口>扩展>知了插件4.功能解释5.总结 1.介绍 本文介绍一款免费插件&#xff0c;加强illustrator使用人员工作效率&#xff0c;进行文本对象分行。首先从下载网址下载这款插件 https://download.csdn.net/download/m0_67316550/87890501&…...

web学习笔记(五十九)

目录 1.style样式 1.1作用域 scoped 1.2 less和 sass 1.3 less和 sass两者的区别 2. 计算属性computed 3. 响应式基础reactive() 4. 什么是MVVM? 1.style样式 1.1作用域 scoped scoped表示样式作用域&#xff0c;把内部的样式仅限于当前组件模板生效&#xff0c;其…...

UE5 UE4 快速定位节点位置

在材质面板中&#xff0c;找到之前写的一个节点&#xff0c;想要修改&#xff0c;但是当时写的比较多&#xff0c;想要快速定位到节点位置. 在面板下方的 Find Results面板中&#xff0c;输入所需节点&#xff0c;找结果后双击&#xff0c;就定位到该节点处。 同理&#xff0c;…...

go routing 之 gorilla/mux

1. 背景 继续学习 go 2. 关于 routing 的学习 上一篇 go 用的库是&#xff1a;net/http &#xff0c;这次我们使用官方的库 github.com/gorilla/mux 来实现 routing。 3. demo示例 package mainimport ("fmt""net/http""github.com/gorilla/mux&…...

新火种AI|警钟长鸣!教唆自杀,威胁人类,破坏生态,AI的“反攻”值得深思...

作者&#xff1a;小岩 编辑&#xff1a;彩云 在昨天的文章中&#xff0c;我们提到了谷歌的AI Overview竟然教唆情绪低迷的网友“从金门大桥跳下去”。很多人觉得&#xff0c;这只是AI 模型的一次错误判断&#xff0c;不会有人真的会因此而照做。但现实就是比小说电影中的桥段…...

AAA实验配置

一、实验目的 掌握AAA本地认证的配置方法 掌握AAA本地授权的配置方法 掌握AAA维护的方法 1.搭建实验拓扑图 2.完成基础配置&#xff1a; 3.使用ping命令测试两台设备的连通性&#xff1a; 二、配置AAA 1.打开R1&#xff1a;配置AAA方案 这两个方框内的可以改名&#xff0c…...

Maven高级详解

文章目录 一、分模块开发与设计分模块开发的意义模块拆分原则 分模块开发(模块拆分)创建Maven模块书写模块代码通过maven指令安装模块到本地仓库(install指令) 二、依赖管理依赖传递可选依赖排除依赖可选依赖和排除依赖的区别 三、聚合与继承聚合工程聚合工程开发创建Maven模块…...

C++的算法:模拟算法

模拟算法是一种基于事物运动变化过程的模型,通过计算机程序来模拟实际系统行为或过程的方法。在C++中,模拟算法常用于解决复杂系统或过程的建模与仿真问题。本文将介绍模拟算法的实现思路及实际应用,并通过具体的实例来展示如何在C++中实现模拟算法。 一、模拟算法的实现思…...

Spring boot集成easy excel

Spring boot集成easy excel 一 查看官网 easyexcel官方网站地址为easyexcel官网&#xff0c;官网的信息比较齐全&#xff0c;可以查看官网使用easyexcel的功能。 二 引入依赖 使用easyexcel&#xff0c;首先要引入easyexcel的maven依赖&#xff0c;具体的版本根据你的需求去…...

【开发 | 环境配置】解决 VSCode 编写 eBPF 程序找不到头文件

问题描述&#xff1a; 在使用 vscode 编写 eBPF 程序时&#xff0c;如果不做一些头文件定位的操作&#xff0c;默认情况下头文件总是带有“红色下划线”&#xff0c;并且大部分的变量不会有提示与补全。 在编写代码文件较小时&#xff08;或者功能需求小时&#xff09;并不会…...

View->Bitmap缩放到自定义ViewGroup的任意区域

Bitmap缩放和平移 加载一张Bitmap可能为宽高相同的正方形&#xff0c;也可能为宽高不同的矩形缩放方向可以为中心缩放&#xff0c;左上角缩放&#xff0c;右上角缩放&#xff0c;左下角缩放&#xff0c;右下角缩放Bitmap中心缩放&#xff0c;包含了缩放和平移两个操作&#xf…...

十种常用数据分析方法

描述性统计分析&#xff08;Descriptive Statistics&#xff09; 使用场景&#xff1a;用来总结数据的基本特征&#xff0c;如平均值、中位数、标准差等。 优势&#xff1a;简单易懂&#xff0c;快速总结数据。 劣势&#xff1a;无法深入挖掘数据的潜在关系。 模拟数据及示例…...

拉格朗日插值及牛顿差商方法的实现(Matlab)

一、问题描述 拉格朗日插值及牛顿差商方法的实现。 二、实验目的 掌握拉格朗日插值和牛顿差商方法的原理&#xff0c;能够编写代码实现两种方法&#xff1b;能够分析多项式插值中的误差。 三、实验内容及要求 利用拉格朗日插值及牛顿差商方法估计1980 年的人口&#xff0c;并…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...