力扣1312. 让字符串成为回文串的最少插入次数
动态规划
- 思路:
- 通过插入字符构造回文串,要想插入次数最少,可以将字符串 s 的逆序 s' 进行比较找出最长公共子序列;
- 可以先分析,字符串 s 通过插入得到回文串 ps,其中间的字符应该不会变化:
-
若 s' 的长度为奇数,那么它的回文中心为单个字符 c。例如当 s' = "adgda" 时,它的回文中心为单个字符 "g"。我们可以断定,回文中心 c 一定是原字符串 s 中的字符,否则如果 c 是通过操作添加的字符,那么我们可以舍弃这一步操作,此时 s' 成为长度为偶数的字符串,并且它仍是回文串(在例子中,即 "adgda" -> "adda")
-
若 s' 的长度为偶数,那么它的回文中心为两个字符 cc,例如当 s' = "adggda" 时,它的回文中心为两个字符 "gg"。我们同样可以断定,回文中心 cc 一定是原字符串中的两个字符,否则如果 cc 中有至少一个是通过操作添加的字符,那么我们可以舍弃这些操作,此时 s' 成为长度为偶数(舍弃一次操作)或奇数(舍弃两次操作)的字符串,并且它仍是回文串(在例子中,即 "adggda" -> "adgda" 或 "adggda" -> "adda")。
-
-
可以通过原字符串与逆序字符串进行“并集”构建回文字符串,可以假设字符串 s 分成三部分 s(l) c s(r),则其逆序字符串 s(r) c s(l);
-
如果构建之后的回文字符串看作一块板子,原串和逆串像两个“缺了孔”的两块板子叠在一起,补上“缺的孔”就构成了回文串,一样的是公共子串;
-
那么需要补上的“孔”的个数为原串长度减去公共子串长度;
-
综上,问题回到求取两个字符串的最长公共子串,参考 力扣1143. 最长公共子序列
class Solution {
public:int minInsertions(string s) {int n = s.size();std::string invs(s.rbegin(), s.rend());std::vector<std::vector<int>> dp(n + 1, std::vector<int>(n + 1));for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);if (s[i - 1] == invs[j - 1]) {dp[i][j] = std::max(dp[i][j], dp[i - 1][j - 1] + 1);}}}return n - dp[n][n];}
};
————————————————————————————————————

