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

代码随想录打卡—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】感觉和下面这题很像。就是一模一样&#xff0c;return变一下就是。 1143. 最长公共子序列 【注意点2】注意这题和day55的最后一题的区别&#xff0c;本题求的是最大长度&#xff0c;那题求的是组合方式。…...

uni-app app端.m3u8类型流的播放

1.开发环境&#xff1a;HBuilderX3.8.7、uni-app、vue2.0、view2.0、uni-ui 2.实现通过web-view 嵌入H5页面&#xff0c;进行视频流自动播放。 注意事项&#xff1a; 如果只是在android端可以直接使用.flv格式的视频流&#xff1b; 如果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口扩展

在工控板设计中&#xff0c;经常会遇到扩展IO。具有相同的功能电路板接口相同&#xff0c;所以很容易采用排线方式连接到CPU主控板上&#xff0c;这种排线连接&#xff0c;我称之为总线。 现在的CPU引脚多&#xff0c;不扩展IO&#xff0c;使用模拟SPI&#xff0c;也可以实现&…...

【jsthree.js】全景vr看房进阶版

three小结&#xff1a; Scene场景 指包含了所有要渲染和呈现的三维对象、光源、相机以及其他相关元素的环境&#xff1b;场景可以被渲染引擎或图形库加载和处理&#xff0c;以生成最终的图像或动画 常见属性&#xff1a; scene.background new THREE.Color(0x000000); // …...

实战:基于卷积的MNIST手写体分类

前面实现了基于多层感知机的MNIST手写体识别&#xff0c;本章将实现以卷积神经网络完成的MNIST手写体识别。 1. 数据的准备 在本例中&#xff0c;依旧使用MNIST数据集&#xff0c;对这个数据集的数据和标签介绍&#xff0c;前面的章节已详细说明过了&#xff0c;相对于前面章…...

Ubuntu开启生成Core Dump的方法

C 文章目录 C1. 首先ulimit通过查看2. 执行下面的命令 Ubuntu下无法生成Core Dump解决方法 1. 首先ulimit通过查看 ulimit -a查看是core file size是否为0&#xff0c;若为0&#xff0c;通过以下方式设置size ulimit -c 1024或者 ulimit -c unlimited //size没有限制2. 执行…...

git视频教程Jenkins持续集成视频教程Git Gitlab Sonar教程

[TOC这里写自定义目录标题) https://edu.51cto.com/lesson/290903.html 欢迎使用Markdown编辑器 你好&#xff01; 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章&#xff0c;了解一下Markdown的基本语法知识。…...

机器学习:Xgboost

Xgboost XGBoost&#xff08;eXtreme Gradient Boosting&#xff09;是一种机器学习算法&#xff0c;是梯度提升决策树&#xff08;Gradient Boosting Decision Trees&#xff09;的一种优化实现。它是由陈天奇在2014年开发并推出的。XGBoost是一种强大而高效的算法&#xff0…...

《Kubernetes部署篇:Ubuntu20.04基于二进制安装安装cri-containerd-cni》

一、背景 由于客户网络处于专网环境下&#xff0c; 使用kubeadm工具安装K8S集群&#xff0c;由于无法连通互联网&#xff0c;所有无法使用apt工具安装kubeadm、kubelet、kubectl&#xff0c;当然你也可以使用apt-get工具在一台能够连通互联网环境的服务器上下载cri-tools、cont…...

[CISCN 2019初赛]Love Math

文章目录 前言考点解题过程 前言 感慨自己实力不够&#xff0c;心浮气躁根本做不来难题。难得这题对我还很有吸引力&#xff0c;也涉及很多知识。只能说我是受益匪浅&#xff0c;总的来说加油吧ctfer。 考点 利用php动态函数的特性利用php中的数学函数实现命令执行利用php7的特…...

运行命令出现错误 /bin/bash^M: bad interpreter: No such file or directory

在系统上运行一个 Linux 的命令的时候出现下面的错误信息&#xff1a; -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&#xff08;免费使用授权&…...

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可以协助人们提高公共服务和社区建设能力。公共服务是一个广泛的领域&#xff0c;包括教育、医疗、城市规划、紧急救援、环境保护等多个方面。ChatGPT作为一种人工智能工具&#xff0c;具有巨大的潜力&#xff0c;可以在各个领域提供支持和增强决策制定、信息获取、沟通…...

机器人中的数值优化(七)——修正阻尼牛顿法

本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考&#xff0c;主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等&#xff0c;本系列文章篇数较多&#xff0c;不定期更新&#xff0c;上半部分介绍无约束优化&#xff0c;…...

程序员自由创业周记#3:No1.作品

作息 如果不是热爱&#xff0c;很难解释为什么能早上6点自然醒后坐在电脑前除了吃饭一直敲代码到23点这个现象&#xff0c;而且还乐此不疲。 之前上班的时候生活就很规律&#xff0c;没想到失业后的生活比之前还要规律&#xff1b;记得还在上班的时候&#xff0c;每天7点半懒洋…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...