当前位置: 首页 > 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点半懒洋…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

云原生周刊:k0s 成为 CNCF 沙箱项目

开源项目推荐 HAMi HAMi&#xff08;原名 k8s‑vGPU‑scheduler&#xff09;是一款 CNCF Sandbox 级别的开源 K8s 中间件&#xff0c;通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度&#xff0c;为容器提供统一接口&#xff0c;实现细粒度资源配额…...