当前位置: 首页 > 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 核心模块中比较小…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...

多元隐函数 偏导公式

我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式&#xff0c;给定一个隐函数关系&#xff1a; F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 &#x1f9e0; 目标&#xff1a; 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z​、 …...

命令行关闭Windows防火墙

命令行关闭Windows防火墙 引言一、防火墙:被低估的"智能安检员"二、优先尝试!90%问题无需关闭防火墙方案1:程序白名单(解决软件误拦截)方案2:开放特定端口(解决网游/开发端口不通)三、命令行极速关闭方案方法一:PowerShell(推荐Win10/11)​方法二:CMD命令…...

Java并发编程实战 Day 11:并发设计模式

【Java并发编程实战 Day 11】并发设计模式 开篇 这是"Java并发编程实战"系列的第11天&#xff0c;今天我们聚焦于并发设计模式。并发设计模式是解决多线程环境下常见问题的经典解决方案&#xff0c;它们不仅提供了优雅的设计思路&#xff0c;还能显著提升系统的性能…...