代码随想录算法训练营第五十五天|583. 两个字符串的删除操作、72. 编辑距离
583. 两个字符串的删除操作
- 刷题
https://leetcode.cn/problems/delete-operation-for-two-strings/description/ - 文章讲解
https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html - 视频讲解
https://www.bilibili.com/video/BV1we4y157wB/?vd_source=af4853e80f89e28094a5fe1e220d9062 -
题解:
class Solution {public int minDistance(String word1, String word2) {char[] char1 = word1.toCharArray();char[] char2 = word2.toCharArray();int len1 = char1.length;int len2 = char2.length;int dp[][] = new int [len1 + 1][len2 + 1];for(int i = 1; i <= len1; i++){for(int j = 1; j <= len2; j++){if(char1[i - 1] == char2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}return len1 + len2 - (2 * dp[len1][len2]);//和leetcode 1143只差在这一行。}
}
72. 编辑距离
- 刷题
https://leetcode.cn/problems/edit-distance/description/ - 文章讲解
https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html - 视频讲解
https://www.bilibili.com/video/BV1qv4y1q78f/?vd_source=af4853e80f89e28094a5fe1e220d9062 -
题解:
public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m + 1][n + 1];// 初始化for (int i = 1; i <= m; i++) {dp[i][0] = i;}for (int j = 1; j <= n; j++) {dp[0][j] = j;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// 因为dp数组有效位从1开始// 所以当前遍历到的字符串的位置为i-1 | j-1if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;}}}return dp[m][n];
}
相关文章:
代码随想录算法训练营第五十五天|583. 两个字符串的删除操作、72. 编辑距离
583. 两个字符串的删除操作 刷题https://leetcode.cn/problems/delete-operation-for-two-strings/description/文章讲解https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html视频讲解https://…...
StringRedisTemplate Autowired注入为空解决
如下注入方式报空指针异常: java.lang.NullPointerException: null Autowiredprivate StringRedisTemplate redisTemplate; 解决办法:查看该类上有没有加注解,如Component等,没加的话加上。 还有一种是在工具类中使用,…...
c语言:文件操作
1. 为什么使⽤⽂件? 如果没有⽂件,我们写的程序的数据是存储在电脑的内存中,如果程序退出,内存回收,数据就丢失 了,等再次运⾏程序,是看不到上次程序的数据的,如果要将数据进⾏持久…...
C#事件实例详解
一、什么是事件? 在C#中,事件(event)是一种特殊的类成员,它允许类或对象通知其他类或对象发生了某些事情。 从语法上看,事件的声明类似于字段,但它们在功能和行为上有一些重要的区别。 从技术角度来说,事件实际上是一个封装了事件订阅和取消订阅功能的委托字段。…...
零基础机器学习(3)之机器学习的一般过程
文章目录 一、机器学习一般过程1.数据获取2.特征提取3.数据预处理①去除唯一属性②缺失值处理A. 均值插补法B. 同类均值插补法 ③重复值处理④异常值⑤数据定量化 4.数据标准化①min-max标准化(归一化)②z-score标准化(规范化) 5.…...
用java做一个双色球彩票系统
代码如下: import java.util.Random; public class HelloWorld{public static void main(String[] args){//1、生成中奖号码 int[] arrcreateNumber();for (int i 0;i<arr.length;i) {System.out.print(arr[i]" ");}}public static int[] createNu…...
某对象存储元数据集群改造流水账
软件产品:某厂商提供的不便具名的对象存储产品,核心底层技术源自HDFS和Amazon S3,元数据集群采用了基于MongoDB的NOSQL数据库产品和MySQL数据库产品相结合。 该产品的元数据逻辑示意图如下: 业务集群现状:当前第3期建…...
前端理论总结(js)——filter、foearch、for in 、for of 、for的区别以及返回值
Filter: 用途:用于筛选数组中符合条件的元素,返回一个新数组。 返回值:返回一个新数组,包含经过筛选的元素。 Foreach: 用途:遍历数组中的每个元素,执行回调函数。 返回值&#x…...
【JavaEE初阶系列】——多线程案例一——单例模式 (“饿汉模式“和“懒汉模式“以及解决线程安全问题)
目录 🚩单例模式 🎈饿汉模式 🎈懒汉模式 ❗线程安全问题 📝加锁 📝执行效率提高 📝指令重排序 🍭总结 单例模式,非常经典的设计模式,也是一个重要的学科&#x…...
革新水库大坝监测:传统软件与云平台之比较
在水库大坝的监测管理领域,传统监测软件虽然曾发挥了重要作用,但在多方面显示出了其局限性。传统解决方案通常伴随着高昂的运维成本,需要大量的硬件支持和人员维护,且软件整合和升级困难,限制了其灵活性和扩展性。 点击…...
C++模版(基础)
目录 C泛型编程思想 C模版 模版介绍 模版使用 函数模版 函数模版基础语法 函数模版原理 函数模版实例化 模版参数匹配规则 类模版 类模版基础语法 C泛型编程思想 泛型编程:编写与类型无关的通用代码,是代码复用的一种手段。 模板是泛型编程…...
MySQL驱动Add Batch优化实现
MySQL 驱动 Add Batch 优化实现 MySQL 驱动会在 JDBC URL 添加 rewriteBatchedStatements 参数时,对 batch 操作进行优化。本文测试各种参数组合的行为,并结合驱动代码简单分析。 batch参数组合行为 useServerPrepStmts 参数 PreparedStatement psmt…...
手撕算法-数组中的第K个最大元素
描述 分析 使用小根堆,堆元素控制在k个,遍历数组构建堆,最后堆顶就是第K个最大的元素。 代码 class Solution {public int findKthLargest(int[] nums, int k) {// 小根堆PriorityQueue<Integer> queue new PriorityQueue<>…...
【vue】computed和watch的区别和应用场景
Computed 和 Watch 是 Vue.js 中用于监视数据变化的两个不同特性,它们各自有不同的应用场景和功能。 Computed: 计算属性(Computed properties)用于声明基于其他数据属性的计算值。它具有缓存功能,只有在依赖的数…...
ARM.day8
1.自己设置温度湿度阈值,当温度过高时,打开风扇,蜂鸣器报警 2.当湿度比较高时,打开LED1灯,蜂鸣器报警 main.c #include "si7006.h" #include "CH1.h" #include "led.h" // 延时函数in…...
SpringCloud Gateway工作流程
Spring Cloud Gateway的工作流程 具体的流程: 用户发送请求到网关 请求断言,用户请求到达网关后,由Gateway Handler Mapping(网关处理器映射)进行Predicates(断言),看一下哪一个符合…...
西井科技与安通控股签署战略合作协议 共创大物流全新生态
2024年3月21日,西井科技与安通控股在“上海硅巷”新象限空间正式签署战略合作框架协议。双方基于此前在集装箱物流的成功实践与资源优势,积极拓展在AI数字化产品、新能源自动驾驶解决方案和多场景应用,以及绿色物流链等领域的深度探索、强强联…...
CCCorelib 点云RANSAC拟合球体(CloudCompare内置算法库)
文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 RANSAC是一种随机参数估计算法。RANSAC从样本中随机抽选出一个样本子集,使用最小方差估计算法对这个子集计算模型参数,然后计算所有样本与该模型的偏差,再使用一个预先设定好的阈值与偏差比较,当偏差小于阈值时…...
map china not exists. the geojson of the map must be provided.
map china not exists. the geojson of the map must be provided. 场景:引入echarts地图报错map china not exists. the geojson of the map must be provided. 原因: echarts版本过高,ECharts 之前提供下载的矢量地图数据来自第三方&…...
Redis如何删除大key
参考阿里云Redis规范 查找大key: redis-cli --bigkeys 1、String类型: Redis 4.0及以后版本提供了UNLINK命令,该命令与DEL命令类似,但它会在后台异步删除key,不会阻塞当前客户端,也不会阻塞Redis服务器的…...
基于Comsol相控阵技术的实用钢纵波超声波成像模型:单层缺陷TFM成像与压力声学仿真
comsol 相控阵 超声成像 此模型为压力声学仿真超声波,实用钢纵波速度6000 密度7.8e-9 单层缺陷TFM成像相控阵超声检测这玩意儿在工业NDT圈子里算是老熟人了,今天咱们拿COMSOL搞个钢材料缺陷成像的骚操作。模型基础是压力声学模块,材料参数先给…...
WAN2.2文生视频开源镜像快速上手:ComfyUI界面操作+SDXL Prompt Styler详解
WAN2.2文生视频开源镜像快速上手:ComfyUI界面操作SDXL Prompt Styler详解 想试试用几句话就让AI帮你生成一段视频吗?WAN2.2文生视频开源镜像,结合了强大的ComfyUI界面和SDXL Prompt Styler风格化工具,让这个过程变得直观又简单。…...
物理引擎核心原理拆解:GJK算法如何用Support函数取代SAT检测
物理引擎核心原理拆解:GJK算法如何用Support函数取代SAT检测 在实时物理模拟的世界里,碰撞检测算法的效率直接决定了虚拟世界的真实感与流畅度。当两个刚体在三维空间中高速运动时,传统分离轴定理(SAT)需要检测多达15组…...
别再手动改请求头了!用BurpSuite插件5分钟搞定自动化添加(附完整Java代码)
解放双手:用BurpSuite插件实现HTTP请求头自动化管理 每次安全测试时,你是否也厌倦了反复点击"拦截"按钮、手动添加X-Debug-Header或修改User-Agent?作为一名长期与BurpSuite打交道的安全工程师,我深知这种重复性操作不仅…...
Qwerty Learner可扩展性设计:为未来功能预留空间的完整指南
Qwerty Learner可扩展性设计:为未来功能预留空间的完整指南 【免费下载链接】qwerty-learner 为键盘工作者设计的单词记忆与英语肌肉记忆锻炼软件 / Words learning and English muscle memory training software designed for keyboard workers 项目地址: https:…...
MCP 会不会成为 AI 系统的“新中间件”?
一、为什么人们开始把 MCP 和“中间件”类比?(Why Do People Start Comparing MCP to “Middleware”?)1、MCP 出现的位置非常“熟悉”(MCP Appears in a Very Familiar Position)当人们第一次在企业架构中引入 MCP 时…...
无损视频剪辑终极指南:如何用LosslessCut保持原始画质快速编辑
无损视频剪辑终极指南:如何用LosslessCut保持原始画质快速编辑 【免费下载链接】lossless-cut The swiss army knife of lossless video/audio editing 项目地址: https://gitcode.com/gh_mirrors/lo/lossless-cut 在视频编辑的世界里,质量与速度…...
企业开始用 AI 后,最容易被忽略的其实是这件事!
这两年,越来越多企业开始尝试把 AI 用到日常办公中。从写邮件、整理纪要,到查询知识库、生成文档,AI 正在从个人工具变成企业工作的一部分。但很多企业在推进 AI 时,首先关注的往往是功能和效率,比如“能不能写”“能不…...
[实战] 从点云到避障:FIESTA ESDF实时构建全解析
1. 为什么需要实时ESDF构建 当机器人需要在复杂环境中自主移动时,避障是最基础也最关键的能力。想象一下你在黑暗中摸索前行,手碰到墙壁就立即缩回——机器人也需要类似的"触觉"。欧氏距离场(ESDF)就是机器人的三维空间…...
硕博必看|论文盲审前,这些硬伤一定要避开!
作为过来人,太懂硕博生面对论文盲审的焦虑——熬夜完成的论文,查重、改格式、找导师签字后,仍怕因细节被盲审专家打回、延毕。盲审专家只看质量不看人情,很多不起眼的小问题,都可能成为“致命扣分点”。今天分享核心干…...
