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

代码随想录算法训练营第56天 | 583、72

583. 两个字符串的删除操作

题目描述

给定两个单词 word1 和 word2 ,返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例1:
输入: w o r d 1 = " s e a " , w o r d 2 = " e a t " word1 = "sea", word2 = "eat" word1="sea",word2="eat"
输出: 2 2 2
示例2:
输入: w o r d 1 = " l e e t c o d e " , w o r d 2 = " e t c o " word1 = "leetcode", word2 = "etco" word1="leetcode",word2="etco"
输出: 4 4 4

思路

1、确定dp数组
dp[i][j]表示以i-1为结尾的字符串word1和以j-1为结尾的字符串word2,想要达到相等,所需要删除元素的最少次数
2、确定递推公式
当word[i-1]和word2[j-1]相等时,直接等于上一状态即可
不相等时,存在三种情况:
1)删word1[i-1]
2)删word2[j-1]
3)同时删word1[i-1]和word2[j-1]
最后取最小值

解法

class Solution {public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1+1][len2+1];for(int i = 1;i<= len1;i++){for(int j = 1;j<=len2;j++){if(word1.charAt(i-1) == word2.charAt(j-1)){dp[i][j] = dp[i-1][j-1] +1;}else{dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}}return len1+len2-dp[len1][len2]*2;}
}

总结

好好看,好好学

72. 编辑距离

题目描述

给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符
示例1:
输入: w o r d 1 = " h o r s e " , w o r d 2 = " r o s " word1 = "horse", word2 = "ros" word1="horse",word2="ros"
输出: 3 3 3
示例2:
输入: w o r d 1 = " i n t e n t i o n " , w o r d 2 = " e x e c u t i o n " word1 = "intention", word2 = "execution" word1="intention",word2="execution"
输出: 5 5 5

思路

1、确定dp数组
dp[i][j]表示以下标i-1为结尾的字符串word1,和以下标j-1为结尾的字符串word2,最近编辑距离为dp[i][j]
2、确定递推公式
word1[i-1]和word2[j-1]
相等时,不进行操作
不相等时,可以进行增删改的动作

解法

class Solution {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++){if(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];}
}

总结

最近考试周,没细看,我有罪,等考试周结束之后再好好总结

相关文章:

代码随想录算法训练营第56天 | 583、72

583. 两个字符串的删除操作 题目描述 给定两个单词 word1 和 word2 &#xff0c;返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 示例1&#xff1a; 输入&#xff1a; w o r d 1 " s e a " , w o r d 2 " e a t …...

c++输入输出文件操作stream

系列文章目录 C IO库 文章目录 系列文章目录前言一、文件IO概述coutcin其他istream类方法 文件输入和输出内核格式化总结 前言 一、文件IO 概述 c程序把输入和输出看作字节流。输入时&#xff0c;程序从输入流中抽取字节&#xff1a;输出时&#xff0c;程序将字节流插入到输…...

【小呆的力学笔记】非线性有限元的初步认识【三】

文章目录 1.2.2 基于最小势能原理的线性有限元一般格式1.2.2.1 离散化1.2.2.2 位移插值1.2.2.3 单元应变1.2.2.4 单元应力1.2.2.5 单元刚度矩阵1.2.2.6 整体刚度矩阵1.2.2.7 处理约束1.2.2.8 求解节点载荷列阵1.2.2.9 求解位移列阵1.2.2.10 计算应力矩阵等 1.2.2 基于最小势能原…...

python计算闰年

这里说明一下&#xff1a;看到网上很多写python计算闰年的&#xff0c;有很多是不同。 有份省级期刊万年历计算公元1-10000年的闰年 算法如下&#xff1a;4000年停闰一次。区别其他算法&#xff0c;有些是3200年停闰一次。 def division(dividend, divisor) -> bool:"…...

聊聊如何使用Js写一个简单的二级联动和三级联动呢?

前言&#xff1a;咳咳哈&#xff0c;大佬说&#xff1a;"这不是有手就行了&#xff1f;"好吧&#xff0c;这里不做过多罗里吧嗦&#xff0c;真的不过多吹&#xff0c;我们在下面直接上代码上注释。 文章目录&#xff1a; 原Js二级联动实现原Js三级联动实现 一、二级…...

IPv4 和 IPv6 的特点、区别以及在互联网中的应用

在当今互联网时代&#xff0c;IP 地址是连接和通信的基础。IPv4&#xff08;Internet Protocol version 4&#xff09;和 IPv6&#xff08;Internet Protocol version 6&#xff09;是两种常见的 IP 地址版本。IPv4 是最早广泛使用的 IP 地址协议&#xff0c;而 IPv6 则是 IPv4…...

JavaScript处理移动web交互

touch对象和touchevent touch事件 touch对象 每一次发生touch事件时就会产生一个touch对象&#xff0c;类似事件处理函数中的事件对象。 <div class" "><button class"child" style"height: 400px; width: 400px">我是按钮</b…...

