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

代码随想录算法训练营第59天:动态[1]

代码随想录算法训练营第59天:动态

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

力扣题目链接(opens new window)

给定两个单词 word1 和 word2,找到使得 word1 和 word2 相同所需的最小步数,每步可以删除任意一个字符串中的一个字符。

示例:

  • 输入: “sea”, “eat”
  • 输出: 2
  • 解释: 第一步将"sea"变为"ea",第二步将"eat"变为"ea"

#算法公开课

《代码随想录》算法视频公开课 ****(opens new window)****​ LeetCode:583.两个字符串的删除操 ****(opens new window)****​ ,相信结合视频再看本篇题解,更有助于大家对本题的理解

#思路

#动态规划一

本题和动态规划:115.不同的子序列 ​**(opens new window)** 相比,其实就是两个字符串都可以删除了,情况虽说复杂一些,但整体思路是不变的。

这次是两个字符串可以相互删了,这种题目也知道用动态规划的思路来解,动规五部曲,分析如下:

  1. 确定dp数组(dp table)以及下标的含义

dp[i][j]:以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2,想要达到相等,所需要删除元素的最少次数。

这里dp数组的定义有点点绕,大家要撸清思路。

  1. 确定递推公式
  • 当word1[i - 1] 与 word2[j - 1]相同的时候
  • 当word1[i - 1] 与 word2[j - 1]不相同的时候

当word1[i - 1] 与 word2[j - 1]相同的时候,dp[i][j] = dp[i - 1][j - 1];

当word1[i - 1] 与 word2[j - 1]不相同的时候,有三种情况:

情况一:删word1[i - 1],最少操作次数为dp[i - 1][j] + 1

情况二:删word2[j - 1],最少操作次数为dp[i][j - 1] + 1

情况三:同时删word1[i - 1]和word2[j - 1],操作的最少次数为dp[i - 1][j - 1] + 2

那最后当然是取最小值,所以当word1[i - 1] 与 word2[j - 1]不相同的时候,递推公式:dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2,所以递推公式可简化为:dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);

这里可能不少录友有点迷糊,从字面上理解 就是 当 同时删word1[i - 1]和word2[j - 1],dp[i][j-1] 本来就不考虑 word2[j - 1]了,那么我在删 word1[i - 1],是不是就达到两个元素都删除的效果,即 dp[i][j-1] + 1。

  1. dp数组如何初始化

从递推公式中,可以看出来,dp[i][0] 和 dp[0][j]是一定要初始化的。

dp[i][0]:word2为空字符串,以i-1为结尾的字符串word1要删除多少个元素,才能和word2相同呢,很明显dp[i][0] = i。

dp[0][j]的话同理,所以代码如下:

vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
  1. 确定遍历顺序

从递推公式 dp[i][j] = min(dp[i - 1][j - 1] + 2, min(dp[i - 1][j], dp[i][j - 1]) + 1); 和dp[i][j] = dp[i - 1][j - 1]可以看出dp[i][j]都是根据左上方、正上方、正左方推出来的。

所以遍历的时候一定是从上到下,从左到右,这样保证dp[i][j]可以根据之前计算出来的数值进行计算。

  1. 举例推导dp数组

以word1:“sea”,word2:"eat"为例,推导dp数组状态图如下:

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

以上分析完毕,代码如下:

class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
for (int i = 1; i <= word1.size(); i++) {
for (int j = 1; j <= word2.size(); j++) {
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][j - 1] + 1);
}
}
}
return dp[word1.size()][word2.size()];
}
};
  • 时间复杂度: O(n * m)
  • 空间复杂度: O(n * m)

#动态规划二

本题和动态规划:1143.最长公共子序列 ​**(opens new window)** 基本相同,只要求出两个字符串的最长公共子序列长度即可,那么除了最长公共子序列之外的字符都是必须删除的,最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。

代码如下:

