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

力扣 72. 编辑距离 python AC

动态规划

class Solution:def minDistance(self, word1, word2):size1 = len(word1)size2 = len(word2)dp = [[0] * (size2 + 1) for _ in range(size1 + 1)]for i in range(1, size1 + 1):dp[i][0] = dp[i - 1][0] + 1for i in range(1, size2 + 1):dp[0][i] = dp[0][i - 1] + 1for i in range(1, size1 + 1):for j in range(1, size2 + 1):if word1[i - 1] == word2[j - 1]:dp[i][j] = dp[i - 1][j - 1]else:dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1return dp[size1][size2]

定义状态dp[i][j]为:字符串1到第i位为止转化成字符串2到第j位为止需要的最少操作数

--初始化二维数组dp:size1+1行size2+1列

--处理边界:第0行/第0列表示空字符串1转化为字符串2/字符串1转化为空字符串2需要的操作数

(索引每+1,操作数+1,(需要增加/删去它长度次))

--从1到size1遍历i

  --从1到size2遍历j

    --如果字符串1第i位和字符串2第j位相等

      --dp[i][j] 和 dp[i - 1][j - 1] 相同(需要操作次数相同)

    --否则

      --dp[i][j] 为 dp[i - 1][j - 1](替换) dp[i - 1][j](删除)dp[i][j - 1] (插入)三者中的最小值 + 1

相关文章:

力扣 72. 编辑距离 python AC

动态规划 class Solution:def minDistance(self, word1, word2):size1 len(word1)size2 len(word2)dp [[0] * (size2 1) for _ in range(size1 1)]for i in range(1, size1 1):dp[i][0] dp[i - 1][0] 1for i in range(1, size2 1):dp[0][i] dp[0][i - 1] 1for i in…...

vue 发布项目

You are not allowed to force push code to a protected branch on this project. 分支做了保护,git中设置允许强制推送...

springBoot实现发送邮箱验证码 redis缓存源码

要在Spring Boot中实现发送邮箱验证码并使用Redis进行缓存,你需要遵循几个步骤。以下是一个简化的示例,展示了如何整合这些功能: 添加依赖 首先,确保你的pom.xml(Maven)或build.gradle(Gradle…...

QT--4

QT 使用定时器完成闹钟 #include "widget.h" #include "ui_widget.h"void Widget::timestart() {timer.start(1000); }void Widget::timeend() {timer.stop(); }Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(t…...

感染了后缀为.360勒索病毒如何应对?数据能够恢复吗?

导言: 在数字化时代的浪潮中,网络安全问题如同暗流涌动,威胁着每一个互联网用户的安宁。而近年来,一种名为.360勒索病毒的新型网络威胁逐渐浮出水面,以其独特的加密方式和狡猾的传播策略,给全球网络安全带…...

JavaSE多态

多态:一个对象在不同条件下表示的不同形态就叫多态。在程序中,多态是父类引用指定子类对象就叫多态。 多态是面向对象程序设计中的第三个特征 // 多态 class Father {String name;public void desc() {System.out.println("----------");Sys…...

M 有效算法

M 有效算法 本题考验二分知识&#xff0c;思路是二分k的取值&#xff0c;就按第一组样例来说当我们k取值为1的时候我们遍历数组想让|8-x|<k1的话x的取值范围是7-9&#xff0c;想让|3-x|<k2的话x的取值范围是1-5&#xff0c;两者x的区间不重合&#xff0c;说明肯定没有x能…...

知识付费系统制作,托管机构如何提高体验课转化率?要注意什么?

现在托管机构非常流行&#xff0c;一所学校周边就会出现好几家托管机构&#xff0c;所以竞争非常激烈。很多托管机构为了扩大生源&#xff0c;会选择体验课来让学生体验&#xff0c;至于如何提高体验课转化率&#xff0c;就看机构的本事了。 1、市场调研&#xff1a;摸清当前我…...

【iOS逆向与安全】网上gw如何自动登录与签到SM2,SM3,SM4算法加解密

1.下载 app 2.frida 调试 3.抓包查看接口 4.分析加密数据 5.易语言编写代码 1 .开始下载 下载好发现有越狱检测&#xff0c;检测点为&#xff1a; -[AppDelegate isJailBreak]; 于是编写插件xm代码 : %hook AppDelegate- (void)isJailBreak{NSLog("AppDelegate is…...

《CKA/CKAD应试指南/从docker到kubernetes 完全攻略》学习笔记 第14章 包管理helm v3

前言 考试大纲: 了解helm是如何工作的,从而实现快速部署应用 本章要点: 考点1:添加helm源 考点2:使用helm 部署应用 前面在使用wordpress + mysql 部署博客应用的时候,需要做许多工作,需要每个pod创建pv和pvc,然后分别创建每个应用pod及svc,整个过程非常麻烦. 如果搭建博客的…...

蓝桥杯备战.19有奖问答dfs

P9230 [蓝桥杯 2023 省 A] 填空问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) #include<bits/stdc.h> using namespace std; #define endl \n //#define int long long const int N 2e510; int a[N],w[N]; int ans 0; void dfs(int score,int cnt) {if(cnt>3…...

