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

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

五子棋测试用例

一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏&#xff0c;有着深厚的文化底蕴。通过将五子棋制作成网页游戏&#xff0c;可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家&#xff0c;都可以通过网页五子棋感受到东方棋类…...

深入理解 React 样式方案

React 的样式方案较多,在应用开发初期,开发者需要根据项目业务具体情况选择对应样式方案。React 样式方案主要有: 1. 内联样式 2. module css 3. css in js 4. tailwind css 这些方案中,均有各自的优势和缺点。 1. 方案优劣势 1. 内联样式: 简单直观,适合动态样式和…...