当前位置: 首页 > 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实际上在验收这一块的要求还是比较低的。 但是这个…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...