力扣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. 编辑距离
动态规划 思路: 假设 dp[i][j] 是 word1 前 i 个字母到 word2 前 j 个字母的编辑距离;那么状态 dp[i][j] 状态的上一个状态有: dp[i - 1][j],word1 前 i - 1 个字母到 word2 前 j 个字母的编辑距离,此状态再插入一个字…...
Unity中 URP Shader 的纹理与采样器的分离定义
文章目录 前言一、URP Shader 纹理采样的实现1、在属性面板定义一个2D变量用于接收纹理2、申明纹理3、申明采样器4、进行纹理采样 二、申明纹理 和 申明采样器内部干了什么1、申明纹理2、申明采样器 三、采样器设置采样器的传入格式1、纹理设置中,可以看见我们的采样…...
Electron学习第一天 ,启动项目
之前在安装官网的步骤操作,结果报错,找了好多办法,最后这种办法成功启动项目,并且没有报错,特此记录 特别提醒,最好安装淘宝镜像,npm 太慢,会导致报错问题,解决起来个人觉…...
WebService技术--随笔1
1.WebService 发展史 创建阶段(1990 年代末至 2000 年代初):在这个阶段,XML-RPC 和 SOAP 协议被引入,为跨平台和跨语言的应用程序集成提供了基础。XML-RPC 提供了一种基于 XML 的远程过程调用机制,而 SOAP…...
如何使用Docker将.Net6项目部署到Linux服务器(一)
目录 一 配置服务器环境 1.1 配置yum 1.1.1 更新yum包 1.1.2 yum命令 1.2 配置docker …...
第4章-第3节-Java中跟数组相关的几个算法以及综合应用
在写这篇博文之前,先大概说明一下,就是很常见的数组算法如求最大值、一维数组的遍历等,这里就不去专门说明了,只说一些有代表性的,然后就是冒泡排序算法很容易查阅到,这里也不专门说明了,只说明…...
AlexNet(pytorch)
AlexNet是2012年ISLVRC 2012(ImageNet Large Scale Visual Recognition Challenge)竞赛的冠军网络,分类准确率由传统的 70%提升到 80% 该网络的亮点在于: (1)首次利用 GPU 进行网络加速训练。 ÿ…...
【单调栈 】LeetCode321:拼接最大数
作者推荐 【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数 本文涉及的知识点 单调栈 题目 给定长度分别为 m 和 n 的两个数组,其元素由 0-9 构成,表示两个自然数各位上的数字。现在从这两个数组中选出 k (k < m n) 个数字…...
TikTok与虚拟现实的完美交融:全新娱乐时代的开启
TikTok,这个风靡全球的短视频平台,与虚拟现实(VR)技术的深度结合,为用户呈现了一场全新的娱乐盛宴。虚拟现实技术为TikTok带来了更丰富、更沉浸的用户体验,标志着全新娱乐时代的开启。本文将深入探讨TikTok…...
PXI/PCIe/VPX机箱 ARM|x86 + FPGA测试测量板卡解决方案
PXI便携式测控系统是一种基于PXI总线的便携式测试测控系统,它填补了现有台式及机架式仪器在外场测控和便携测控应用上的空白,在军工国防、航空航天、兵器电子、船舶舰载等各个领域的外场测控场合和科学试验研究场合都有广泛的应用。由于PXI便携式测控系统…...
ES6 面试题 | 12.精选 ES6 面试题
🤍 前端开发工程师(主业)、技术博主(副业)、已过CET6 🍨 阿珊和她的猫_CSDN个人主页 🕠 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 🍚 蓝桥云课签约作者、已在蓝桥云…...
【linux】Debian不能运行sudo的解决
一、问题: sudo: 没有找到有效的 sudoers 资源,退出 sudo: 初始化审计插件 sudoers_audit 出错 二、可用的方法: 出现 "sudo: 没有找到有效的 sudoers 资源,退出" 和 "sudo: 初始化审计插件 sudoers_audit 出错&q…...
讲解ThinkPHP的链式操作
数据库提供的链式操作方法,可以有效的提高数据存取的代码清晰度和开发效率,并且支持所有的CURD操作。 使用也比较简单,假如我们现在要查询一个User表的满足状态为1的前10条记录,并希望按照用户的创建时间排序 Db::table(think_u…...
Java技术栈 —— 微服务框架Spring Cloud —— Ruoyi-Cloud 学习(二)
RuoYi项目开发过程 一、登录功能(鉴权模块)1.1 后端部分1.1.1 什么是JWT?1.1.2 什么是Base64?为什么需要它?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 什么是软件测试? 软件测试是一种评估系统的过程,目的是发现潜在的错误或缺陷。通过对软件进行测试,开发者和测试人员可以确定软件是否符合预期的需求、功能是否正常运行,以及系统是否足够稳定和可靠。 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)覆盖优化 - 附代码
智能优化算法应用:基于天牛须算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用:基于天牛须算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.天牛须算法4.实验参数设定5.算法结果6.参考文…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
