算法-动态规划/中心扩散法-最长回文子串
算法-动态规划/中心扩散法-最长回文子串
1 题目概述
1.1 题目出处
https://leetcode.cn/problems/longest-palindromic-substring
1.2 题目描述
2 动态规划
2.1 思路
dp[i][j] 表示[i,j]之间的字符串是否是回文。
那么,如果chars[i] = chars[j]时,就有可能构成的子串为回文:
- 如果j - i < 3,则子串肯定是回文。比如 aba、aa、a
- 如果j - i >=3,则就会用到动态规划了,即 dp[i][j] = dp[i+1][j-1],也就是说 i的下一个字符和j的前一个字符组成的闭区间子串是否是回文,只要是那么本子序列也是。
- 这里有个重要的点,表达式为dp[i][j] = dp[i+1][j-1],也就是说i取决于i+1,j取决于j-1,所以遍历时需要i从大到小计算,而j需要从小到大计算。
- 遍历过程中,每当判断子序列为回文,就和之前已经找到的最大回文长度的比较,如果更长就更新,并记录下i、j
- 最后将字符串从i、j取子序列即可
2.2 代码
public class Solution {public String longestPalindrome(String s) {// 表示[i,j]之间的字符串是否是回文boolean[][] dp = new boolean[s.length()][s.length()];for(int i = 0; i < s.length(); i++) {// 定义同一个位置的为truedp[i][i] = true;}int maxLength = 0;int left = 0, right = 0;for (int i = s.length() - 1; i >= 0; i--) {for (int j = i + 1; j < s.length(); j++) {if (s.charAt(i) == s.charAt(j)) {if (j - i < 3) {dp[i][j] = true;} else {dp[i][j] = dp[i+1][j-1];}if (dp[i][j] && (j - i + 1 > maxLength)) {maxLength = j - i + 1;left = i;right = j;}}}}return s.substring(left, right+1);}}
2.3 时间复杂度
O(N^2)
2.4 空间复杂度
O(N^2)
3 中心扩散
3.1 思路
从左到右移动,每当移动一次后,往两边扩散,直到两侧边界字符不符合回文规则。
3.2 代码
public class Solution {int maxLength = 0;int left = 0, right = 0;public String longestPalindrome(String s) {for (int i = 0; i < s.length() - 1; i++) {// 字符串奇数长度时,中间一个字符串往两边扩散spread(i, i, s);// 字符串偶数长度时,中间两个字符串往两边扩散spread(i, i+1, s);}return s.substring(left, right+1);}private void spread(int i, int j, String s) {while (i >= 0 && j < s.length()) {if (s.charAt(i) != s.charAt(j)) {break;} i--;j++;}// 把多减了、加了的补上i++;j--;if (j - i + 1 > maxLength) {left = i;right = j;maxLength = j - i + 1;}}
}
3.3 时间复杂度
O(N^2)
3.4 空间复杂度
O(1)
参考文档
- 动态规划、中心扩散
- 图解马拉车算法
相关文章:

算法-动态规划/中心扩散法-最长回文子串
算法-动态规划/中心扩散法-最长回文子串 1 题目概述 1.1 题目出处 https://leetcode.cn/problems/longest-palindromic-substring 1.2 题目描述 2 动态规划 2.1 思路 dp[i][j] 表示[i,j]之间的字符串是否是回文。 那么,如果chars[i] chars[j]时,就…...
(6)SpringMVC中使用CharacterEncodingFilter编码过滤器处理请求和响应的乱码问题
处理SpringMVC中乱码问题 处理原生Servlet中请求和响应的乱码问题,参考文章 Servlet中的过滤器的实现及其原理,参考文章 配置CharacterEncodingFilter 在Servlet规范中要求request和response对象设置编码之前不能有获取请求参数和响应数据的操作,否则后续设置的编码都将不起…...

USB协议层数据格式
USB协议 1. 硬件拓扑结构2. 协议层2.1 字节/位传输顺序2.2 SYNC域2.3 包格式2.3.1 PID域2.3.2 令牌包(Token)2.3.3 数据包2.3.4 握手包 2.4 传输细节2.4.1 传输(Transfer)和事务(Transaction)2.4.2 过程(stage)和阶段(phase)2.4.3 批量传输2.4.4 中断传输2.4.5 实时传输2.4.6 控…...

加密的重要性,MySQL加密有哪些好处?
加密是一种将信息转化为无法直接读取的格式的技术,从而保护信息安全。在当今数字化的世界中,数据已成为企业的重要资产,因此加密的重要性不言而喻。在这篇文章中,我们将探讨MySQL加密的好处以及如何选择合适的加密算法。 MySQL加密…...

Python为Excel中每一个单元格计算其在多个文件中的平均值
本文介绍基于Python语言,对大量不同的Excel文件加以跨文件、逐单元格平均值计算的方法。 首先,我们来明确一下本文的具体需求。现有一个文件夹,其中有如下所示的大量Excel文件,我们这里就以.csv文件为例来介绍。其中,每…...
LLM 系列之 Transformer 组件总结
本系列为LLM 学习博客,会一一记录各个模块解读。 以下内容参考:大语言模型综述 https://github.com/RUCAIBox/LLMSurvey 主流架构 大语言模型,主要的核心组件是Transformer。不同的模型选择的架构不一样,目前主流架构有: 编码器…...

计算机等级考试—信息安全三级真题十
目录 一、单选题 二、填空题 三、综合题 一、单选题...

面试总结(mysql定精度/oom排查/spring三级缓存/stream流)
Mysql数据类型上的一个把握 1、MySQL Decimal为什么不会丢失精度 DECIMAL的存储方式和其他数据类型都不同,它是以字符串形式存储的。假设一个字段为DECIMAL(3,0),当我们存入100时,实际上存入的1、0、0这三个字符拼接而成的字符串的二进制值&…...
uniapp四个元素点击那个哪个变色,其他的还变原来的颜色
在UniApp中,可以使用CSS伪类选择器和动态样式绑定来实现点击某个元素时改变其颜色的效果。假设有四个元素分别为A、B、C和D。 首先,为这四个元素添加一个共同的类名,例如"item"。 然后,在页面的样式中定义两种颜色&am…...

Springcloud笔记(2)-Eureka服务注册
Eureka服务注册 服务注册,发现。 在Spring Cloud框架中,Eureka的核心作用是服务的注册和发现,并实现服务治理。 Eureka包含两个组件:Eureka Server和Eureka Client。 Eureka Server提供服务注册服务,各个节点启动后…...
国庆 day 5
QT实现TCP服务器客户端搭建的代码,现象 服务器 #include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);server new QTcpServer(this);connect (server,&…...

计算机网络 | OSI 参考模型
计算机网络 | OSI 参考模型 计算机网络 | OSI 参考模型应用层表示层会话层传输层网络层数据链路层物理层 参考视频:王道计算机考研 计算机网络 参考书:《2022年计算机网络考研复习指导》 计算机网络 | OSI 参考模型 OSI 参考模型自下而上分为7层&…...

uniapp 实现地图头像上的水波纹效果
最近实现了uniapp 地图头像水波纹的效果,话不多说,先来看看视频效果吧:链接 在这里具体的代码就不放出来了,还是利用了uniapp的 uni.createAnimation 方法,因为cover-view 不支持一些css 的动画效果,所以这…...

Zabbix7.0 LTS新功能
一、简介 LTS是长期支持。LTS版本支持5年。如果更喜欢稳定性,未涉及到最新的功能,可以选次新的LTS或者更低解决方案。而Zabbix6.4是最新的主要版本不属于LTS版本。 二、新功能 从以下几个方面介绍部分新功能: 性能提升:内存储存…...

充电100%并非都是美事,有时少点更有溢出!如何正确为iPhone充电
iPhone是非凡的设备,但一旦电池耗尽,它们就会失去光泽。这就是为什么照看电池内部并确保始终正确充电很重要。 在这篇文章中,我们解释了如果你想让你的iPhone每天运行到深夜,并尽可能多地保持这种状态,你需要采取的步…...

【软件测试】JUnit详解
文章目录 一. Junit是什么?二.Junit中常见的注解1. Test2. BeforeAll & AfterAll3. BeforeEach & AfterEach4. ParameterizedTest参数化5. Disabled6. Order 三. 测试套件1. 通过class运行测试用例2. 通过包运行测试用例 四. 断言 一. Junit是什么? JUnit是一个用于…...
hive统计页面停留时间
1、背景:通过业务埋点数据,统计用户在页面的停留时间 样例数据,样例数据存入表tmp, 有如下字段用户uid、动作时间戳time、页面名称pn、动作名称action SELECT 12345 AS uid, 1695613731020 AS time, 搜索 AS pn, click AS acti…...

LeetCode 24.两两交换链表中的结点
题目链接 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 题目解析 首先可以特判一下,如果结点数目小于等于1,则直接返回即可,因为数目小于等于1就不需要交换了。 然后我们可以创建一个虚拟的头结点,然…...

【每日一记】OSPF区域划分详讲、划分区域的优点好处
个人名片: 🐼作者简介:一名大二在校生,喜欢编程🎋 🐻❄️个人主页🥇:小新爱学习. 🐼个人WeChat:hmmwx53 🕊️系列专栏:🖼…...

复旦管院启动科创战略,培养科技研发人才,引领未来发展!
今年夏天,600多位优秀的企业家成为复旦大学EMBA 2023级新生。在疫情结束后,他们选择百战归来再读书,重新回到久违的课堂,共同探索科创大时代下企业的商业本质,开启新的学习与人生旅程。复旦大学管理学院院长陆雄文教授…...

idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...

ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...