力扣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.线性表的定义和基本操作 线性表的定义 定义:线性表是具有相同数据类…...
重磅|微软打响第一枪:爆改HR体系,让组织像AI一样思考
微软打响第一枪:爆改HR体系,让组织像AI一样思考3月25日晚,一封来自微软首席人力资源官(CPO)Amy Coleman 的内部备忘录,把微软庞大的HR架构推倒重来。 这不仅宣告了几位见证微软文化转型期的资深高管&#x…...
思源宋体:七重字体音阶如何重塑中文数字美学
思源宋体:七重字体音阶如何重塑中文数字美学 【免费下载链接】source-han-serif-ttf Source Han Serif TTF 项目地址: https://gitcode.com/gh_mirrors/so/source-han-serif-ttf 当数字界面与中文排版相遇时,你是否有过这样的困惑:为什…...
NVIDIA GPU监控效能深度解析:nvitop如何破解多用户环境资源管理难题
NVIDIA GPU监控效能深度解析:nvitop如何破解多用户环境资源管理难题 【免费下载链接】nvitop An interactive NVIDIA-GPU process viewer and beyond, the one-stop solution for GPU process management. 项目地址: https://gitcode.com/gh_mirrors/nv/nvitop …...
硬件工程师眼中的“省心”麦克风:MP421A-AT01E如何解决射频干扰与声音漂移
从“喂,听得到吗?”到“你说,我听着”:MP421A-AT01E如何让蓝牙耳机回归通话本质你有没有这样的经历?戴上刚买的蓝牙耳机,兴冲冲地给朋友打电话,结果对方第一句就是:“你那边好吵&…...
科研人投稿破局:Paperxie AI 期刊写作,把「拒稿重写」变成「一次过审」
paperxie-免费查重复率aigc检测/开题报告/毕业论文/智能排版/文献综述/期刊论文https://www.paperxie.cn/ai/journalArticleshttps://www.paperxie.cn/ai/journalArticles 在学术圈,「写期刊论文」从来都不是敲字那么简单 —— 要贴合期刊收稿方向、要挖创新点、要卡…...
granite-4.0-h-350m从部署到应用:Ollama本地大模型在法律文书处理中的案例
granite-4.0-h-350m从部署到应用:Ollama本地大模型在法律文书处理中的案例 1. 快速上手:granite-4.0-h-350m模型部署 granite-4.0-h-350m是一个轻量级的指令跟随模型,专门为本地部署和特定领域应用而设计。这个模型只有3.5亿参数࿰…...
SAM 3入门到应用:从图片分割到视频跟踪完整指南
SAM 3入门到应用:从图片分割到视频跟踪完整指南 1. SAM 3简介与核心能力 SAM 3(Segment Anything Model 3)是Facebook推出的新一代图像和视频分割模型,它通过统一的基础架构实现了前所未有的通用分割能力。与传统的专用分割模型…...
ReAct、CoT、ToT大模型推理框架:小白入门指南+程序员实战技巧(收藏必备)
ReAct、CoT、ToT大模型推理框架:小白入门指南程序员实战技巧(收藏必备) 本文深入解析ReAct、CoT、ToT三大核心推理框架,阐述其如何推动大模型从直接输出答案升级为逻辑化推理解题。通过五大维度解析,结合通俗示例与实用…...
SecGPT-14B部署教程:适配国产昇腾910B的vLLM分支编译与性能调优
SecGPT-14B部署教程:适配国产昇腾910B的vLLM分支编译与性能调优 1. SecGPT-14B简介 SecGPT是由云起无垠推出的开源大语言模型,专注于网络安全领域。该模型融合了自然语言理解、代码生成和安全知识推理等能力,旨在为安全专业人员提供智能辅助…...
智能网联汽车(CAV)缩略语大全:从C-V2X到VRUCW,一文搞懂所有专业术语
智能网联汽车(CAV)术语全解析:从技术原理到场景应用 在智能交通系统快速发展的今天,智能网联汽车(Connected-Automated Vehicle, CAV)已经成为行业变革的核心驱动力。无论是汽车工程师、软件开发人员还是交通规划者,都需要掌握这一领域的关键…...
