力扣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.线性表的定义和基本操作 线性表的定义 定义:线性表是具有相同数据类…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...

中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...