4年测试经验,一问三不知,过于离谱...

公司今年要招人&#xff0c;面倒是面了很多测试&#xff0c;但没有一个合适的。一开始想要的就是中级的水准&#xff0c;也没指望来大牛&#xff0c;当然来了更好&#xff0c;提供的薪资在10-20k,来面试的人有很多&#xff0c;但平均水准真的是让人失望。 看简历时很多都写着3…...

Java 与查找算法(2)二分查找

一、二分查找 二分查找&#xff0c;也称折半查找&#xff0c;是一种常见的查找算法。它的思想是将有序数组分成两部分&#xff0c;取中间位置的值与目标值进行比较&#xff0c;如果相等则返回该位置&#xff0c;如果目标值小于中间值&#xff0c;则在左半部分继续查找&#xf…...

Java程序设计入门教程--原始类与包装类

包装类 Java语言是一个面向对象的语言&#xff0c;但是Java中的基本数据类型却是不面向对象的&#xff0c;这在实际使用时存在很多的不便。 为了解决这个不足&#xff0c;在设计类时为每个基本数据类型设计了一个对应的类进行代表&#xff0c;这样八个和基本数据类型对应的类统…...

pip安装python库速度慢、失败及超时报错解决办法

背景&#xff1a; 随着人工智能的不断兴起&#xff0c;python作为最接近人工智能的语言&#xff0c;变得越来越流行&#xff0c;人生苦短&#xff0c;python要学起来。之所以越来用的人喜欢学习python和研究Python&#xff0c;除了python本身便于学些、语法简短、面向对象等特点…...

向量数据库

向量数据库可以做哪些事情 存储和索引向量检索相似向量&#xff0c;还具有过滤功能自动将文档转变成向量&#xff0c;所以会自动化分词、向量化、索引等操作 目前存在的向量数据库&#xff1a; 名称github开源协议chromahttps://github.com/chroma-core/chromaApache 2.0Mil…...

leetcode 11.盛最多水的容器

题目描述 跳转到leetocde题目 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线&#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明&#xff…...

都说00后已经躺平了,但是有一说一,该卷的还是卷啊。

这不&#xff0c;三月份春招我们公司来了个00后&#xff0c;工作没两年&#xff0c;跳槽到我们公司起薪20K&#xff0c;都快接近我了。 后来才知道人家是个卷王&#xff0c;从早干到晚就差搬张床到工位睡觉了。 最近和他聊了一次天&#xff0c;原来这位小老弟家里条件不太好&…...

牛客网刷题学习SQL(二)

SQL22 统计每个学校的答过题的用户的平均答题数 描述 运营想要了解每个学校答过题的用户平均答题数量情况&#xff0c;请你取出数据。 用户信息表 user_profile&#xff0c;其中device_id指终端编号&#xff08;认为每个用户有唯一的一个终端&#xff09;&#xff0c;gender指…...

深蓝学院 C++笔记 先导篇章 - 绪论

一、介绍-老师寄语 为什么选择C&#xff1f; 高性能解决问题 二、C推荐书目 1. 基础 《C Primer》&#xff0c;Stanley B. Lippman 等著&#xff0c;王刚、杨巨峰等译 2. 进阶 《Effective C》&#xff0c;Scott Meyers 著&#xff0c;侯捷译。 《More Effective C》&am…...

R7-19 天梯赛团队总分

“天梯赛”的竞赛题目一共有 15 道&#xff0c;分为 3 个梯级&#xff1a; 基础级设 8 道题&#xff0c;其中 5 分、10 分、15 分、20 分的题各 2 道&#xff0c;满分为 100 分&#xff1b;题目编号相应为L1-X&#xff0c;X取1,2,3,4,5,6,7,8&#xff0c;分别表示基础级的8道题…...

使用 Kotlin 的 Opt-in (选择加入)功能注解API提示当前非稳定API

前言 之前在给公司项目封装库的时候&#xff0c;领导告诉我封装的漂亮一点&#xff0c;等以后公司发展起来了可能需要把这个库提供给第三方接入使用。 此时&#xff0c;就有这么一个问题&#xff1a;某些功能函数使用条件比较苛刻&#xff0c;直接使用可能会出现意想不到的后…...

webpack配置排除打包

webpack配置排除打包 思路 打包时&#xff0c;不要把类似于element-ui第三方的这些包打进来 从网络上&#xff0c;通过url地址直接引入这些包 操作 &#xff08;1&#xff09;先找到 vue.config.js&#xff0c; 添加 externals 项&#xff0c;具体如下&#xff1a; config…...

HNU-操作系统OS-ucoreLab系列-感悟

谨以此片篇,献给熬夜的8个晚上,以及逝去的时光。 感悟: 今天结束了所有的Lab实验(2023.6.3),感慨万千。 喜是这个实验终于结束了,悲是其实有好多地方我都没有理解。 应该指出,由于验收的助教学长学姐们的宽容,HNU实际上在验收这一块的要求还是比较低的。 但是这个…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...