【JS红宝书学习笔记】第1、2章 初识JS

第1章 什么是JavaScript JavaScript 是一门用来与网页交互的脚本语言&#xff0c;包含以下三个组成部分。 ECMAScript&#xff1a;由 ECMA-262 定义并提供核心功能。文档对象模型&#xff08;DOM&#xff09;&#xff1a;提供与网页内容交互的方法和接口。浏览器对象模型&…...

学习java

在实验室看见这本书&#xff0c;无聊看了下&#xff0c;写出了第一个java代码 成功下载了eclipse并且汉化。 写了自己的第一个java程序&#xff1a; package ttttt;public class ttttt {public static void main(String[] args) {System.out.println("hello world")…...

Redis日常维护流程及技巧:确保稳定性与性能

目录 一、监控和报警设置 1.实时监控&#xff1a;洞察Redis的脉搏 &#xff08;1&#xff09;. 资源使用监控 &#xff08;2&#xff09;. 数据访问模式监控 &#xff08;3&#xff09;. 持久化监控 &#xff08;4&#xff09;. 客户端连接 2.报警机制&#xff1a;快速响…...

牛客华为机试题——难度:入门(python实现)

HJ7 取近似值 HJ9 提取不重复的整数 HJ46 截取字符串 HJ58 输入n个整数&#xff0c;输出其中最小的k个 HJ101 输入整型数组和排序标识&#xff0c;对其元素按照升序或降序进行排序 HJ7 取近似值 描述&#xff1a;写出一个程序&#xff0c;接受一个正浮点数值&#xff0c;输…...

数据结构与算法学习笔记之线性表五---循环链表的表示和实现(C++)

目录 前言 1.双向链表的定义 2.双向链表的表示和实现 1.定义 2.初始化 3.销毁 4.清空 5.表长 6.获取数据元素 7.前驱节点 8.后继节点 9.插入 10.删除 11.遍历 12.完整代码 前言 记录下双向链表的表示和实现。 1.循环链表的定义 循环链表(circular linked list)…...

微信小程序生命周期揭秘:从启动到消亡的全过程剖析【附代码】

微信小程序生命周期揭秘&#xff1a;从启动到消亡的全过程剖析 一、小程序生命周期概览核心生命周期函数 二、深入理解生命周期回调2.1 onLoad: 首次亮相的准备2.2 onShow: 重登舞台的瞬间2.3 onReady: 舞台就绪&#xff0c;静待表演2.4 onHide & onUnload: 谨慎离场&#…...

Linux 下载 miniconda

https://repo.anaconda.com/miniconda/ 下载对应版本&#xff1a; wget -c https://repo.anaconda.com/miniconda/Miniconda3-py310_24.3.0-0-Linux-x86_64.sh给下载的文件添加可执行权限 chmod x Miniconda3-py310_24.3.0-0-Linux-x86_64.sh安装 ./Miniconda3-py310_24.3.…...

第十五篇:全面防护:构建不容侵犯的数据库安全策略与实战指南

全面防护&#xff1a;构建不容侵犯的数据库安全策略与实战指南 1. 引言&#xff1a;数据库安全的现代战略 1.1 简介&#xff1a;数据库安全在当今的数字化时代中的重要性 在数字化的浪潮中&#xff0c;数据已成为企业乃至国家的核心资产&#xff0c;其价值不亚于实体世界的黄…...

电脑快速搜索文件及文件夹软件——Everything

一、前言 Everything是一款由voidtools开发的文件搜索工具&#xff0c;主要运行于Windows操作系统上。它的主要功能是快速、高效地搜索电脑上的文件和文件夹名称。Everything通过利用NTFS文件系统的MFT&#xff08;主文件表&#xff09;来索引文件&#xff0c;从而实现几乎实时…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...