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

leetcode 712. Minimum ASCII Delete Sum for Two Strings(字符串删除字母的ASCII码之和)

在这里插入图片描述

两个字符串s1, s2, 删除其中的字母使s1和s2相等。
问删除字母的最小ASCII码之和是多少。

思路:

DP

先考虑极端的情况,s1为空,那么要想达到s2和s1相等,就要把s2中的字母删完,
ASCII码之和就是s2中所有字母的ASCII码之和。
同理s2为空的情况。

现在来遍历s1和s2, s1的下标记为 i , s2的下标记为 j.
记dp[ i ][ j ]表示s1, s2分别遍历到i, j时删除字母的ASCII码之和。

如果s1[ i ] == s2[ j ], 字母相等,不需要删除,那么状态保持在前一状态,
也就是dp[ i ][ j ] = dp[i-1][j-1].

如果字母不相等,要么删除s1[ i ], 要么删除s2[ j ].
删除s1[ i ]的ASCII码: dp[i-1][ j ] + s1[ i ]
删除s2[ j ]的ASCII码: dp[i][ j+1 ] + s2[ j ]
取两者中较小的一个给dp[ i ][ j ]

最后返回dp[s1.length][s2.length]

    public int minimumDeleteSum(String s1, String s2) {char[] chs1 = s1.toCharArray();  //计算更快char[] chs2 = s2.toCharArray();int n1 = chs1.length;int n2 = chs2.length;int[][] dp = new int[n1+1][n2+1];//注意下面的i,j是遍历到的字符串长度,下标需要-1//s2长度为0时,s1达到长度为0需要删除字母的ASCII码之和for(int i = 1; i <= n1; i++) dp[i][0] = dp[i-1][0]+chs1[i-1];//s1长度为0时,s2达到长度为0需要删除字母的ASCII码之和for(int i = 1; i <= n2; i++) dp[0][i] = dp[0][i-1] + chs2[i-1];for(int i = 1; i <= n1; i++) {for(int j = 1; j <= n2; j++) {if(chs1[i-1] == chs2[j-1]) { //字符相等,不需要删除字母,保持前一状态dp[i][j] = dp[i-1][j-1];} else {//删除s1的一个字母或者删除s2的一个字母,取较小dp[i][j] = Math.min(dp[i-1][j]+chs1[i-1], dp[i][j-1]+chs2[j-1]); }}}return dp[n1][n2];}

相关文章:

leetcode 712. Minimum ASCII Delete Sum for Two Strings(字符串删除字母的ASCII码之和)

两个字符串s1, s2, 删除其中的字母使s1和s2相等。 问删除字母的最小ASCII码之和是多少。 思路&#xff1a; DP 先考虑极端的情况&#xff0c;s1为空&#xff0c;那么要想达到s2和s1相等&#xff0c;就要把s2中的字母删完&#xff0c; ASCII码之和就是s2中所有字母的ASCII码之…...

Springboot -- 按照模板生成docx、pdf文件,docx转pdf格式

使用 poi-tl 根据模板生成 word 文件。 使用 xdocreport 将 docx 文件转换为 pdf 文件。 xdocreport 也支持根据模板导出 word &#xff0c;但是 poi-tl 的功能更齐全&#xff0c;操作更简单&#xff0c;文档清晰。 poi-tl 、xdocreport 内部均依赖了 poi &#xff0c;要注意两…...

UE5.1.1 创建C++项目失败

因一直使用Unity开发环境&#xff0c;安装Unreal后&#xff0c;并未详细配置过其开发环境&#xff0c;默认创建蓝图工程无异常&#xff0c;但创建UE C项目时总共遇到两个错误&#xff1a; 错误一 Running /Epic/UE/UE_5.1/Engine/Build/BatchFiles/Build.bat -projectfiles -…...

windows进行端口映射

windows进行端口映射 1. 查询端口映射情况 netsh interface portproxy show v4tov42. 查询某一个IP的所有端口映射情况 netsh interface portproxy show v4tov4 | find "[IP]" # 例&#xff1a; netsh interface portproxy show v4tov4 | find "192.168.1.1&quo…...

Python 异常处理

Python 异常处理 python提供了两个非常重要的功能来处理python程序在运行中出现的异常和错误。你可以使用该功能来调试python程序。 异常处理: 本站Python教程会具体介绍。断言(Assertions):本站Python教程会具体介绍。 python标准异常 异常名称描述BaseException所有异常的…...

C++ 类的静态成员

在结构化程序设计中程序模块的基本单位是函数&#xff0c;因此模块间对内存中数据的共享是通过函数与和函数之间的数据共享来实现的&#xff0c;其中包括两个途径——参数传递和全局变量。 面向对象的程序设计方法兼顾数据的共享和保护&#xff0c;将数据与操作数据的函数封装…...

360T7路由器进行WiFi无线中继教程

360T7路由器进行WiFi中继教程 1. 概述2. 360T7路由器进行WiFi中继实现教程2.1 登录路由器管理界面2.2 选择上网方式2.3 搜索WiFi2.4 连接WiFi2.5 点击确认2.6 在主页面查看网络 1. 概述 中继路由系统由一组中继路由器组成&#xff0c;为不能交换路由信息的路由域提供中继路由。…...

主成分分析

主成分分析 相关概念方差协方差协方差矩阵特征值和特征向量 主成分分析数据降维主成分分析原理主成分分析过程sklearn库中的PCA主成分分析实现案例 相关概念 方差 方差是一个用来衡量一组数据离散程度的统计量&#xff0c;它是各样本与样本均值的差的平方和的平均值。方差越大…...

笙默考试管理系统-MyExamTest(26)

笙默考试管理系统-MyExamTest&#xff08;26&#xff09; 目录 一、 笙默考试管理系统-MyExamTest 二、 笙默考试管理系统-MyExamTest 三、 笙默考试管理系统-MyExamTest 四、 笙默考试管理系统-MyExamTest 五、 笙默考试管理系统-MyExamTest 笙默考试管理系统-MyEx…...

重新理解 RocketMQ Commit Log 存储协议

最近突然感觉&#xff1a;很多软件、硬件在设计上是有 root reason 的&#xff0c;不是 by desgin 如此&#xff0c;而是解决了那时、那个场景的那个需求。一旦了解后&#xff0c;就会感觉在和设计者对话&#xff0c;了解他们的思路&#xff0c;学习他们的方法&#xff0c;思维…...

ES6基础知识十:你是怎么理解ES6中 Decorator 的?使用场景?

一、介绍 Decorator&#xff0c;即装饰器&#xff0c;从名字上很容易让我们联想到装饰者模式 简单来讲&#xff0c;装饰者模式就是一种在不改变原类和使用继承的情况下&#xff0c;动态地扩展对象功能的设计理论。 ES6中Decorator功能亦如此&#xff0c;其本质也不是什么高大…...

接口/Web自动化测试如何做?框架如何搭建封装?

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 自动化测试怎么做…...

Linux怎么从网络上下载文件

wget命令用于从网络上下载文件 下载文件&#xff1a; wget [URL]使用wget命令加上要下载的文件的URL&#xff0c;可以将文件下载到当前目录。 指定保存的文件名&#xff1a; wget -O [保存的文件名] [URL]使用-O选项后跟保存的文件名&#xff0c;可以指定下载的文件保存的名称…...

Flutter携带JSON参数post请求

在Flutter中发送带有JSON参数的网络请求&#xff0c;你可以使用HTTP库&#xff08;如http或dio&#xff09;来实现。以下是使用http库发送网络请求并携带JSON参数的示例&#xff1a; import package:http/http.dart as http; import dart:convert;// 创建参数Map Map<Strin…...

【vue】vue-image-lazy图片懒加载使用与介绍【超详细+npm包源代码】

简介 当前插件是基于vue3&#xff0c;写的一个图片懒加载&#xff0c;文章最下方是npm包的源码&#xff0c;你可以自己拿去研究和修改&#xff0c;如有更好的想法可以留言&#xff0c;如果对你有帮助&#xff0c;可以点赞收藏和关注&#xff0c;谢谢。 后续会添加图片放大和切…...

MFC第二十四天 使用GDI对象画笔和画刷来开发控件(分页控件选择态的算法分析、使用CToolTipCtrl开发动静态提示)

文章目录 GDI对象画笔和画刷来开发控件梯形边框的按钮控件CMainDlg.hCMainDlg.cppCLadderCtrl.hCLadderCtrl.cpp 矩形边框的三态按钮控件 CToolTipCtrl开发动静态提示CMainDlg.hCMainDlg.cppCLadderCtrl.hCLadderCtrl.cpp: 实现文件 矩形边框的三态按钮控件 CToolTipCtrl开发动…...

【NLP-新工具】语音转文本与OpenAI的用途

一、说明 OpenAI最近2022发布了一个名为Whisper的新语音识别模型。与DALLE-2和GPT-3不同&#xff0c;Whisper是一个免费的开源模型。它的主要功能就是将语音翻译成文本。本文将介绍如何使用这个重要应用库。 二、 Whisper概念 2.1 Whisper是啥&#xff1f; Whisper 是一种自动…...

try-catch-finally的字节码原理

Java 中有一个非常重要的内容是 try-catch-finally 的执行顺序和返回值问题&#xff0c;其中 finally 一定会执行&#xff0c;但是为什么会这样&#xff1f; 下面看下 try-catch-finally 背后的实现原理 try-catch public class Test {public static void main(String[] args)…...

基于双层优化的微电网系统规划设计方法(Matlab代码实现)

目录 &#x1f4a5;1 概述 1.1 微电网系统结构 1.2 微电网系统双层规划设计结构 1.3 双层优化模型 1.4 上层容量优化模型 1.5 下层调度优化模型 &#x1f4da;2 运行结果 &#x1f389;3 文献来源 &#x1f308;4 Matlab代码、数据、文章讲解 &#x1f4a5;1 概述 文献来源&…...

【Nginx13】Nginx学习:HTTP核心模块(十)Types、AIO及其它配置

Nginx学习&#xff1a;HTTP核心模块&#xff08;十&#xff09;Types、AIO及其它配置 今天学习的内容也比较简单&#xff0c;主要的是 Types 相关的配置&#xff0c;另外还会了解一下 AIO 以及部分没有特别大的分类归属的配置指令的使用。后面的内容都是 HTTP 核心模块中比较小…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

Linux 下 DMA 内存映射浅析

序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存&#xff0c;但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程&#xff0c;可以参考这篇文章&#xff0c;我觉得写的非常…...

ThreadLocal 源码

ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物&#xff0c;因为每个访问一个线程局部变量的线程&#xff08;通过其 get 或 set 方法&#xff09;都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段&#xff0c;这些类希望将…...

react菜单,动态绑定点击事件,菜单分离出去单独的js文件,Ant框架

1、菜单文件treeTop.js // 顶部菜单 import { AppstoreOutlined, SettingOutlined } from ant-design/icons; // 定义菜单项数据 const treeTop [{label: Docker管理,key: 1,icon: <AppstoreOutlined />,url:"/docker/index"},{label: 权限管理,key: 2,icon:…...