算法-动态规划/中心扩散法-最长回文子串
算法-动态规划/中心扩散法-最长回文子串
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级新生。在疫情结束后,他们选择百战归来再读书,重新回到久违的课堂,共同探索科创大时代下企业的商业本质,开启新的学习与人生旅程。复旦大学管理学院院长陆雄文教授…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
