当前位置: 首页 > 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;从而实现几乎实时…...

从零到一:STM32手动移植FreeRTOS的工程化实践与源码解析

1. 为什么需要手动移植FreeRTOS&#xff1f; 第一次接触FreeRTOS时&#xff0c;很多人会选择用STM32CubeMX自动生成工程。这确实方便&#xff0c;就像用预制菜做饭&#xff0c;但真正想掌握RTOS内核&#xff0c;手动移植才是"从买菜到炒菜"的完整过程。我遇到过不少项…...

PromptTemplate和ChatPromptTemplate的区别是什么呢?

我用最简单、最直白、一看就懂的方式给你讲清楚&#xff1a; PromptTemplate 和 ChatPromptTemplate 的真正区别 一句话总结 PromptTemplate 生成一段普通字符串 给补全模型/简单模型用ChatPromptTemplate 生成一整段聊天对话格式 给**聊天模型&#xff08;ChatGLM、Qwen、GP…...

新手指南:掌握3MF格式实现Blender高效3D打印工作流

新手指南&#xff1a;掌握3MF格式实现Blender高效3D打印工作流 【免费下载链接】Blender3mfFormat Blender add-on to import/export 3MF files 项目地址: https://gitcode.com/gh_mirrors/bl/Blender3mfFormat 副标题&#xff1a;从格式解析到自动化处理的完整应用方案…...

PTA编程题‘Person抽象类’避坑指南:变量命名冲突、多态指针数组与输出格式化的那些坑

PTA编程题‘Person抽象类’避坑指南&#xff1a;变量命名冲突、多态指针数组与输出格式化的那些坑 在C面向对象编程的实战中&#xff0c;抽象类和派生类的设计看似简单&#xff0c;却暗藏诸多陷阱。许多初学者在完成PTA/LeetCode这类编程题时&#xff0c;往往因为一些看似微不足…...

给嵌入式新手的Cortex-M0内核超详细图解:从寄存器到中断,一篇搞定STM32/GD32入门

给嵌入式新手的Cortex-M0内核超详细图解&#xff1a;从寄存器到中断&#xff0c;一篇搞定STM32/GD32入门 刚拿到STM32开发板时&#xff0c;看着密密麻麻的引脚和上百页的芯片手册&#xff0c;我完全不知道从哪里开始。直到导师指着原理图说&#xff1a;"把芯片想象成一个忙…...

轻量级PDF渲染库PdfiumAndroid:Android开发者的高效集成指南

轻量级PDF渲染库PdfiumAndroid&#xff1a;Android开发者的高效集成指南 【免费下载链接】PdfiumAndroid 项目地址: https://gitcode.com/gh_mirrors/pd/PdfiumAndroid 核心价值&#xff1a;为什么选择PdfiumAndroid&#xff1f; &#x1f4cc; 解决PDF渲染痛点&#…...

OpenRocket:从设计到飞行的全链路火箭仿真实战指南

OpenRocket&#xff1a;从设计到飞行的全链路火箭仿真实战指南 【免费下载链接】openrocket Model-rocketry aerodynamics and trajectory simulation software 项目地址: https://gitcode.com/GitHub_Trending/op/openrocket 火箭爱好者与工程师的终极工具&#xff1a;…...

Qwen3-ForcedAligner-0.6B生产环境:支持日均1000+分钟音频批处理任务

Qwen3-ForcedAligner-0.6B生产环境&#xff1a;支持日均1000分钟音频批处理任务 1. 项目概述 Qwen3-ForcedAligner-0.6B是一款基于阿里巴巴先进语音识别技术开发的本地化智能语音转录工具。该工具采用双模型架构设计&#xff0c;集成了Qwen3-ASR-1.7B语音识别模型和ForcedAli…...

HP-Socket技术债务管理会议决策记录:选项、理由与结果

HP-Socket技术债务管理会议决策记录&#xff1a;选项、理由与结果 【免费下载链接】HP-Socket High Performance TCP/UDP/HTTP Communication Component 项目地址: https://gitcode.com/gh_mirrors/hp/HP-Socket 作为一款高性能TCP/UDP/HTTP通信组件库&#xff0c;HP-So…...

OliveTin高级功能指南:定时任务、文件监控和实体动态更新

OliveTin高级功能指南&#xff1a;定时任务、文件监控和实体动态更新 【免费下载链接】OliveTin OliveTin gives safe and simple access to predefined shell commands from a web interface. 项目地址: https://gitcode.com/gh_mirrors/ol/OliveTin OliveTin是一个强…...