代码随想录打卡—day56—【编辑距离】— 9.2 编辑距离系列
1 583. 两个字符串的删除操作
583. 两个字符串的删除操作
【注意点1】感觉和下面这题很像。就是一模一样,return变一下就是。
1143. 最长公共子序列
【注意点2】注意这题和day55的最后一题的区别,本题求的是最大长度,那题求的是组合方式。
AC代码:
class Solution {
public:int dp[510][510]; // word1的前i-1的字符串 与 word2的前i-1的字符串的最长公共子序列长度/*if(word1[i-1] == word2[j-1])dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = max(dp[i][j-1],dp[i-1][j]);dp[0][0] = 0dp[i][0] = 0dp[0][j] = 0i++ j++模拟——*/int minDistance(string word1, string word2) {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;elsedp[i][j] = max(dp[i][j-1],dp[i-1][j]);}}return word1.size() + word2.size() - 2*dp[word1.size()][word2.size()];}
};
2 72. 编辑距离
72. 编辑距离
状态转移方程难推导。学习题解的,详见注释
AC代码:
class Solution {
public:int dp[510][510]; // word1的前i-1个的子串 转换成 word2的前j-1个的子串最小操作数/*if(word1[i-1] == word2[j-1]){dp[i][j] = dp[i-1][j-1]; //不用操作}else{//【1】 插入按照题解的说法 一个子串删除最后一个元素 等价于 另一个子串增加最后一个元素所以省去// 【2】 删除删掉word1[i-1]dp[i][j] = dp[i-1][j] + 1;删掉word2[j-1]dp[i][j] = dp[i][j-1] + 1;// 【3】 替换dp[i][j] = dp[i-1][j-1] + 1;}初始化:dp[0][0] = 0;dp[0][j] = j;dp[i][0] = i;顺序:i++ j++模拟:*/int minDistance(string word1, string word2) {for(int j = 0; j <= word2.size();j++)dp[0][j] = j;for(int i = 0; i <= word1.size();i++)dp[i][0] = i;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]; //不用操作elsedp[i][j] = min(dp[i-1][j],min(dp[i][j-1] , dp[i-1][j-1])) + 1;return dp[word1.size()][word2.size()];}
};
编辑距离系列总结
go to
相关文章:
代码随想录打卡—day56—【编辑距离】— 9.2 编辑距离系列
1 583. 两个字符串的删除操作 583. 两个字符串的删除操作 【注意点1】感觉和下面这题很像。就是一模一样,return变一下就是。 1143. 最长公共子序列 【注意点2】注意这题和day55的最后一题的区别,本题求的是最大长度,那题求的是组合方式。…...
uni-app app端.m3u8类型流的播放
1.开发环境:HBuilderX3.8.7、uni-app、vue2.0、view2.0、uni-ui 2.实现通过web-view 嵌入H5页面,进行视频流自动播放。 注意事项: 如果只是在android端可以直接使用.flv格式的视频流; 如果App需要支持ios就可以考虑一下播放.m3u8格…...
使用proxy_pool来为爬虫程序自动更换代理IP | 开源IP代理
1. 前言 之前做爬虫的时候,经常会遇到对于一个网页,使用同一个IP多次会被禁掉IP的问题,我们可以自己手动更换代理IP再继续这个问题但多少会有点麻烦,我对于一个懒人来说,手动更换IP太麻烦,而且也不符合程序员懒惰的美德,于是便有了下面的故事。proxy_pool 是一个开源的代…...
【易售小程序项目】修改“我的”界面前端实现;查看、重新编辑、下架自己发布的商品【后端基于若依管理系统开发】
文章目录 “我的”界面修改效果界面实现界面整体代码 查看已发布商品界面效果商品数据表后端上架、下架商品ControllerMapper 界面整体代码back方法 编辑商品、商品发布、保存草稿后端商品校验方法Controller 页面整体代码 “我的”界面修改 效果 界面实现 界面的实现使用了一…...
Centos7 + Apache Ranger 2.4.0 部署
一、Ranger简介 Apache Ranger提供一个集中式安全管理框架, 并解决授权和审计。它可以对Hadoop生态的组件如HDFS、Yarn、Hive、Hbase等进行细粒度的数据访问控制。通过操作Ranger控制台,管理员可以轻松的通过配置策略来控制用户访问权限。 1、组件列表 # Service Name Liste…...
硬件SPI口扩展
在工控板设计中,经常会遇到扩展IO。具有相同的功能电路板接口相同,所以很容易采用排线方式连接到CPU主控板上,这种排线连接,我称之为总线。 现在的CPU引脚多,不扩展IO,使用模拟SPI,也可以实现&…...
【jsthree.js】全景vr看房进阶版
three小结: Scene场景 指包含了所有要渲染和呈现的三维对象、光源、相机以及其他相关元素的环境;场景可以被渲染引擎或图形库加载和处理,以生成最终的图像或动画 常见属性: scene.background new THREE.Color(0x000000); // …...
实战:基于卷积的MNIST手写体分类
前面实现了基于多层感知机的MNIST手写体识别,本章将实现以卷积神经网络完成的MNIST手写体识别。 1. 数据的准备 在本例中,依旧使用MNIST数据集,对这个数据集的数据和标签介绍,前面的章节已详细说明过了,相对于前面章…...
Ubuntu开启生成Core Dump的方法
C 文章目录 C1. 首先ulimit通过查看2. 执行下面的命令 Ubuntu下无法生成Core Dump解决方法 1. 首先ulimit通过查看 ulimit -a查看是core file size是否为0,若为0,通过以下方式设置size ulimit -c 1024或者 ulimit -c unlimited //size没有限制2. 执行…...
git视频教程Jenkins持续集成视频教程Git Gitlab Sonar教程
[TOC这里写自定义目录标题) https://edu.51cto.com/lesson/290903.html 欢迎使用Markdown编辑器 你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本语法知识。…...
机器学习:Xgboost
Xgboost XGBoost(eXtreme Gradient Boosting)是一种机器学习算法,是梯度提升决策树(Gradient Boosting Decision Trees)的一种优化实现。它是由陈天奇在2014年开发并推出的。XGBoost是一种强大而高效的算法࿰…...
《Kubernetes部署篇:Ubuntu20.04基于二进制安装安装cri-containerd-cni》
一、背景 由于客户网络处于专网环境下, 使用kubeadm工具安装K8S集群,由于无法连通互联网,所有无法使用apt工具安装kubeadm、kubelet、kubectl,当然你也可以使用apt-get工具在一台能够连通互联网环境的服务器上下载cri-tools、cont…...
[CISCN 2019初赛]Love Math
文章目录 前言考点解题过程 前言 感慨自己实力不够,心浮气躁根本做不来难题。难得这题对我还很有吸引力,也涉及很多知识。只能说我是受益匪浅,总的来说加油吧ctfer。 考点 利用php动态函数的特性利用php中的数学函数实现命令执行利用php7的特…...
运行命令出现错误 /bin/bash^M: bad interpreter: No such file or directory
在系统上运行一个 Linux 的命令的时候出现下面的错误信息: -bash: ./build.sh: /bin/bash^M: bad interpreter: No such file or directory 这个是在 Windows 作为 WSL 的时候出的错误。 原因和解决 出现问题的原因在于脚本在 Windows 中使用的回车换行和 Linux …...
码农重装系统后需要安装的软件
文章目录 前言1 编程软件1.1 IntelliJ IDEA1.2 Eclipse1.3 VSCode 2 Java 开发环境3 测试运维工具3.1 Docker3.2 VirtualBox3.2.1 windows3.2.2 centos 7 83.2.3 Alma Linux3.2.4 Rocky Linux3.2.5 ubuntu server3.2.6 统信 UOS 服务器操作系统V20(免费使用授权&…...
Kotlin return 和 loop jump
再聊 return 在上一篇文章《Kotlin inline、noinline、crossinline 深入解析》 我们介绍到,在 lambda 中不能使用 return,除非该函数是 inline 的。如果该高阶函数是 inline ,调用该函数时,在传入的 lambda 中使用 return,则 return 的是离它最近的 enclosing function,…...
计算一组数据中的低中位数即如果一组数据中有两个中位数则较小的那个为低中位数statistics.median_low()
【小白从小学Python、C、Java】 【计算机等考500强证书考研】 【Python-数据分析】 计算一组数据中的低中位数 即如果一组数据中有两个中位数 则较小的那个为低中位数 statistics.median_low() 选择题 以下程序的运行结果是? import statistics data_1[1,2,3,4,5] data_2[1,2,…...
ChatGPT是否能够协助人们提高公共服务和社区建设能力?
ChatGPT可以协助人们提高公共服务和社区建设能力。公共服务是一个广泛的领域,包括教育、医疗、城市规划、紧急救援、环境保护等多个方面。ChatGPT作为一种人工智能工具,具有巨大的潜力,可以在各个领域提供支持和增强决策制定、信息获取、沟通…...
机器人中的数值优化(七)——修正阻尼牛顿法
本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考,主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等,本系列文章篇数较多,不定期更新,上半部分介绍无约束优化,…...
程序员自由创业周记#3:No1.作品
作息 如果不是热爱,很难解释为什么能早上6点自然醒后坐在电脑前除了吃饭一直敲代码到23点这个现象,而且还乐此不疲。 之前上班的时候生活就很规律,没想到失业后的生活比之前还要规律;记得还在上班的时候,每天7点半懒洋…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
Python竞赛环境搭建全攻略
Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型(算法、数据分析、机器学习等)不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...
