【动态规划-最长公共子序列(LCS)】力扣712. 两个字符串的最小ASCII删除和
给定两个字符串s1 和 s2,返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
示例 1:
输入: s1 = “sea”, s2 = “eat”
输出: 231
解释: 在 “sea” 中删除 “s” 并将 “s” 的值(115)加入总和。
在 “eat” 中删除 “t” 并将 116 加入总和。
结束时,两个字符串相等,115 + 116 = 231 就是符合条件的最小和。
示例 2:
输入: s1 = “delete”, s2 = “leet”
输出: 403
解释: 在 “delete” 中删除 “dee” 字符串变成 “let”,
将 100[d]+101[e]+101[e] 加入总和。在 “leet” 中删除 “e” 将 101[e] 加入总和。
结束时,两个字符串都等于 “let”,结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 “lee” 或 “eet”,我们会得到 433 或 417 的结果,比答案更大。
提示:
0 <= s1.length, s2.length <= 1000
s1 和 s2 由小写英文字母组成
class Solution {
public:int minimumDeleteSum(string s1, string s2) {int m = s1.length(), n = s2.length();vector<vector<int>> dp(m+1,vector<int>(n+1));for(int i = 1; i <= m; i++){char c1 = s1.at(i-1);for(int j = 1; j <= n; j++){char c2 = s2.at(j-1);if(c1 == c2){dp[i][j] = dp[i-1][j-1] + int(c2);}else{dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}}int ans1 = 0, ans2 = 0;for(int i = 0; i < m; i++){ans1 += int(s1[i]);}for(int i = 0; i < n; i++){ans2 += int(s2[i]);}return ans1 + ans2 - 2*dp[m][n];}
};
力扣1143的LCS模板题的变形,我们采用一样的动态规划进行修改, dp[i][j] = dp[i-1][j-1] + int(c2);在这行代码中我们将原本的+1改成了加上字符的ascII码,所以最后dp中储存的是最长公共子序列的ascII码值总和。最后我们计算出字符串s1和s2的ascII码之和,然后减去保留下来的相同子序列的ascII码值(需要乘以2),剩下的就是两个字符串的最小ASCII删除和。
相关文章:
【动态规划-最长公共子序列(LCS)】力扣712. 两个字符串的最小ASCII删除和
给定两个字符串s1 和 s2,返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。 示例 1: 输入: s1 “sea”, s2 “eat” 输出: 231 解释: 在 “sea” 中删除 “s” 并将 “s” 的值(115)加入总和。 在 “eat” 中删除 “t” 并将 116 加入总和。 结束时&…...
override
override 是 C11 引入的一个关键字,override 的作用是在派生类中显式地声明某个函数是用于重写基类的虚函数。它不仅仅是一个语法标记,更重要的是提供了编译时的错误检查功能,确保程序员确实按照预期在派生类中重写了基类的函数。如果没有正确…...
万象奥科工业平板上线,邀您体验与众不同!
Vanxoak推出的全新品类——ARM工业平板电脑!该系列工业平板具有防护等级高、接口丰富、易开发等特点,专为工业HMI(人机界面)和工业控制领域设计。整机采用高性能工业级ARM处理器,适配全贴合电容触摸屏,可选…...
java将word转pdf
总结 建议使用aspose-words转pdf,poi的容易出问题还丑… poi的(多行的下边框就不对了) aspose-words的(基本和word一样) poi工具转换 <!-- 处理PDF --><dependency><groupId>fr.opensagres.xdocreport</groupId><artifactId>fr.opensagres…...
Golang | Leetcode Golang题解之第449题序列化和反序列化二叉搜索树
题目: 题解: type Codec struct{}func Constructor() (_ Codec) { return }func (Codec) serialize(root *TreeNode) string {arr : []string{}var postOrder func(*TreeNode)postOrder func(node *TreeNode) {if node nil {return}postOrder(node.Le…...
基于SpringBoot+Vue+MySQL的美食信息推荐系统
系统展示 用户前台界面 管理员后台界面 系统背景 在数字化时代,随着人们对美食文化的热爱与追求不断增长,美食信息推荐系统成为了连接食客与美食之间的重要桥梁。面对海量的美食信息,用户往往难以快速找到符合个人口味和需求的美食。因此&…...
spring boot jar 分离自动部署脚本
背景 远程部署时spring boot 包,比较大。可以采用依赖库和业务包分离的方式。提供一个脚本进行自动部署 maven 配置分离jar包 <build><finalName>${project.artifactId}</finalName><plugins><plugin><groupId>org.springfra…...
PGMP-03战略一致性
1.概要 program strategy alignment:战略一致性 2.详细...
华为OD机试真题---智能成绩表
题目描述 小明来到某学校当老师,需要将学生按考试总分或单科分数进行排名。输入包括学生人数、科目数量、科目名称、每个学生的姓名和对应科目的成绩,最后输入一个用作排名的科目名称。如果输入的排名科目不存在,则按总分进行排序。输出一行…...
828华为云征文 | 华为云Flexus云服务器X实例搭建企业内部VPN私有隧道,以实现安全远程办公
VPN虚拟专用网络适用于企业内部人员流动频繁和远程办公的情况,出差员工或在家办公的员工利用当地ISP就可以和企业的VPN网关建立私有的隧道连接。 通过拨入当地的ISP进入Internet再连接企业的VPN网关,在用户和VPN网关之间建立一个安全的“隧道”ÿ…...
Hadoop集群的高可用(HA):NameNode和resourcemanager高可用的搭建
文章目录 一、NameNode高可用的搭建1、免密配置2、三个节点都需要安装psmisc3、检查三个节点是否都安装jdk以及zk4、检查是否安装了hadoop集群5、修改hadoop-env.sh6、修改core-site.xml7、修改hdfs-site.xml8、检查workers 文件是否为三台服务9、分发给其他两个节点10、初始化…...
支付宝沙箱环境 支付
一 什么是沙箱: 沙箱环境是支付宝开放平台为开发者提供的安全低门槛的测试环境 支付宝正式和沙箱环境的区别 : AI: 从沙箱到正式环境: 当应用程序开发完成后,需要将应用程序从沙箱环境迁移到正式环境。 这通常涉及…...
获取unity中prefab的中文文本内容以及和prefab有关的问题
背景1:经常会在开发中遇到策划需要改某个界面,但是我们不知道那是什么界面,只看到一些关键字比如圣诞活动,那这样我就可以轻易找到这个预设了。另外还可以扩展就是收集项目中的所有中文文本然后归集到多语言表中,然后接…...
Web自动化中常用XPath定位方式
在进行Web自动化测试时,元素定位是一个至关重要的环节。XPath(XML Path Language)是一种用于在XML文档中定位节点的语言。在Web自动化中,XPath广泛应用于定位HTML元素。本文将详细介绍几种常用的XPath定位方式,包括绝对…...
Unity3D播放GIF图片使用Animation来制作动画
系列文章目录 unity工具 文章目录 系列文章目录👉前言👉一、下载GIF动图,用PS制作导出帧动画图片👉二、使用Animation制作动画👉三、脚本控制动画播放👉壁纸分享👉总结👉前言 unity播放gif图片,本身是不支持的,但是可以使用其他方法来实现, 1.有一种使用System…...
redo log 和 bin log 的两阶段提交
两阶段提交的过程 当事务提交后,有一个两阶段提交策略。 在开启两阶段提交时,会开启一个 XA 事务(宏观上的事务), Prepare 阶段:将 redo log 的状态设置为 prepare,然后将 事务XID 写入 redo…...
Go基础学习07-map注意事项;多协程对map的资源竞争;sync.Mutex避免竟态条件
文章目录 Go中map使用以及注意事项map使用时的并发安全问题 Go中map使用以及注意事项 Go语言中map使用简单示例: func main() {var mp map[string]int// mp : map[string]int{}val, ok : mp["one"]if ok {fmt.Println(val)} else {fmt.Println(val)}mp[…...
远程服务器安装anaconda并创建虚拟环境
1、承接上文新用户zrcs,在服务器的zrcs文件夹下直接下载anaconda(很慢): wget https://repo.anaconda.com/archive/Anaconda3-2024.06-1-Linux-x86_64.sh 或者选择本地下载,清华大学开源软件镜像站:https:/…...
什么是IIC通信协议?
IIC(Inter-Integrated Circuit)通信协议,又称为I2C(Inter-Integrated Circuit 2)协议,是一种广泛使用的串行通信协议。它由飞利浦半导体公司(现NXP Semiconductors)开发,…...
P3131 [USACO16JAN] Subsequences Summing to Sevens S Python题解
[USACO16JAN] Subsequences Summing to Sevens S 题目描述 Farmer John’s N N N cows are standing in a row, as they have a tendency to do from time to time. Each cow is labeled with a distinct integer ID number so FJ can tell them apart. FJ would like to ta…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
