动态规划-最长回文子串
题目描述
给你一个字符串 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等文档中的文字转换成语音
✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...
