当前位置: 首页 > news >正文

算法-动态规划/中心扩散法-最长回文子串

算法-动态规划/中心扩散法-最长回文子串

1 题目概述

1.1 题目出处

https://leetcode.cn/problems/longest-palindromic-substring

1.2 题目描述

在这里插入图片描述

2 动态规划

2.1 思路

dp[i][j] 表示[i,j]之间的字符串是否是回文。
那么,如果chars[i] = chars[j]时,就有可能构成的子串为回文:

  1. 如果j - i < 3,则子串肯定是回文。比如 aba、aa、a
  2. 如果j - i >=3,则就会用到动态规划了,即 dp[i][j] = dp[i+1][j-1],也就是说 i的下一个字符和j的前一个字符组成的闭区间子串是否是回文,只要是那么本子序列也是。
  3. 这里有个重要的点,表达式为dp[i][j] = dp[i+1][j-1],也就是说i取决于i+1,j取决于j-1,所以遍历时需要i从大到小计算,而j需要从小到大计算。
  4. 遍历过程中,每当判断子序列为回文,就和之前已经找到的最大回文长度的比较,如果更长就更新,并记录下i、j
  5. 最后将字符串从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]之间的字符串是否是回文。 那么&#xff0c;如果chars[i] chars[j]时&#xff0c;就…...

(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加密有哪些好处?

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

Python为Excel中每一个单元格计算其在多个文件中的平均值

本文介绍基于Python语言&#xff0c;对大量不同的Excel文件加以跨文件、逐单元格平均值计算的方法。 首先&#xff0c;我们来明确一下本文的具体需求。现有一个文件夹&#xff0c;其中有如下所示的大量Excel文件&#xff0c;我们这里就以.csv文件为例来介绍。其中&#xff0c;每…...

LLM 系列之 Transformer 组件总结

本系列为LLM 学习博客&#xff0c;会一一记录各个模块解读。 以下内容参考:大语言模型综述 https://github.com/RUCAIBox/LLMSurvey 主流架构 大语言模型&#xff0c;主要的核心组件是Transformer。不同的模型选择的架构不一样&#xff0c;目前主流架构有&#xff1a; 编码器…...

计算机等级考试—信息安全三级真题十

目录 一、单选题 二、填空题 三、综合题 一、单选题...

面试总结(mysql定精度/oom排查/spring三级缓存/stream流)

Mysql数据类型上的一个把握 1、MySQL Decimal为什么不会丢失精度 DECIMAL的存储方式和其他数据类型都不同&#xff0c;它是以字符串形式存储的。假设一个字段为DECIMAL(3,0)&#xff0c;当我们存入100时&#xff0c;实际上存入的1、0、0这三个字符拼接而成的字符串的二进制值&…...

uniapp四个元素点击那个哪个变色,其他的还变原来的颜色

在UniApp中&#xff0c;可以使用CSS伪类选择器和动态样式绑定来实现点击某个元素时改变其颜色的效果。假设有四个元素分别为A、B、C和D。 首先&#xff0c;为这四个元素添加一个共同的类名&#xff0c;例如"item"。 然后&#xff0c;在页面的样式中定义两种颜色&am…...

Springcloud笔记(2)-Eureka服务注册

Eureka服务注册 服务注册&#xff0c;发现。 在Spring Cloud框架中&#xff0c;Eureka的核心作用是服务的注册和发现&#xff0c;并实现服务治理。 Eureka包含两个组件&#xff1a;Eureka Server和Eureka Client。 Eureka Server提供服务注册服务&#xff0c;各个节点启动后…...

国庆 day 5

QT实现TCP服务器客户端搭建的代码&#xff0c;现象 服务器 #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 参考模型应用层表示层会话层传输层网络层数据链路层物理层 参考视频&#xff1a;王道计算机考研 计算机网络 参考书&#xff1a;《2022年计算机网络考研复习指导》 计算机网络 | OSI 参考模型 OSI 参考模型自下而上分为7层&…...

uniapp 实现地图头像上的水波纹效果

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

Zabbix7.0 LTS新功能

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

充电100%并非都是美事,有时少点更有溢出!如何正确为iPhone充电

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

【软件测试】JUnit详解

文章目录 一. Junit是什么?二.Junit中常见的注解1. Test2. BeforeAll & AfterAll3. BeforeEach & AfterEach4. ParameterizedTest参数化5. Disabled6. Order 三. 测试套件1. 通过class运行测试用例2. 通过包运行测试用例 四. 断言 一. Junit是什么? JUnit是一个用于…...

hive统计页面停留时间

1、背景&#xff1a;通过业务埋点数据&#xff0c;统计用户在页面的停留时间 样例数据&#xff0c;样例数据存入表tmp&#xff0c; 有如下字段用户uid、动作时间戳time、页面名称pn、动作名称action SELECT 12345 AS uid, 1695613731020 AS time, 搜索 AS pn, click AS acti…...

LeetCode 24.两两交换链表中的结点

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

【每日一记】OSPF区域划分详讲、划分区域的优点好处

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大二在校生&#xff0c;喜欢编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;小新爱学习. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc…...

复旦管院启动科创战略,培养科技研发人才,引领未来发展!

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

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...