力扣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.线性表的定义和基本操作 线性表的定义 定义:线性表是具有相同数据类…...
InstructPix2Pix实现Web端图像编辑:前端开发实战
InstructPix2Pix实现Web端图像编辑:前端开发实战 1. 为什么要把InstructPix2Pix搬到浏览器里 你有没有遇到过这样的场景:设计师同事发来一张产品图,需要临时把背景换成纯白;电商运营急着要一组节日主题的海报,但PS操…...
别再傻傻分不清!雷达、激光雷达、超声波在ROS2里到底怎么选?实战避坑指南
雷达、激光雷达与超声波传感器在ROS2中的实战选型指南 引言 在机器人感知系统的设计中,传感器选型往往决定着整个项目的成败。面对市场上琳琅满目的雷达、激光雷达和超声波传感器,工程师们常常陷入选择困难。这三种传感器各有千秋,但价格、性…...
Creo新手必看:如何快速搞定紫铜零件单位换算(附密度设置技巧)
Creo实战指南:紫铜零件单位换算与材料密度设置全解析 在三维建模领域,精确的材料属性设置往往被初学者忽视,却直接影响产品设计的可靠性和后续分析结果。作为Creo入门用户,当你第一次尝试为紫铜零件计算重量时,可能会…...
Qwen3-4B快速上手:无需深度学习基础,轻松玩转AI对话
Qwen3-4B快速上手:无需深度学习基础,轻松玩转AI对话 想体验一个反应迅速、对话流畅的AI助手吗?阿里通义千问的Qwen3-4B模型或许就是你需要的。这个专门优化过的版本去掉了所有视觉处理功能,专注于文本对话,响应速度大…...
AI赋能开发:让快马智能分析并优化你的openclaw101风格网站代码与体验
今天想和大家分享一个很有意思的发现:用AI辅助开发工具来优化技术博客网站,效果真的超出预期。就拿我最近在InsCode(快马)平台上体验的openclaw101风格网站优化来说,整个过程既高效又有趣。 网站分析阶段 首先,我让平台的AI模型…...
当游戏语言成为障碍:如何用XUnity.AutoTranslator打破语言壁垒
当游戏语言成为障碍:如何用XUnity.AutoTranslator打破语言壁垒 【免费下载链接】XUnity.AutoTranslator 项目地址: https://gitcode.com/gh_mirrors/xu/XUnity.AutoTranslator 想象一下,你终于等到了期待已久的日式角色扮演游戏,但打…...
GIL已死,但并发未生:从字节码级剖析无锁Python的7类竞态陷阱与4种Lock-Free算法选型矩阵
第一章:GIL已死,但并发未生:无锁Python并发范式的认知重构Python的全局解释器锁(GIL)长期被视为并发编程的“原罪”,但自CPython 3.13起,GIL在I/O密集型路径中已被条件性移除,而3.14…...
StructBERT-Large本地化部署实战:无需联网、不传数据、隐私安全的语义匹配解决方案
StructBERT-Large本地化部署实战:无需联网、不传数据、隐私安全的语义匹配解决方案 你是不是经常需要判断两句话是不是一个意思?比如,检查用户提交的答案是否和标准答案一致,或者判断两篇新闻稿是不是在说同一件事。过去…...
Ubuntu服务器中文乱码终极解决方案:从locale配置到阿里云重启避坑指南
Ubuntu服务器中文乱码终极解决方案:从locale配置到阿里云重启避坑指南 当你第一次在Ubuntu服务器上看到中文字符变成一堆问号或方框时,那种困惑和挫败感我深有体会。特别是在云服务器环境下,问题往往比本地环境更复杂——即使按照常规教程操作…...
保姆级教程:手把手教你安装并激活DevExpress 20.1.3(附资源与注册机使用避坑指南)
深度指南:DevExpress 20.1.3开发环境高效配置与资源管理 在.NET生态系统中,DevExpress始终以其强大的控件库和高效的开发工具占据重要地位。对于刚接触这个工具集的开发者来说,如何快速搭建一个稳定的开发环境往往成为项目启动的第一道门槛。…...
