day-56 代码随想录算法训练营(19)动态规划 part 16
538.两个字符串的删除操作
思路一:
- 1.dp存储:以word1[i-1]结尾,word2[j-1]结尾,最少进行dp[i][j]次操作
- 2.动态转移方程: if(word1[i-1]==word2[i-1]) dp[i][j]=dp[i-1][j-1];
- else dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1)
- 3.初始化:dp[i][0]=i dp[0][j]=j
- 4.遍历顺序:1~尾巴
class Solution {
public:int minDistance(string word1, string word2) {int n=word1.size(),m=word2.size();vector<vector<int>>dp(n+1,vector<int>(m+1,0));for(int i=0;i<=n;i++) dp[i][0]=i;//相同时需要删除所有字符串for(int j=0;j<=m;j++) dp[0][j]=j;for(int i=1;i<=n;i++){for(int j=1;j<=m;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[n][m];}
};
72.编辑距离
思路:
- 1.dp存储:以word1[i]结尾,word2[j]结尾,使两个字符串相同的最小操作次数
- 2.动态转移方程: 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)
- 3.初始化:dp[i][0]=i dp[0][j]=j
- 4.遍历顺序:1~n 1~m
class Solution {
public:int minDistance(string word1, string word2) {int n=word1.size(),m=word2.size();vector<vector<int>>dp(n+1,vector<int>(m+1,0));for(int i=0;i<=n;i++) dp[i][0]=i;for(int j=0;j<=m;j++) dp[0][j]=j;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//添加和删除都是一样的,两边各添加和删除;改变就是上一次的值+1if(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[n][m];}
};
相关文章:
day-56 代码随想录算法训练营(19)动态规划 part 16
538.两个字符串的删除操作 思路一: 1.dp存储:以word1[i-1]结尾,word2[j-1]结尾,最少进行dp[i][j]次操作2.动态转移方程: if(word1[i-1]word2[i-1]) dp[i][j]dp[i-1][j-1]; else dp[i][j]min(dp[i-1][…...
蓝桥等考Python组别四级005
第一部分:选择题 1、Python L4 (15分) 字符“0”的ASCII码值为48,则字符“5”的ASCII码值为( )。 3953120240正确答案:B 2、Python L4 (15分) 下面哪个是Python中正确的变量名?( ) ABC#sup01Trueif正确答案:B...
【Linux】diff 命令
【Linux】diff 命令——并排格式输出 功能 diff 以逐行的方式,比较文本文件的异同处。 如果指定要比较目录,则 diff 会比较目录中相同文件名的文件,但不会比较其中子目录 diff [参数] [文件A] [文件B]diff [参数] [目录A] [目录B]【参数】…...
【51单片机】9-定时器和计数器
1.定时器的介绍 1.什么是定时器 (1)SoC的一种内部的外设【在单片机里面,但是在CPU外面】 (2)定时器就是CPU的”闹钟“ 2.什么是计数器 (1)定时器就是用计数的原始实现的 (2…...
2023年海南省职业院校技能大赛(高职组)信息安全管理与评估赛项规程
2023年海南省职业院校技能大赛(高职组) 信息安全管理与评估赛项规程 一、赛项名称 赛项名称:信息安全管理与评估 英文名称:Information Security Management and Evaluation 赛项组别:高等职业教育 赛项归属产业&…...
大模型深挖数据要素价值:算法、算力之后,存储载体价值凸显
文 | 智能相对论 作者 | 叶远风 18.8万亿美元,这是市场预计2030年AI推动智能经济可产生的价值总和,其中大模型带来的AI能力质变无疑成为重要的推动力量。 大模型浪潮下,业界对AI发展的三驾马车——算力、算法、数据任何一个维度的关注都到…...
AI文章,AI文章生成工具
在互联网时代,随着信息爆炸式增长,文章的需求愈发旺盛。从博客、新闻、社交媒体到企业宣传,文字作为传达信息、吸引受众的工具变得愈发重要。但问题是,对于很多人来说,创作一篇高质量的文章并不容易。时间、创意、写作…...
mac有必要用清理软件吗?有哪些免费的清理工具
当我们谈到Mac电脑时,很多人都会觉得它比Windows系统更加稳定和高效,也更不容易积累垃圾文件。但实际上,任何长时间使用的操作系统都会逐渐积累不必要的文件和缓存。那么,对于Mac用户来说,有必要使用专门的清理软件吗&…...
React 全栈体系(十八)
第九章 React Router 6 二、代码实战 6. 路由的 params 参数 6.1 routes /* src/routes/index.js */ import About from "../pages/About"; import Home from "../pages/Home"; import Message from "../pages/Message"; import News from &q…...
TCP/UDP
TCP:可靠的有序传输 TCP是一种面向连接的协议,旨在提供可靠、有序的数据传输。它通过以下方式实现这一目标: 1. 连接建立和维护 在使用TCP传输数据之前,必须先建立连接。这个过程包括三次握手,即客户端和服务器之间…...
c++内存对齐
原文在这里。https://blog.csdn.net/WangErice/article/details/103598081 但是内容有错误。我在自己的这里修改并变成红色了。 内存在使用过程并不是单一的依次排列,而是按照某种既定的规则来进行对齐,以方便快速访问.内存的对齐原则有以下三条&#…...
leetcode 33. 搜索旋转排序数组
2023.9.26 本题暴力法可以直接A,但是题目要求用log n的解法。 可以想到二分法,但是一般二分法适用于有序数组的,这里的数组只是部分有序,还能用二分法吗? 答案是可以的。因为数组是经过有序数组旋转得来的,…...
VCS flow学习
VCS VCS 是IC从业者常用软件,该篇文章是一个学习记录,会记录在使用过程中各种概念及options。 VCS Flow VCS Flow 可以分为Two-step Flow和Three-step Flow两类。 两步法 两步法只支持Verilog HDL和SystemVerilog的design,两步法主要包括…...
微信扫码关注公众号登录功能php实战分享
1、安装easywechat 基于easywechat框架开发,首先下载安装easywechat composer require overtrue/wechat 2、公众号配置 先去公众号后台基本配置/ 填写服务器配置配置接口,需要是线上能正确收到微信推送消息的地址,关注如果有关注、扫码、收到消息等事件都会推送到该地址…...
Git 精简快速使用
安装 Git 忽略,自行搜索 新建项目,或者在仓库拉取项目,进入到项目目录 Github 给出的引导,新项目和旧项目 echo "# testgit" >> README.md git init git add README.md git commit -m "first commit"…...
线性约束最小方差准则(LCMV)波束形成算法仿真
常规波束形成仅能使得主波束对准目标方向,从而在噪声环境下检测到目标,但无法对复杂多变的干扰做出响应,所以不能称之为真正意义上的自适应滤波。自适应阵列处理指的是采用自适应算法对空间阵列接收的混合信号进行处理,又可称为自…...
什么是内容运营?
关于内容运营,在不同种类的公司,侧重点也不一样。 电商平台的内容运营岗更偏内容营销;产品功能比较简单的公司,内容运营和新媒体运营的岗位职责差不多;而内容平台的内容运营更多的是做内容的管理和资源整合。...
搭建安信可小安派Windows 开发环境
搭建小安派Windows 开发环境 Ai-Pi-Eyes 系列是安信可开源团队专门为Ai-M61-32S设计的开发板,支持WiFi6、BLE5.3。所搭载的Ai-M61-32S 模组具有丰富的外设接口,具体包括 DVP、MJPEG、Dispaly、AudioCodec、USB2.0、SDU、以太网 (EMAC)、SD/MMC(SDH)、SP…...
XML文件反序列化读取
原始XML文件 <?xml version"1.0" encoding"utf-8" ?> <School headmaster"王校长"><Grade grade"12" teacher"张老师"><Student name"小米" age"18"/><Student name&quo…...
会议剪影 | 思腾合力受邀参加2023第二届世界元宇宙大会并作主题演讲
由中国仿真学会、中国指挥与控制学会和北京理工大学共同主办,上海市嘉定区安亭镇人民政府和中国仿真学会元宇宙专业委员会承办的第二届世界元宇宙大会于2023年9月20日-22日在上海安亭举行。 大会以“虚实相生、产业赋能”为主题,聚焦元宇宙关键技术发展的…...
使用 C++ 模拟 ShaderLanguage 的 swizzle
经常编写着色器的同学应该对 swizzle(重排)语法非常熟悉,方便又灵活,可以说是用过一次便回味无穷。 代码 vec4 color vec4(1.0, 0.5, 0.0, 1.0); vec3 rgb color.rgb; // { 1.0, 0.5, 0.0 } vec2 xy color.xy; …...
收藏!阿里放大招成立ATH事业群,AI月薪6W+,小白/程序员入局正当时
近日,据行业网友爆料,阿里近期迎来AI领域重大动作——正式组建Alibaba Token Hub(简称ATH)事业群,由集团CEO吴某铭亲自挂帅带队,其核心战略目标十分明确,浓缩为一句话就是:创造Token…...
反激式电源设计避坑指南:如何优化5V/2A方案的EMI和效率
反激式电源设计避坑指南:如何优化5V/2A方案的EMI和效率 在中小功率电源设计中,反激式拓扑凭借结构简单、成本低廉的优势占据主流地位。但当工程师面对5V/2A这类常见规格时,往往会陷入效率卡在65%难以提升、EMI测试屡次失败的困境。本文将从实…...
PDF文本高效提取:用pdftotext实现秒级文档内容解析
PDF文本高效提取:用pdftotext实现秒级文档内容解析 【免费下载链接】pdftotext Simple PDF text extraction 项目地址: https://gitcode.com/gh_mirrors/pd/pdftotext 破解PDF提取痛点:为什么你需要专业工具? 每天面对数十份PDF文档却…...
Codesys电子凸轮Cam表两种设置方法对比:可视化拖拽 vs 程序动态配置
Codesys电子凸轮Cam表设置方法深度对比:可视化拖拽与程序动态配置实战解析 在工业自动化领域,电子凸轮技术正逐步取代传统机械凸轮,成为运动控制系统的核心组件。作为Codesys平台下的重要功能,Cam表的设置方法直接关系到运动轨迹…...
Fish Speech 1.5开源大模型落地:为乡村学校定制方言普通话双语教学语音
Fish Speech 1.5开源大模型落地:为乡村学校定制方言普通话双语教学语音 想象一下,在偏远山区的教室里,孩子们正跟着一个亲切的“本地老师”学习普通话。这位老师不仅能说一口标准的普通话,还能用孩子们熟悉的家乡方言进行解释和互…...
出国旅行手机没信号?Nrfr免Root工具一键解锁全球网络
出国旅行手机没信号?Nrfr免Root工具一键解锁全球网络 【免费下载链接】Nrfr 🌍 免 Root 的 SIM 卡国家码修改工具 | 解决国际漫游时的兼容性问题,帮助使用海外 SIM 卡获得更好的本地化体验,解锁运营商限制,突破区域限制…...
实时手机检测-通用实战案例:手机质检报告自动生成系统集成方案
实时手机检测-通用实战案例:手机质检报告自动生成系统集成方案 1. 引言:从人工质检到智能报告的跨越 想象一下,在一个大型手机生产线上,质检员每天需要手动检查成千上万张手机外观照片,寻找划痕、污渍、装配瑕疵。这…...
PicView图片浏览器完整指南:从零开始掌握高效图片管理技巧
PicView图片浏览器完整指南:从零开始掌握高效图片管理技巧 【免费下载链接】PicView Fast, free and customizable image viewer for Windows 10 and 11. 项目地址: https://gitcode.com/gh_mirrors/pi/PicView PicView是一款专为Windows 10和11设计的快速、…...
cv_unet_image-colorization高保真上色案例:人脸肤色/服饰纹理自然还原实录
cv_unet_image-colorization高保真上色案例:人脸肤色/服饰纹理自然还原实录 你有没有翻看过家里的老相册?那些泛黄的黑白照片,记录着珍贵的瞬间,却总让人觉得少了点什么。色彩,是记忆的温度。过去,为黑白照…...
