力扣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.参考文…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