相关文章:
力扣1312. 让字符串成为回文串的最少插入次数
动态规划 思路: 通过插入字符构造回文串,要想插入次数最少,可以将字符串 s 的逆序 s 进行比较找出最长公共子序列;可以先分析,字符串 s 通过插入得到回文串 ps,其中间的字符应该不会变化: 若 s…...
qemu的安装
1、简介 QEMU(Quick EMUlator)是一个开源的处理器模拟器,它可以在一种硬件平台上模拟另一种硬件平台,从而运行各种不同的操作系统。QEMU通过动态二进制翻译来实现高性能的模拟,这使得它可以在接近原生性能的速度下运行…...
myql入门
目录 安装修改密码学习资料个人git仓库文章视频官网 安装 #移除以前的mysql相关 sudo apt remove --purge mysql-\* #安装mysql sudo apt install mysql-server mysql-client #查看是否启动 systemctl status mysql #手动启动 systemctl start mysql #查看mysql版本 mysql --v…...
前端开发有没有必要转鸿蒙开发?
前端开发有没有必要转鸿蒙开发?如果后面的工作中有参与鸿蒙开发的机会,那肯定是转呀!毕竟多接触一些技能也不会有什么坏处。 我想说的是:鸿蒙替代不了前端,如果你目前正在从事前端开发,那么你完全可以将鸿蒙…...
《动手学深度学习(PyTorch版)》笔记1
Chapter1 Introduction 1.1 机器学习的关键组件 data 每个数据集由一个个样本(example, sample)组成,大多时候,它们遵循独立同分布(independently and identically distributed, i.i.d.)。 样本有时也叫做数据点(dat…...
前端工程化之:webpack1-5(配置文件)
一、配置文件 webpack 提供的 cli 支持很多的参数,例如 --mode ,但更多的时候,我们会使用更加灵活的配置文件来控制 webpack 的行为。 默认情况下, webpack 会读取 webpack.config.js 文件作为配置文件,但也可以通过 C…...
代码随想录栈和队列专题二刷复盘day17
栈和队列理论基础 队列是先进先出,栈是先进后出 栈和队列是STL里面的两个数据结构 三个最为普遍的STL版本 1.HP STL其他版本的C STL,一般是以HP STL为蓝本实现出来的,HP STL是C STL的第一个实现版本,且开放源代码 2.P.J.Plauger…...
代码随想录算法刷题训练营day16
代码随想录算法刷题训练营day16:LeetCode(104)二叉树的最大深度 、LeetCode(559)n叉树的最大深度、LeetCode(111)二叉树的最小深度、LeetCode(222)完全二叉树的节点个数 LeetCode(104)二叉树的最大深度 题目 代码 /*** Definition for a binary tree node.* publ…...
【C语言/数据结构】排序(直接插入排序|希尔排序)
🌈个人主页:秦jh__https://blog.csdn.net/qinjh_?spm1010.2135.3001.5343🔥 系列专栏:《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm1001.2014.3001.5482 目录 插入排序 直接插入排序&…...
Jupyter Notebook安装使用教程
Jupyter Notebook 是一个基于网页的交互式计算环境,允许你创建和共享包含代码、文本说明、图表和可视化结果的文档。它支持多种编程语言,包括 Python、R、Julia 等。其应用场景非常广泛,特别适用于数据科学、机器学习和教育领域。它可以用于数…...
Unity 中的接口和继承
在Unity的游戏开发中,理解面向对象编程的概念,如类、接口、继承和多态性,是非常重要的。本文旨在帮助理解和掌握Unity中接口和继承的概念,以及如何在实际项目中应用这些知识。 类和继承 在C#和Unity中,类是构建应用程序…...
C++区间覆盖(贪心算法)
假设有n个区间,分别是:[l1,r1], [l2,r2], [l3,r3].....[ln,rn] 从这n个区间中选出某些区间,要求这些区间满足两两不相交,最多能选出多少个区间呢? 基本思路: 按照右端点从小到大排序,再比较左端…...
Python with Office 054 - Work with Word - 7-9 插入图像 (3)
近日详细学习了寒冰老师的很好的书《让Python遇上Office》,总结了系列视频。 这个是其中的一集:如何在Word中插入图像,我会陆续分享其他的视频并加上相应说明 https://www.ixigua.com/7319498175104942643?logTage9d15418663166a05d10...
Nodejs前端学习Day4_fs文件系统模块基础应用之成绩转换
君子应有龙蛇之变,处于木雁之间 文章目录 前言一、fs文件系统模块1.1 判断文件是否读取成功1.2 向指定的文件中写入内容1.2.1 fs.writeFile的语法格式1.2.2 fs.readFile和fs.writeFile的运用——成绩转换 总结 前言 Day3fs开了点头 一、fs文件系统模块 1.1 判断文…...
五、Kotlin 函数进阶
1. 高阶函数 1.1 什么是高阶函数 以下 2 点至少满足其一的函数称为高阶函数: 形参列表中包含函数类型的参数 //参数 paramN 可以是:函数引用、函数类型变量、或 Lambda 表达式。 fun funName(param1: Type1, param2: Type2, ... , paramN: (p1: T1, p2…...
重温《深入理解Java虚拟机:JVM高级特性与最佳实践(第二版)》 –– 学习笔记(一)
第一部分:走近Java 第1章:走近Java 1.1 Java的技术体系 SUN 官方所定义的 Java 技术体系包括:Java程序设计语言、Java虚拟机、Class文件格式、Java API类库、第三方(商业机构和开源社区)Java类库。 其中࿰…...
定向减免!函数计算让轻量 ETL 数据加工更简单,更省钱
作者:澈尔、墨飏 业内较为常见的高频短时 ETL 数据加工场景,即频率高时延短,一般均可归类为调用密集型场景。此场景有着高并发、海量调用的特性,往往会产生高额的计算费用,而业内推荐方案一般为攒批处理,业…...
git checkout和git switch的区别
git checkout 和 git switch 是 Git 中用于切换分支的命令,但它们在某些方面有一些区别。需要注意的是,git switch 是在 Git 2.23 版本引入的,它提供了一种更直观的分支切换方式。 git checkout: 分支切换: 在 Git 2.…...
故障树分析蒙特卡洛仿真程序(附MATLAB完整代码)
故障树是一种特殊的倒立树状逻辑因果关系图,它用事件符号、逻辑门符号和转移符号描述系统中各种事件之间的因果关系,通过对引起系统故障的各种因素进行逻辑因果分析,确定导致故障发生的各种可能的原因,并通过定性和定量分析找出系…...
数据结构-线性表
文章目录 数据结构—线性表1.线性表的定义和基本操作线性表的定义线性表的特点线性表的基本操作 2.线性表的顺序存储和链式存储表示顺序存储链式存储单链表循环链表双向链表 数据结构—线性表 1.线性表的定义和基本操作 线性表的定义 定义:线性表是具有相同数据类…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...
前端调试HTTP状态码
1xx(信息类状态码) 这类状态码表示临时响应,需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分,客户端应继续发送剩余部分。 2xx(成功类状态码) 表示请求已成功被服务器接收、理解并处…...
