算法训练营第五十六天|583. 两个字符串的删除操作 72. 编辑距离
目录
- Leetcode583. 两个字符串的删除操作
- Leetcode72. 编辑距离
Leetcode583. 两个字符串的删除操作
文章链接:代码随想录
题目链接:583. 两个字符串的删除操作
思路:直接记录需要改(增或删)几个,也就是求不公共的子序列
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] + 2, min(dp[i][j - 1] + 1, dp[i - 1][j] + 1));}}return dp[word1.size()][word2.size()];}
};
也可以记录最长公共子序列,再减
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));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][j - 1], dp[i - 1][j]);}}return word1.size() + word2.size() - dp[word1.size()][word2.size()] * 2;}
};
Leetcode72. 编辑距离
文章链接:代码随想录
题目链接:72. 编辑距离
思路:和上一题相比,差别在于多了替换,因此dp[i - 1][j - 1] 只需要多加一步即可变为dp[i][j]。
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 = 1; 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] + 1, min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));}}return dp[word1.size()][word2.size()];}
};
第五十六天打卡,今天给周老师写了个冰层项目进展,耽误了一些学习进度,加油!!!
相关文章:
算法训练营第五十六天|583. 两个字符串的删除操作 72. 编辑距离
目录 Leetcode583. 两个字符串的删除操作Leetcode72. 编辑距离 Leetcode583. 两个字符串的删除操作 文章链接:代码随想录 题目链接:583. 两个字符串的删除操作 思路:直接记录需要改(增或删)几个,也就是求不…...
使用WAF防御网络上的隐蔽威胁之目录穿越
目录穿越(Directory Traversal)是一种网络安全攻击手段,也被称为路径穿越。 这种攻击允许攻击者访问存储在Web服务器文件系统上的文件和目录,这些文件和目录原本不应该对用户可见或可访问。 通过利用安全漏洞,攻击者…...
Linux:vim的相关知识
目录 vim 是一个较为常见的编译文件的命令操作。 三种模式的区分的作用如下: 命令模式: 插入模式: 进入插入模式的标志:左下角有INSERT 底行模式: 命令模式的常见命令: 底行模式常见命令࿱…...
Qt 国产嵌入式操作系统实现文字转语音功能(ekho库)
1.简介 Qt 国产嵌入式操作系统实现文字转语音功能(TTS)_tts驱动 转文字-CSDN博客 在继上篇文章之后,甲方粑粑不满意使用eSpeak发出的声音太难听了,这就不得不找个替代品,声音稍微好听了一些。 使用ekho开源库。 Ekho(余音)是一个免费、开源的中文语音合成软件。它目…...
Redis常见类型及常用命令
目录 常见的数据类型 一、String类型 1、简介 2、常用命令 (1)新建key (2)设值取值 编辑 (3)批量操作 (4)递增递减 3、原子性操作 4、数据结构 二、list类型 1、list常…...
实战纪实 | 某配送平台zabbix 未授权访问 + 弱口令
本文由掌控安全学院 - 17828147368 投稿 找到一个某src的子站,通过信息收集插件wappalyzer,发现ZABBIX-监控系统: 使用谷歌搜索历史漏洞:zabbix漏洞 通过目录扫描扫描到后台,谷歌搜索一下有没有默认弱口令 成功进去了…...
【第十五课】数据结构:堆 (“堆”的介绍+主要操作 / acwing-838堆排序 / c++代码 )
目录 关于堆的一些知识的回顾 数据结构:堆的特点 "down" 和 "up":维护堆的性质 down up 数据结构:堆的主要操作 acwing-838堆排序 代码如下 时间复杂度分析 确实是在写的过程中频繁回顾了很多关于树的知识&…...
前端JavaScript篇之JavaScript有哪些数据类型,它们的区别?
目录 JavaScript有哪些数据类型,它们的区别?数据类型区别 JavaScript有哪些数据类型,它们的区别? 数据类型 JavaScript数据类型有: Undefined、Null、Boolean、Number、String、Array、Object、Symbol、BigInt… St…...
LeetCode---380周赛
题目列表 3005. 最大频率元素计数 3006. 找出数组中的美丽下标 I 3007. 价值和小于等于 K 的最大数字 3008. 找出数组中的美丽下标 II 一、最大频率元素计数 这题就是个简单的计数题,正常遍历统计数据即可,关键是你要会写代码逻辑。 代码如下&…...
archlinux 如何解决安装以后没有声音的问题
今天安装完archlinux以后发现看视频没声音 检查一下是否有 /lib/firmware/intel/sof 发现没有 如果你也是这样的话,可以尝试安装: sudo pacman -S sof-firmware 重启后再看看有没有声音: reboot 反正我有声音了...
什么是ORM思想?
1. ORM概念 ORM(Object Relational Mapping)对象关系映射模式,是一种技术,解决了面向对象与关系型数据库存互不匹配的现象。 ORM在业务逻辑层和数据库层之间充当了桥梁的作用。 2. ORM由来 在软件开发的过程中,通常…...
设计接口时,为其添加签名鉴权---详细教程
一、何为签名 我们知道无论是restful api还是传统接口、亦或是其他形式接口的调用,接口签名都是非常重要的安全机制,它可以确保请求的发起者是经过认证和授权的客户端,同时也可以防止接口被攻击,请求参数被篡改等等。 用大白话来解…...
5G+物联网:连接万物,重塑智慧社区,开启未来生活新纪元,助力智慧社区的革新与发展
一、5G与物联网:技术概述与基础 随着科技的飞速发展,第五代移动通信技术(5G)和物联网(IoT)已经成为当今社会的热门话题。这两项技术作为现代信息社会的核心基础设施,正深刻地改变着人们的生活和…...
[反转链表] [合并两个有序链表][分割链表]
这里写目录标题 反转链表合并两个有序链表分割链表 反转链表 1、题目: 2.思路 思路1:建立一个newHead,取一个节点进行头插。具体做法如下! 建立一个newHead(新头),由于一个节点里面存的是下一个节点的地址,如果取…...
中文数据让LLM变笨?
我这里先贴一下论文的原链接: https://arxiv.org/abs/2401.10286 然后贴一下我翻译标注的下载链接:https://gitee.com/chatpaper/arXiv_top_chinese/blob/master/0801_top/%E4%B8%AD%E6%96%87%E4%BC%9A%E8%AE%A9LLM%E5%8F%98%E7%AC%A8%EF%BC%9F.pdf 先…...
【代码随想录】刷题笔记Day54
前言 差单调栈就结束代码随想录一刷啦,回家二刷打算改用python补充进博客,小涛加油!!! 647. 回文子串 - 力扣(LeetCode) 双指针法 中心点外扩,注意中心点可能有一个元素可能有两个…...
二.Winform使用Webview2在Demo1中实现地址简单校验
Winform使用Webview2在Demo1中实现地址简单校验 往期目录回顾添加对于的简单url验证提示通过上节和本节涉及到的函数有 往期目录 往期相关文章目录 专栏目录 回顾 通过一.Winform使用Webview2(Edge浏览器核心) 创建demo(Demo1)实现回车导航到指定地址 我们已经知道了解决资源…...
从0开始学习C++ 第二十课:模板与泛型编程
第二十课:模板与泛型编程 学习目标: 掌握模板的基本语法和概念。学会使用函数模板来创建可重用的函数。学习如何定义类模板以实现数据结构的泛型。理解模板在C中提供的灵活性和强大功能。 学习内容: 模板的概念: 模板是C中支持…...
pcl之滤波器(一)
pcl滤波器 pcl一共是有十二个主要模块,详细了解可以查看官网。https://pcl.readthedocs.io/projects/tutorials/en/latest/#basic-usage 今天学习一下pcl的滤波器模块。 滤波器模块,官网一共是提供了6个例程,今天先来看第一第二个。 直通…...
java项目性能优化(MyBatis中开启查询缓存及flushCache与useCache的使用)
在java项目中,如果需要大量的DB查询,导致缓存过多,项目运行缓慢,可以设置在select查询时,添加二级缓存的清空。 如果没有去配置flushCache、useCache,那么默认是启用缓存的。 1,flushCache默认…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