class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));
for (int i=1; i<=word1.size(); i++){
for (int j=1; j<=word2.size(); j++){
if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return word1.size()+word2.size()-dp[word1.size()][word2.size()]*2;
}
};
  • 时间复杂度: O(n * m)
  • 空间复杂度: O(n * m)

相关文章:

代码随想录算法训练营第59天:动态[1]

代码随想录算法训练营第59天&#xff1a;动态 两个字符串的删除操作 力扣题目链接(opens new window) 给定两个单词 word1 和 word2&#xff0c;找到使得 word1 和 word2 相同所需的最小步数&#xff0c;每步可以删除任意一个字符串中的一个字符。 示例&#xff1a; 输入: …...

jvm性能监控常用工具

在java的/bin目录下有许多java自带的工具。 我们常用的有 基础工具 jar:创建和管理jar文件 java&#xff1a;java运行工具&#xff0c;用于运行class文件或jar文件 javac&#xff1a;java的编译器 javadoc&#xff1a;java的API文档生成工具 性能监控和故障处理 jps jstat…...

ISP IC/FPGA设计-第一部分-SC130GS摄像头分析-IIC通信(1)

1.摄像头模组 SC130GS通过一个引脚&#xff08;SPI_I2C_MODE&#xff09;选择使用IIC或SPI配置接口&#xff0c;通过查看摄像头模组的原理图&#xff0c;可知是使用IIC接口&#xff1b; 通过手册可知IIC设备地址通过一个引脚控制&#xff0c;查看摄像头模组的原理图&#xff…...

HTTP协议头中X-Forwarded-For是能做什么?

X-Forwarded-For和相关几个头部的理解 $remote_addr 是nginx与客户端进行TCP连接过程中&#xff0c;获得的客户端真实地址. Remote Address 无法伪造&#xff0c;因为建立 TCP 连接需要三次握手&#xff0c;如果伪造了源 IP&#xff0c;无法建立 TCP 连接&#xff0c;更不会有后…...

Linux高并发服务器开发(八)Socket和TCP

文章目录 1 IPV4套接字结构体2 TCP客户端函数 3 TCP服务器流程函数代码粘包 4 三次握手5 四次挥手6 滑动窗口 1 IPV4套接字结构体 2 TCP客户端 特点&#xff1a;出错重传 每次发送数据对方都会回ACK&#xff0c;可靠 tcp是打电话的模型&#xff0c;建立连接 使用连接 关闭连接…...

力扣第220题“存在重复元素 III”

在本篇文章中&#xff0c;我们将详细解读力扣第220题“存在重复元素 III”。通过学习本篇文章&#xff0c;读者将掌握如何使用桶排序和滑动窗口来解决这一问题&#xff0c;并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释&#xff0c;以便于理解。 问题描述…...

Qt实战项目——贪吃蛇

一、项目介绍 本项目是一个使用Qt框架开发的经典贪吃蛇游戏&#xff0c;旨在通过简单易懂的游戏机制和精美的用户界面&#xff0c;为玩家提供娱乐和编程学习的机会。 游戏展示 二、主要功能 2.1 游戏界面 游戏主要是由三个界面构成&#xff0c;分别是游戏大厅、难度选择和游戏…...

Windows 10,11 Server 2022 Install Docker-Desktop

docker 前言 Docker 是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的镜像中,然后发布到任何流行的 Linux或Windows 机器上,也可以实现虚拟化。容器是完全使用沙箱机制,相互之间不会有任何接口。 docker-compose Compose 是用于定义和运行…...

C++中的RAII(资源获取即初始化)原则

C中的RAII&#xff08;Resource Acquisition Is Initialization&#xff0c;资源获取即初始化&#xff09;原则是一种管理资源、避免资源泄漏的惯用法。RAII是C之父Bjarne Stroustrup提出的设计理念&#xff0c;其核心思想是将资源的获取&#xff08;如动态内存分配、文件句柄、…...

【机器学习】Whisper:开源语音转文本(speech-to-text)大模型实战

