动态规划-最长回文子串
题目描述
给你一个字符串 s,找到 s 中最长的 回文子串。
对于该题使用中心扩展法在某些情况下可以比动态规划方法更优,尤其是在处理较长字符串时。这是因为中心扩展法具有更好的空间复杂度,并且在实际应用中可能具有更快的运行速度,尽管其时间复杂度与动态规划相同(均为O(n^2))。但是本专题主要讲解动态规划算法,因此不对其过多讲解。
解题思路
当使用动态规划(Dynamic Programming, DP)方法来解决寻找字符串中最长回文子串的问题时,我们主要关注如何定义状态、状态转移方程以及边界条件。下面,我将详细讲解这个过程。
1. 定义状态
首先,我们需要定义DP数组dp,其中dp[i][j]表示字符串s中从索引i到索引j的子串(即s[i--j])是否是回文子串。注意,这里i和j都是基于0的索引。
2. 初始化状态
- 对于所有
i,dp[i][i]都是true,因为单个字符自然是回文。 - 如果字符串
s的长度大于1,我们还应该初始化长度为2的子串。即,对于所有i,如果s[i] == s[i+1],则dp[i][i+1]为true,否则为false。
3. 状态转移方程
对于长度大于2的子串s[i--j],如果s[i] == s[j],则当s[i--j]是回文的,那么s[i+1--j-1]也是回文。因此,状态转移方程为:
dp[i][j] = ( s[i] ==s [j] )∧dp[i+1][j−1] .
其中,i和j满足j > i + 1,以确保子串s[i+1--j-1]的长度至少为1。
4. 边界条件
- 需要注意
i和j的遍历顺序。由于DP表的填充依赖于较小的子问题,我们应该从较小的子串开始,逐步扩展到较大的子串。这通常意味着外层循环遍历子串的长度(从2开始,直到整个字符串的长度),内层循环遍历起始索引i。 - 当
j超出字符串s的边界时,应停止内层循环。
5. 记录最长回文子串
在填充DP表的过程中,我们可以跟踪并记录遇到的最长回文子串的起始索引和长度。
代码示例
class Solution {
public:string longestPalindrome(string s) {int n = s.length();if (n < 2)return s; //如果字符串长度小于2,直接返回原字符串vector<vector<bool>> dp(n, vector<bool>(n, false));int start = 0, maxLength = 1; //初始化最长回文子串的起始位置和长度// 初始化长度为1和2的子串for (int i = 0; i < n; ++i) {dp[i][i] = true; // 单个字符是回文if (i < n - 1 && s[i] == s[i + 1]) {dp[i][i + 1] = true;start = i;maxLength = 2; //如果找到长度为2的回文子串,则更新最长回文子串}}//填充DP表,并找到最长回文子串for (int len = 3; len <= n; ++len) { for (int i = 0; i <= n - len; ++i) {int j = i + len - 1;if (s[i] == s[j] && dp[i + 1][j - 1]) {dp[i][j] = true;start = i; //更新最长回文子串的起始位置maxLength = len; //更新最长回文子串的长度}}}//返回最长回文子串return s.substr(start, maxLength);}
};
中心扩展法:
class Solution {
public:string longestPalindrome(string s) {int start = 0, maxLength = 1;for (int i = 0; i < s.length(); ++i) {//奇数长度的回文子串int len1 = expandAroundCenter(s, i, i);//偶数长度的回文子串int len2 = expandAroundCenter(s, i, i + 1);//更新最长回文子串的起始位置和长度int len = max(len1, len2);if (len > maxLength) {start = i - (len - 1) / 2;maxLength = len;}}return s.substr(start, maxLength);}int expandAroundCenter(string& s, int left, int right) {int L = left, R = right;while (L >= 0 && R < s.length() && s[L] == s[R]) {L--;R++;}//返回以left和right为中心的回文子串的长度(注意要+1来包含中心字符)return R - L - 1;}
};
实现步骤:
- 遍历字符串中的每个字符(以及每对相邻字符,以处理偶数长度的回文),将它们作为潜在的中心点。
- 从中心点开始向两侧扩展,检查两侧字符是否相等,如果相等则继续扩展,直到不再相等为止。
- 在扩展过程中,记录遇到的最长回文子串的起始位置和长度。
- 遍历完成后,返回最长回文子串。
相关文章:
动态规划-最长回文子串
题目描述 给你一个字符串 s,找到 s 中最长的 回文子串。 对于该题使用中心扩展法在某些情况下可以比动态规划方法更优,尤其是在处理较长字符串时。这是因为中心扩展法具有更好的空间复杂度,并且在实际应用中可能具有更快的运行速度…...
海康威视 嵌入式 面经 海康威视嵌入式软件 嵌入式硬件总结面试经验 面试题目汇总
标题海康威视 嵌入式 面经 海康威视嵌入式软件 嵌入式硬件总结面试经验 面试题目汇总 整理总结了海康威视嵌入式的面试题目!,可以供大家面试参考 标题海康威视 嵌入式 面经 五月底投递,六月初面试,一场技术面,一场H…...
使用图论技巧——有遍数限制的最短路
给定一个 n个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。 请你求出从 11 号点到 n 号点的最多经过 k 条边的最短距离,如果无法从 1 号点走到 n 号点,输出 impossible。 注意:图中可能 存在负权回路…...
flume 使用 exec 采集容器日志,转储磁盘
flume 使用 exec 采集容器日志,转储磁盘 在该场景下,docker 服务为superset,flume 的sources 选择 exec , sinks选择 file roll 。 任务配置 具体配置文件如下: #simple.conf: A single-node Flume configuration#…...
459重复的子字符串
给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。 public repeatedSubstringPattern(String s){int n s.length();for(int i 1; i < n / 2; i){if(n % i ! 0) continue;// substring获取子字符串是左闭右开的String ss s.substring(0,…...
【HarmonyOS NEXT】实现截图功能
【HarmonyOS NEXT】实现截图功能 【需求】 实现:实现点击截图按钮,实现对页面/组件的截图 【步骤】 编写页面UI Entry Component struct Screenshot {BuildergetSnapContent() {Column() {Image().width(100%).objectFit(ImageFit.Auto).borderRadi…...
小皮面板webman ai项目本地启动教程
1.前置条件 下载小皮面板 下载后,双击安装,一路next(下一步),无需更改配置。 2.安装必须软件 在小皮面板的软件管理页,安装编号①②③④下面四个软件。 3.启动本地服务 进入到小皮面板的首页&#x…...
从零实现诗词GPT大模型:实现多头自注意力
专栏规划: https://qibin.blog.csdn.net/article/details/137728228 在上一篇文章的最后,我们已经介绍了为什么要使用多头注意力了,本篇文章我们主要来实现多头自注意力,然后综合我们之前实现的FFN和TransformerBlock其实就差不多完成了整个GPT模型的实现了。 在开始实现之…...
[rk3399 android11]关闭声卡
使用以下命令查看声卡,可以看到目前有三个声卡 cat /proc/asound/cards 修改设备树 diff --git a/kernel/arch/arm64/boot/dts/rockchip/rk3399-jw-d039.dts b/kernel/arch/arm64/boot/dts/rockchip/rk3399-jw-d039.dtsindex 515334c127..5b592a852f 100755--- a/…...
项目实战 ---- 商用落地视频搜索系统(7)---预处理二次优化
目录 背景 要解决的问题 技术理念与落地思路 完整代码 另外的问题与解决 优化运行效果 log 效果图 背景 作为商用落地系统,我们当然希望搜索视频的关联度或者说准确性与我们希望查询的视频相关度越高越好。为此,除了在query 层面上优化,我们还需要注重我们的录入数…...
【干货分享】央企国企的群面、半结构面试复习方法和经验总结
目录 0.前言1.个人背景介绍2.行业选择心路历程3.求职历程3.1 网申如何准备?3.2 笔试考什么?如何准备3.2.1 笔试考什么?3.2.2 笔试如何准备4.面试如何准备?敲黑板!重点!4.1 面试题收集来源、我的准备方法4.…...
前端HTML基础笔记
HTML(HyperText Markup Language,超文本标记语言)是一种用于创建网页的标准标记语言。它通过一系列的元素(或称为标签)来定义网页的结构和内容。HTML文档由一系列的元素组成,这些元素可以包含文本、图片、链…...
用三极管搭建简易电流源
目录 一、三极管搭建电流源设计思路二、实例及搭建仿真1.电阻分压偏置 2.齐纳二极管偏置 3.串联二极管偏置 一、三极管搭建电流源设计思路 设计思路:利用分压电路,可用多种方式给基极提供偏压,使三极管处于放大区,VB保持稳定电压&…...
MiniGPT-3D, 首个高效的3D点云大语言模型,仅需一张RTX3090显卡,训练一天时间,已开源
项目主页:https://tangyuan96.github.io/minigpt_3d_project_page/ 代码:https://github.com/TangYuan96/MiniGPT-3D 论文:https://arxiv.org/pdf/2405.01413 MiniGPT-3D在多个任务上取得了SoTA,被ACM MM2024接收,只拥…...
Android Google Maps
Android 谷歌地图 前言正文一、设置Google Cloud 项目二、项目配置① 设置SDK② 配置API密钥③ 配置AndroidManifest.xml 三、添加地图四、定位当前① 请求定位权限② 我的位置控件③ 获取当前位置 五、配置地图① xml配置地图② 代码配置地图③ 地图点击事件④ 管理Marker 六、…...
Linux——进程概念
什么是操作系统 操作系统管理各种计算机硬件、为应用程序提供基础、并且充当计算机硬件与用户之间的中介。 冯诺依曼体系 这里的存储器指的是内存不考虑缓存情况,这里的CPU能且只能对内存进行读写,不能访问外设(输入或输出设备)外设(输入或输出设备)要…...
【H2O2|全栈】关于HTML(1)认识HTML
HTML相关知识 目录 前言 准备工作 WEB前端是什么? HTML是什么? 如何运行HTML文件? 标签 概念 分类 双标签和单标签 行内标签和块标签 HTML文档结构 预告和回顾 UI设计相关 Markdown | Md文档相关 项目合作管理相关 后话 前…...
Oracle(111) 如何使用RMAN备份数据库?
使用 RMAN(Recovery Manager)备份 Oracle 数据库是确保数据安全和可恢复性的关键步骤。下面是详细的指导和代码示例,展示如何使用 RMAN 进行数据库备份。 1. 准备工作 在开始备份之前,需要确保以下几点: 已安装并配…...
linux字符设备驱动程序
字符设备驱动程序简介 linux系统中万物皆文件,驱动程序加载后会在/dev目录下生成一 个对应的文件,如/dev/led。应用程序就是先用open打开该文件, 用write控制led的亮灭,用read读取led的亮灭,用完之后用close 关闭该…...
【pyhton】python如何实现将word等文档中的文字转换成语音
✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
Java数组Arrays操作全攻略
Arrays类的概述 Java中的Arrays类位于java.util包中,提供了一系列静态方法用于操作数组(如排序、搜索、填充、比较等)。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序(sort) 对数组进行升序…...
从实验室到产业:IndexTTS 在六大核心场景的落地实践
一、内容创作:重构数字内容生产范式 在短视频创作领域,IndexTTS 的语音克隆技术彻底改变了配音流程。B 站 UP 主通过 5 秒参考音频即可克隆出郭老师音色,生成的 “各位吴彦祖们大家好” 语音相似度达 97%,单条视频播放量突破百万…...
GeoServer发布PostgreSQL图层后WFS查询无主键字段
在使用 GeoServer(版本 2.22.2) 发布 PostgreSQL(PostGIS)中的表为地图服务时,常常会遇到一个小问题: WFS 查询中,主键字段(如 id)莫名其妙地消失了! 即使你在…...
