编辑距离 -- 动规
72. 编辑距离
给出动规的两种常见实现形式:自顶向下、自底向上,前者一般借助递归函数+备忘录实现,后者通常基于dp数组实现。
class MinDistance:"""72. 编辑距离https://leetcode.cn/problems/edit-distance/"""def solution(self, s1: str, s2: str) -> int:"""递归解法 + 备忘录自顶向下:param s1::param s2::return:"""# memo[i][j] 表示 s1[0..i] 和 s2[0..j] 的最⼩编辑距离m, n = len(s1), len(s2)self.memo = [[-1 for _ in range(n)] for _ in range(m)]return self.dp(s1, m-1, s2, n-1)def dp(self, s1, i, s2, j):"""自顶向下:param s1::param i::param s2::param j::return: s1[0..i] 和 s2[0..j] 的最⼩编辑距离"""# base caseif i == -1:return j+1if j == -1:return i+1if self.memo[i][j] != -1:return self.memo[i][j]if s1[i] == s2[j]:self.memo[i][j] = self.dp(s1, i-1, s2, j-1)else:self.memo[i][j] = min(self.dp(s1, i-1, s2, j) + 1, # 删除self.dp(s1, i, s2, j-1) + 1, # 插入self.dp(s1, i-1, s2, j-1) + 1, # 替换)return self.memo[i][j]def solution2(self, s1: str, s2: str) -> int:"""dp table自底向上 求解:param s1::param s2::return:"""# dp[i+1][j+1] 表示 s1[0..i] 和 s2[0..j] 的最⼩编辑距离m, n = len(s1), len(s2)dp = [[-1 for _ in range(n+1)] for _ in range(m+1)]# base casefor i in range(m+1):dp[i][0] = ifor j in range(n+1):dp[0][j] = jfor i in range(1, m+1):for j in range(1, n+1):if s1[i-1] == s2[j-1]:dp[i][j] = dp[i-1][j-1]else:dp[i][j] = min(dp[i - 1][j - 1] + 1,dp[i][j - 1] + 1,dp[i - 1][j] + 1)return dp[m][n]
相关文章:
编辑距离 -- 动规
72. 编辑距离 给出动规的两种常见实现形式:自顶向下、自底向上,前者一般借助递归函数备忘录实现,后者通常基于dp数组实现。 class MinDistance:"""72. 编辑距离https://leetcode.cn/problems/edit-distance/""&quo…...
douyin【商品抢购js脚本】
文章目录 前言订阅须知知识点源码前言 脚本主要用来实现抢购douyin商城、直播间秒杀商品等一系列商品 订阅须知 订阅后,只提供js源代码,不提供教学,请根据源码自行抓包知识点 1、在查询串插入一个固定的键rstr 2、对查询串进行按键排序并取值,对空格和+进行转义为a …...
常见Web安全技术总结!474页Web安全从入门到精通(附PDF)
Web安全范围比较大,知识点比较杂,很多朋友都无从下手,这不可怕,可怕的是乱下手,其实往往基础才是决定你是否能走远的关键。 为了帮助大家入门网安,给大家推荐一份《新手Web安全入门到精通》,共…...
Prometheus 监控指南:如何可靠地记录数字时间序列数据
🌷🍁 博主猫头虎(🐅🐾)带您 Go to New World✨🍁 🐅🐾猫头虎建议程序员必备技术栈一览表📖: 🛠️ 全栈技术 Full Stack: 📚…...
rsync远程同步+inotify监控
目录 一、Rsync 简介 1、rsync是什么 2、备份的方式 3、rsync同步方式 4、常用rsync命令 5、配置源的两种表达方法 二、rsync实验 1、本地复制 编辑编辑 2、异地复制 2.1 rsync服务器配置 2.2 rsync客户端配置 2.2.1 普通同步 2.2.2 免密同步 2.2.3 --delet…...
【面试经典150 | 数组】移除元素
文章目录 写在前面Tag题目来源题目解读解题思路方法一:原地操作 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等…...
玩转Mysql系列 - 第21篇:什么是索引?
这是Mysql系列第21篇。 本文开始连续3篇详解mysql索引: 第1篇来说说什么是索引? 第2篇详解Mysql中索引的原理 第3篇结合索引详解关键字explain 本文为索引第一篇:我们来了解一下什么是索引? 路人在搞计算机之前,…...
预处理指令
// The include directive instructs the preprocessor to paste the text of the given file into the current file. // 粘贴指定文件的内容 #include // 定义宏PI #define PI 3.1415926 // 取消定义PI #undef PI条件编译(Conditional Compilation) // 检查xxx是否已被定义为…...
强大的JTAG边界扫描(1):基本原理介绍
文章目录 1. 什么是边界扫描?2. JTAG硬件接口3. 边界扫描相关的软硬件4. 学习资料5. 总结 我是怎么了解到边界扫描的呢? 这就要从我淘到一块FPGA板卡的事情说起了。 前段时间我在某二手平台上淘了一块FPGA板子,它长这样: 板子的…...
【C++】源文件.cpp和头文件.h分离编程
优势介绍 将C代码分为头文件(.h)和源文件(.cpp)的做法有以下几个好处: 模块化和代码组织:将函数和类的声明(包括函数原型、类的成员和属性等)放在头文件中,将函数和类的…...
报错ssh: Could not resolve hostname
…按照网上好多教程试了一下: 新建密钥,添加到gitee,重新测试。修改host,加入gitee的ip地址到里面去。修改.gifconfig配置文件,配置成ssh的仓库链接。 这上面的方法都不行,后面发现一篇文章:SS…...
从零开始学网站建设:从需求分析到上线发布
从零开始学网站建设:从需求分析到上线发布 一、需求分析 在进行网站建设之前,首先需要与客户进行沟通,了解客户的需求和要求,并进行深入的分析和研究。根据不同的需求,需要确定网站的类型、功能、布局、风格等方面的…...
软件系统验收测试需要注意的地方
验收测试 一、软件验收测试含义: 软件验收测试是指测试人员检验软件是否符合软件规格说明书和用户需求的测试活动。 验收测试是软件测试的最后一个环节,也是最为关键的一个要素。 它关系到软件开发公司的产品质量,也关系到需求方的产品能…...
解决three.js中加载纹理贴图时,初次渲染不显示的问题
效果: 解决方法:主要是将一些构建网格对象的操作放在了textureLoader.load()方法中,加载图片也用了require init() {// 1, 创建场景对象this.scene new this.$three.Scene();// 2, 创建立方缓冲几何体this.geometry new this.$three.BoxGe…...
Git学习记录
Contest 一、工作区域二、操作命令2.1 创建仓库2.2 查看仓库状态2.3 从工作区向暂存区添加文件2.3.1 只添加一个文件2.3.2 添加全部文件 2.4 从暂存区向仓库区添加文件2.5 查询日志2.5.1 从当前版本开始查询2.5.2 查看所有日志 2.6 回滚2.6.1 从仓库回滚到工作区2.6.2 取消工作…...
建筑模板木模好还是钢模好
在建筑施工中,模板是一项关键的工程,对于建筑结构的质量和施工效率起着重要作用。在选择模板材料时,木模和钢模都是常见的选择。本文将比较木模和钢模的优缺点,以帮助您做出明智的选择。 正文:一、木模:传统…...
写代码中碰到的错误
bind绑定类内成员导致 "no matching function for call to ..." 当bind绑定类内成员时,需要指明绑定的成员所在类的位置。 上面未指明Remove函数在哪个类中从而导致错误。 此外 bind 的函数指针类型是const类型的,都需要添加 const 修饰。 S…...
java文件传输简单方法
java文件传输简单方法 假设现在已经打包了一个文件(1233444333),要将这个文件传输给另一方: import java.io.*; public class F_PasswordUnPassword { public static void main (String[] args)throws Exception { ByteArrayOutp…...
Vue3后台管理系统Element-plus_侧边栏制作_无限递归
在home.view中添加代码 <template><div><div class"common-layout"><el-container><el-header class"common-header flex-float"><div class"flex"><img class"logo" src"../assets/logo…...
PCIe基础概念
《PCI_Exepress体系结构导读》《WDC databook》读书笔记 RCB read completion boundary MPS max payload size MRRS max read request size 4K对齐 Specifies the address page boundary size supported by the AXI bridge. No packet can have an address that crosses…...
GE IS220PVIBH1A 336A4940CSP16 数字输入模块
GE IS220PVIBH1A(336A4940CSP16)是一种数字输入模块,通常用于工业控制和自动化系统中,以将数字信号输入到PLC(可编程逻辑控制器)或其他控制系统中。以下是一些可能的产品特点和功能,但请注意&am…...
比特币与火人节
作者:Greg Cipolaro,NYDIG 全球研究主管 编译:WEEX 唯客 阅读提要: 灰度胜诉后市场缺乏后续动力,这告诉我们什么信号? ETF 不断涌现,但投资者似乎不太关心。 比特币和火人节:它们有何…...
Nginx 中 location 和 proxy_pass 斜杠/ 问题
location 的斜杠问题比较好理解,不带斜杠的是模糊匹配。例如: location /doc 可以匹配 /doc/index.html,也可以匹配 /docs/index.html。 location /doc/ 强烈建议使用这种 只能匹配 /doc/index.html,不能匹配 /docs/index…...
【Spring】开发框架Spring核心技术含Resource接口详细讲解
这里写目录标题 前言1. Spring简介2. Spring体系结构2.1 核心模块(Core Container)2.2 AOP模块2.3 数据访问集成模块(Data Access/Integration )2.4 Web模块 3. 初识Ioc与DI3.1 IoC控制反转和DI依赖注入3.2 常见的几种注入方法3.3 Spring的IoC例子3.4 Sp…...
【随想】每日两题Day.5 (实则一题)
题目:LeetCode 707.设计链表 你可以选择使用单链表或者双链表,设计并实现自己的链表。 单链表中的节点应该具备两个属性:val 和 next 。val 是当前节点的值,next 是指向下一个节点的指针/引用。 如果是双向链表,则还…...
【LeetCode刷题笔记】动态规划 — 70.爬楼梯
创作不易,本篇文章如果帮助到了你,还请点赞 关注支持一下♡>𖥦<)!! 主页专栏有更多知识,如有疑问欢迎大家指正讨论,共同进步! 更多算法知识专栏:算法分析🔥 给大家跳段街舞感谢…...
2024腾讯校招后端面试真题汇总及其解答(三)
21【算法题】反转链表 题目: 给定单链表的头节点 head ,请反转链表,并返回反转后的链表的头节点。 示例 1: 输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]示例 2: 输入:head = [1,2] 输出:[2,1]示例 3: 输入:head = [] 输出:[]提示: 链表中节点的数目范围是 [0, 5…...
mysql的分组group by
文章目录 一、介绍1、分组查询的内容2、多字段分组3、将查询内容连接group_concat4、有条件的分组查询having 一、介绍 将某个字段的相同值分为一组,分组查询的结果强调的是一个整体,每组内容只显示一行分组查询的内容一般要查询分组字段,因…...
Swoole 介绍以及 编译安装
Swoole是什么? Swoole是一个PHP语言的开源异步网络通信引擎,它是以PHP语言为基础,以C语言编写的扩展。它可以让PHP语言程序拥有异步网络通信能力,并且能够支持高并发、高性能的TCP/UDP/Unix Socket/HTTP服务器。 Swoole的优势 …...
Ubuntu终端指令
目录 目录 一、基本指令 1.命令行提示符 2.切换用户 3.修改密码 4.查看当前目录下的文件 5.修改文件权限---chmod 6.cd 切换路径 7.touch 8.cat 9.echo 10.mkdir 11. rm/rmdir 二、在线下载软件 1.更新软件源 2.更新软件列表 3.下载软件 三、离线安装软件 1. …...
代做毕业设计网站有哪些/微信营销模式有哪些
它是 子Logger 是否继承 root的Logger 的 输出源(appender) 的标志位。 具体说,默认情况下子Logger会继承root的Logger的appender,也就是说子Logger会在root的Logger的appender里输出。 1.若是additivity设为false,则…...
找老外做网站可靠吗/cms建站系统
f{} Python3.6及以上版本才有,Python3.5及以下版本会出错。 %s%() 常用格式 {}.format() {}里面可以带数字也可以不带数字,带数字编号可以调换输出顺序,还可以带关键字。 device torch.device(fcuda:{opt.local_rank}) #python3.6 device …...
色弱可以做网站开发吗/廊坊优化外包
Android中创建多线程管理器实例如果你要反复执行一个任务,用不同的数据集(参数不同),但一次只要一个执行(任务是单线程的),IntentService符合你的需求。当需要在资源可用时自动执行任务,或允许多任务同时执行,你需要一…...
长沙岳麓区做网站/百度搜索推广技巧
对于每一个站长而言,都会遇到要进行网站测试的时候。这个时候,往往需要备份数据库。如果按照一般的操作方式,都是先把数据库导出并备份到本地,然后再服务器上测试。如果一切正常还好,一旦出了问题,就又得把…...
南通政府网站建设/网上网络推广
在 webpack-dev-server 的配置中添加disableHostCheck: true转载于:https://www.cnblogs.com/xiaoroad/p/8967353.html...
辽宁企业网站建设公司/成都seo优化排名公司
在登录Linux时要执行文件的过程如下:在刚登录Linux时,首先启动 /etc/profile 文件,然后再启动用户目录下的 ~/.bash_profile、 ~/.bash_login或 ~/.profile文件中的其中一个,执行的顺序为:~/.bash_profile、 ~/.bash_l…...