目录 一、引言 二、Whisper 模型原理 2.1 模型架构 2.2 语音处理 2.3 文本处理 三、Whisper 模型实战 3.1 环境安装 3.2 模型下载 3.3 模型推理 3.4 完整代码 3.5 模型部署 四、总结 一、引言 上一篇对​​​​​​​ChatTTS文本转语音模型原理和实战进行了讲解&a…...

ubuntu22.04 编译安装openssl C++ library

#--------------------------------------------------------------------------- # openssl C library # https://www.openssl.org/source/index.html #--------------------------------------------------------------------------- cd /opt/download # 下载openssl-3.0.13…...

百度Agent初体验(制作步骤+感想)

现在AI Agent很火&#xff0c;最近注册了一个百度Agent体验了一下&#xff0c;并做了个小实验&#xff0c;拿它和零一万物&#xff08;Yi Large&#xff09;和文心一言&#xff08;ERNIE-4.0-8K-latest&#xff09;阅读了相同的一篇网页资讯&#xff0c;输出资讯摘要&#xff0…...

7-491 3名同学5门课程成绩,输出最好成绩及所在的行和列(二维数组作为函数的参数)

编程:数组存储3名同学5门课程成绩 输出最好成绩及所在的行和列 要求&#xff1a;将输入、查找和打印的功能编写成函数 并将二维数组通过指针参数传递的方式由主函数传递到子函数中 输入格式: 每行输入一个同学的5门课的成绩&#xff0c;每个成绩之间空一格&#xff0c;见输入…...

OpenCloudOS开源的操作系统

OpenCloudOS 是一款开源的操作系统&#xff0c;致力于提供高性能、稳定和安全的操作系统环境&#xff0c;以满足现代计算和应用程序的需求。它结合了现代操作系统设计的最新技术和实践&#xff0c;为开发者和企业提供了一个强大的平台。本文将详细介绍 OpenCloudOS 的背景、特性…...

排序题目:多数元素 II

文章目录 题目标题和出处难度题目描述要求示例数据范围进阶 前言解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 解法三思路和算法代码复杂度分析 题目 标题和出处 标题&#xff1a;多数元素 II 出处&#xff1a;229. 多数元素 II 难度 3 级 题目描述 …...

<电力行业> - 《第1课:电力行业的五大四小》

1 什么是电力行业的五大四小&#xff1f; 我们常说的电力行业的五大四小&#xff0c;指的是电力行业有实力的公司&#xff0c;分为&#xff1a;较强梯队的五大集团、较弱梯队的四小豪门。 五个实力雄厚的集团&#xff0c;分别是&#xff1a; 中国华能集团公司中国大唐集团公…...

数据库定义语言(DDL)

数据库定义语言&#xff08;DDL&#xff09; 一、数据库操作 1、 查询所有的数据库 SHOW DATABASES;效果截图&#xff1a; 2、使用指定的数据库 use 2403 2403javaee;效果截图&#xff1a; 3、创建数据库 CREATE DATABASE 2404javaee;效果截图&#xff1a; 4、删除数据…...

mybatis实现多表查询

mybatis高级查询【掌握】 1、准备工作 【1】包结构 创建java项目&#xff0c;导入jar包和log4j日志配置文件以及连接数据库的配置文件&#xff1b; 【2】导入SQL脚本 运行资料中的sql脚本&#xff1a;mybatis.sql 【3】创建实体来包&#xff0c;导入资料中的pojo 【4】User…...

数据结构:队列详解 c++信息学奥赛基础知识讲解

目录 一、队列概念 二、队列容器 三、队列操作 四、代码实操 五、队列遍历 六、案例实操 题目描述&#xff1a; 输入格式&#xff1a; 输出格式&#xff1a; 输入样例&#xff1a; 输出样例&#xff1a; 详细代码&#xff1a; 一、队列概念 队列是一种特殊的线性…...

硬件开发笔记(二十三):贴片电阻的类别、封装介绍,AD21导入贴片电阻原理图封装库3D模型

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/140110514 长沙红胖子Qt&#xff08;长沙创微智科&#xff09;博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

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

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

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...