当前位置: 首页 > 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.参考文…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

PHP和Node.js哪个更爽?

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

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...