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

力扣72. 编辑距离

动态规划

  • 思路:
    • 假设 dp[i][j] 是 word1 前 i 个字母到 word2 前 j 个字母的编辑距离;
    • 那么状态 dp[i][j] 状态的上一个状态有:
      • dp[i - 1][j],word1 前 i - 1 个字母到 word2 前 j 个字母的编辑距离,此状态再插入一个字母就迁移到 dp[i][j] 状态;
      • 同理在 dp[i][j - 1] 状态 word2 插入一个字母就迁移到 dp[i][j];
      • 状态 dp[i - 1][j - 1],如果 word1 和 word2 最后一个字母相同,则不需要替换;否则,需要进行替换,增加一次编辑;
    • dp[i][j] 是这个上一状态迁移所需距离最小的值;
    • 同时,当一个字母为空串时,需要编辑的距离为另外一个字母的长度:
      • dp[0][j] = j
      • dp[i][0] = i
class Solution {
public:int minDistance(string word1, string word2) {int sz1 = word1.size();int sz2 = word2.size();if (sz1 == 0) {return sz2;}if (sz2 == 0) {return sz1;}std::vector<std::vector<int>> dp(sz1 + 1, std::vector<int>(sz2 + 1));// if word2 emptyfor (int i = 0; i <= sz1; ++i) {dp[i][0] = i;}// if word1 emptyfor (int j = 0; j <= sz2; ++j) {dp[0][j] = j;}for (int i = 1; i <= sz1; ++i) {for (int j = 1; j <= sz2; ++j) {int dp_add = dp[i - 1][j] + 1;int dp_del = dp[i][j - 1] + 1;int dp_re = dp[i - 1][j - 1];if (word1[i - 1] != word2[j - 1]) {dp_re += 1;}dp[i][j] = std::min(std::min(dp_add, dp_del), dp_re);}}return dp[sz1][sz2];}
};

相关文章:

力扣72. 编辑距离

动态规划 思路&#xff1a; 假设 dp[i][j] 是 word1 前 i 个字母到 word2 前 j 个字母的编辑距离&#xff1b;那么状态 dp[i][j] 状态的上一个状态有&#xff1a; dp[i - 1][j]&#xff0c;word1 前 i - 1 个字母到 word2 前 j 个字母的编辑距离&#xff0c;此状态再插入一个字…...

Unity中 URP Shader 的纹理与采样器的分离定义

文章目录 前言一、URP Shader 纹理采样的实现1、在属性面板定义一个2D变量用于接收纹理2、申明纹理3、申明采样器4、进行纹理采样 二、申明纹理 和 申明采样器内部干了什么1、申明纹理2、申明采样器 三、采样器设置采样器的传入格式1、纹理设置中&#xff0c;可以看见我们的采样…...

Electron学习第一天 ,启动项目

之前在安装官网的步骤操作&#xff0c;结果报错&#xff0c;找了好多办法&#xff0c;最后这种办法成功启动项目&#xff0c;并且没有报错&#xff0c;特此记录 特别提醒&#xff0c;最好安装淘宝镜像&#xff0c;npm 太慢&#xff0c;会导致报错问题&#xff0c;解决起来个人觉…...

WebService技术--随笔1

1.WebService 发展史 创建阶段&#xff08;1990 年代末至 2000 年代初&#xff09;&#xff1a;在这个阶段&#xff0c;XML-RPC 和 SOAP 协议被引入&#xff0c;为跨平台和跨语言的应用程序集成提供了基础。XML-RPC 提供了一种基于 XML 的远程过程调用机制&#xff0c;而 SOAP…...

如何使用Docker将.Net6项目部署到Linux服务器(一)

目录 一 配置服务器环境 1.1 配置yum 1.1.1 更新yum包 1.1.2 yum命令 1.2 配置docker …...

第4章-第3节-Java中跟数组相关的几个算法以及综合应用

在写这篇博文之前&#xff0c;先大概说明一下&#xff0c;就是很常见的数组算法如求最大值、一维数组的遍历等&#xff0c;这里就不去专门说明了&#xff0c;只说一些有代表性的&#xff0c;然后就是冒泡排序算法很容易查阅到&#xff0c;这里也不专门说明了&#xff0c;只说明…...

AlexNet(pytorch)

AlexNet是2012年ISLVRC 2012&#xff08;ImageNet Large Scale Visual Recognition Challenge&#xff09;竞赛的冠军网络&#xff0c;分类准确率由传统的 70%提升到 80% 该网络的亮点在于&#xff1a; &#xff08;1&#xff09;首次利用 GPU 进行网络加速训练。 &#xff…...

【单调栈 】LeetCode321:拼接最大数

作者推荐 【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数 本文涉及的知识点 单调栈 题目 给定长度分别为 m 和 n 的两个数组&#xff0c;其元素由 0-9 构成&#xff0c;表示两个自然数各位上的数字。现在从这两个数组中选出 k (k < m n) 个数字…...

TikTok与虚拟现实的完美交融:全新娱乐时代的开启

TikTok&#xff0c;这个风靡全球的短视频平台&#xff0c;与虚拟现实&#xff08;VR&#xff09;技术的深度结合&#xff0c;为用户呈现了一场全新的娱乐盛宴。虚拟现实技术为TikTok带来了更丰富、更沉浸的用户体验&#xff0c;标志着全新娱乐时代的开启。本文将深入探讨TikTok…...

PXI/PCIe/VPX机箱 ARM|x86 + FPGA测试测量板卡解决方案

PXI便携式测控系统是一种基于PXI总线的便携式测试测控系统&#xff0c;它填补了现有台式及机架式仪器在外场测控和便携测控应用上的空白&#xff0c;在军工国防、航空航天、兵器电子、船舶舰载等各个领域的外场测控场合和科学试验研究场合都有广泛的应用。由于PXI便携式测控系统…...

ES6 面试题 | 12.精选 ES6 面试题

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…...

【linux】Debian不能运行sudo的解决

一、问题&#xff1a; sudo: 没有找到有效的 sudoers 资源&#xff0c;退出 sudo: 初始化审计插件 sudoers_audit 出错 二、可用的方法&#xff1a; 出现 "sudo: 没有找到有效的 sudoers 资源&#xff0c;退出" 和 "sudo: 初始化审计插件 sudoers_audit 出错&q…...

讲解ThinkPHP的链式操作

数据库提供的链式操作方法&#xff0c;可以有效的提高数据存取的代码清晰度和开发效率&#xff0c;并且支持所有的CURD操作。 使用也比较简单&#xff0c;假如我们现在要查询一个User表的满足状态为1的前10条记录&#xff0c;并希望按照用户的创建时间排序 Db::table(think_u…...

Java技术栈 —— 微服务框架Spring Cloud —— Ruoyi-Cloud 学习(二)

RuoYi项目开发过程 一、登录功能(鉴权模块)1.1 后端部分1.1.1 什么是JWT?1.1.2 什么是Base64?为什么需要它&#xff1f;1.1.3 SpringBoot注解解析1.1.4 依赖注入和控制反转1.1.5 什么是Restful?1.1.6 Log4j 2、Logpack、SLF4j日志框架1.1.7 如何将项目打包成指定bytecode字节…...

如何进行软件测试和测试驱动开发(TDD)?

1. 软件测试概述 1.1 什么是软件测试&#xff1f; 软件测试是一种评估系统的过程&#xff0c;目的是发现潜在的错误或缺陷。通过对软件进行测试&#xff0c;开发者和测试人员可以确定软件是否符合预期的需求、功能是否正常运行&#xff0c;以及系统是否足够稳定和可靠。 1.2…...

linux 开机启动流程

1.打开电源 2.BIOS 有时间和启动方式 3.启动Systemd 其pid为1 4.挂载引导分区 /boot 5.启动各种服务 如rc.local...

Mybatis 动态SQL的插入操作

需求 : 根据用户的输入情况进行插入 动态SQL:根据需求动态拼接SQL 用户往表中插入数据,有的数据可能不想插入,比如不想让别人知道自己的性别,性别就为空 insert into userinfo(username,password,age,gender,phone) values(?,?,?,?,?); insert into userinfo(username,…...

共建开源新里程:北京航空航天大学OpenHarmony技术俱乐部正式揭牌成立

12月11日,由OpenAtom OpenHarmony(以下简称“OpenHarmony”)项目群技术指导委员会(以下简称“TSC”)和北京航空航天大学共同举办的“OpenHarmony软件工程研讨会暨北京航空航天大学OpenHarmony技术俱乐部成立仪式”在京圆满落幕。 现场大合影 活动当天,多位重量级嘉宾出席了此次…...

企业微信机器人发送文本、图片、文件、markdown、图文信息

import requests import base64 import hashlib import json # 机器人地址的key值 key"811a1652-60e8-4f51-a1d9-231783399ad2" def path2base64(path):"""文件转换为base64:param path: 文件路径:return:"""with open(path, "rb…...

智能优化算法应用:基于天牛须算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于天牛须算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于天牛须算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.天牛须算法4.实验参数设定5.算法结果6.参考文…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

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

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