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

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...