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

LeetCode hot 100—最长回文子串

题目

给你一个字符串 s,找到 s 中最长的 回文 子串

示例

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd"
输出:"bb"

分析

动态规划法

使用动态规划来解决最长回文子串问题的核心思想是利用子问题的解来构建更大问题的解。具体来说,我们定义一个二维布尔数组 dp[i][j] ,其中 dp[i][j] 表示字符串 s 从索引 i 到索引 j 的子串是否为回文串。

状态定义

dp[i][j]:表示子串 s[i...j] 是否为回文串,true 表示是,false 表示不是。

状态转移方程

当 s[i] == s[j] 时:

  • 如果 j - i < 2(即子串长度为 1 或 2),那么 dp[i][j] = true 。例如,单个字符一定是回文串,两个相同字符组成的子串也是回文串。
  • 如果 dp[i + 1][j - 1] 为 true ,那么 dp[i][j] = true 。也就是说,当两端字符相同,且去掉两端字符后的子串也是回文串时,当前子串就是回文串。

当 s[i] != s[j] 时,dp[i][j] = false 。

初始化

对于单个字符,即 i == j 时,dp[i][j] = true ,因为单个字符一定是回文串。

遍历顺序

由于状态转移方程依赖于 dp[i + 1][j - 1] ,所以我们需要按照子串长度从小到大的顺序进行遍历,即先遍历长度为 1 的子串,再遍历长度为 2 的子串,以此类推。

记录最长回文子串

在遍历过程中,记录下最长回文子串的起始位置和长度,最后根据这些信息截取最长回文子串。

时间复杂度:O(n^{2}),n 是字符串的长度

空间复杂度:O(n^{2})

class Solution {
public:string longestPalindrome(string s) {int n = s.length();if (n < 2) {return s;}// 初始化 dp 数组std::vector<std::vector<bool>> dp(n, std::vector<bool>(n, false));int start = 0;  // 最长回文子串的起始位置int maxLen = 1; // 最长回文子串的长度// 单个字符一定是回文串for (int i = 0; i < n; ++i) {dp[i][i] = true;}// 枚举子串长度for (int len = 2; len <= n; ++len) {// 枚举子串的起始位置for (int i = 0; i <= n - len; ++i) {int j = i + len - 1; // 子串的结束位置if (s[i] == s[j]) {if (len <= 2) {dp[i][j] = true;} else {dp[i][j] = dp[i + 1][j - 1];}} else {dp[i][j] = false;}// 更新最长回文子串的信息if (dp[i][j] && len > maxLen) {start = i;maxLen = len;}}}return s.substr(start, maxLen);}
};

中心扩展法

可以使用中心扩展法来找出字符串 s 中最长的回文子串。该方法的核心思想是,回文串具有对称性,因此可以以每个字符或者每两个相邻字符为中心,向两边扩展来判断是否构成回文串。

具体步骤如下:

  • 遍历字符串 s 中的每个字符,将其作为回文串的中心。
  • 对于每个中心,分别考虑两种情况:
    • 以单个字符为中心扩展,形成奇数长度的回文串。
    • 以两个相邻字符为中心扩展,形成偶数长度的回文串。
  • 在扩展过程中,不断比较左右字符是否相等,若相等则继续扩展,直到不相等为止。
  • 记录每次扩展得到的回文串的长度和起始位置,最终找出最长的回文子串。

时间复杂度:O(n^{2}),n 是字符串的长度

空间复杂度:O(1)

class Solution {
public:string longestPalindrome(string s) {if (s.empty()) return "";int start = 0, maxLen = 0;// 遍历字符串中的每个字符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 > maxLen) {maxLen = len;// 计算最长回文子串的起始位置start = i - (len - 1) / 2;}}// 截取最长回文子串return s.substr(start, maxLen);}private:// 中心扩展函数int expandAroundCenter(const string& s, int left, int right) {while (left >= 0 && right < s.length() && s[left] == s[right]) {--left;++right;}// 返回回文串的长度return right - left - 1;}
};    

相关文章:

LeetCode hot 100—最长回文子串

题目 给你一个字符串 s&#xff0c;找到 s 中最长的 回文 子串。 示例 示例 1&#xff1a; 输入&#xff1a;s "babad" 输出&#xff1a;"bab" 解释&#xff1a;"aba" 同样是符合题意的答案。示例 2&#xff1a; 输入&#xff1a;s "cb…...

蓝桥杯知识总结

文章目录 1.常用的数学方法2.大小写转换3.数组和集合排序数组排序集合排序 4.控制小数位数5.栈6.队列7.字符串相关方法8.十进制转n进制模板字符转为十进制某进制转化为十进制 9.前缀和10.差分11.离散化12.双指针13.二分14.枚举模板组合型枚举模板排列型枚举模板 15.搜索算法BFS…...

leetcode:2839. 判断通过操作能否让字符串相等 I(python3解法)

难度&#xff1a;简单 给你两个字符串 s1 和 s2 &#xff0c;两个字符串的长度都为 4 &#xff0c;且只包含 小写 英文字母。 你可以对两个字符串中的 任意一个 执行以下操作 任意 次&#xff1a; 选择两个下标 i 和 j 且满足 j - i 2 &#xff0c;然后 交换 这个字符串中两个…...

Python Lambda表达式详解

Python Lambda表达式详解 1. Lambda是什么&#xff1f; Lambda是Python中用于创建匿名函数&#xff08;没有名字的函数&#xff09;的关键字&#xff0c;核心特点是简洁。它适用于需要临时定义简单函数的场景&#xff0c;或直接作为参数传递给高阶函数&#xff08;如map()、f…...

Matlab 平衡车的建模与控制

1、内容简介 Matlab 189-平衡车的建模与控制 可以交流、咨询、答疑 2、内容说明 略 平衡车的建模与控制 选择一款平衡车&#xff08;如&#xff1a;小米九号平衡车等&#xff09;&#xff0c;并估计平衡车的关键参数。完成以下工作&#xff1a; 1. 建立平衡车模型&#xf…...

KWDB创作者计划—KWDB关系库与时序库混搭

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3; 作者&#xff1a;IT邦德 中国DBA联盟(ACDU)成员&#xff0c;10余年DBA工作经验 Oracle、PostgreSQL ACE CSDN博客专家及B站知名UP主&#xff0c;全网粉丝10万 擅长主流Oracle、MySQL、PG、高斯…...

Android studio2024的第一个安卓项目

目录 一、创建项目 1、创建Empty Views Activity类型项目 2、Android项目结构解析 manifests 目录&#xff1a; Gradle Scripts目录 3、创建安卓应用 二、测试 1、模拟器测试效果 2、连接真机&#xff0c;然后直接选择真机运行即可&#xff08;点击Run或Shift F10运行…...

航电系统之障碍物监测技术篇

航电系统的障碍物监测技术是保障飞行安全、提升飞行效率的核心技术之一&#xff0c;尤其在复杂环境和低空飞行中发挥着关键作用。以下从技术原理、传感器类型、数据处理与应用等方面进行系统介绍&#xff1a; 一、技术原理 航电系统的障碍物监测技术通过多传感器融合和智能算法…...

网站DDoS防护方案——构建企业级安全屏障的关键路径

本文深度解析DDoS攻击最新演变趋势与防御技术体系&#xff0c;通过攻击特征图谱、云原生防护架构、混合防御模型等维度&#xff0c;揭示企业级网站防护方案的设计逻辑。结合2023年金融行业千万级QPS攻击事件&#xff0c;引用Gartner最新防御技术成熟度曲线&#xff0c;给出可落…...

Linux系统使用lshw生成硬件报告方法

使用 lshw 生成 HTML 硬件报告指南 一、工具简介 lshw(List Hardware)是 Linux 系统下用于检测并报告硬件详细信息的命令行工具,支持输出多种格式(文本、HTML、XML 等)。 核心功能: 显示 CPU、内存、磁盘、PCI/USB 设备等完整硬件信息生成结构化报告,便于存档或分析支…...

力扣 905 按奇偶排序数组:双指针法的优雅实现

目录 问题背景 题目解析 解题思路 暴力解法 双指针法 代码实现 代码解析 算法效率 实际应用场景 总结 问题背景 在编程的世界里&#xff0c;数组排序问题一直是经典中的经典。今天我们要解决的是一个有趣的变种&#xff1a;按奇偶排序数组。题目要求我们将一个整数数…...

LeetCode hot 100—子集

题目 给你一个整数数组 nums &#xff0c;数组中的元素 互不相同 。返回该数组所有可能的子集&#xff08;幂集&#xff09;。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3] 输出&#xff1a;[[],[1],[2…...

BERT - BertTokenizer, BertModel API模型微调

本节代码将展示如何在预训练的BERT模型基础上进行微调&#xff0c;以适应特定的下游任务。 ⭐学习建议直接看文章最后的需复现代码&#xff0c;不懂得地方再回看 微调是自然语言处理中常见的方法&#xff0c;通过在预训练模型的基础上添加额外的层&#xff0c;并在特定任务的…...

通过代码获取接口文档工具

通过代码获取接口文档工具 介绍使用到的技术使用说明核心源码演示截图工具源码 介绍 1.通过前后端代码来生成规格化的接口文档 2.支持拖拽上传或点击选择文件&#xff0c;可以一次选择多个文件或选择文件夹 3.用户选择前后端代码&#xff0c;工具调用GPT解析&#xff0c;得到规…...

不再卡顿!如何根据使用需求挑选合适的电脑内存?

电脑运行内存多大合适&#xff1f;在选购或升级电脑时&#xff0c;除了关注处理器的速度、硬盘的容量之外&#xff0c;内存&#xff08;RAM&#xff09;的大小也是决定电脑性能的一个重要因素。但究竟电脑运行内存多大才合适呢&#xff1f;这篇文章将帮助你理解不同使用场景下适…...

leetcode589 N叉树的前序遍历

前序遍历的顺序是&#xff1a;根节点 -> 子节点1 -> 子节点2 -> ... -> 子节点N 递归&#xff1a; class Solution { private:void traverse(Node* cur, vector<int>& res){if(cur NULL) return;res.push_back(cur->val);for(Node* child: cur->…...

游戏引擎学习第216天

回顾并为当天做准备 你可以看到&#xff0c;游戏现在正在运行。如果我没记错的话&#xff0c;我们之前把调试系统关闭了&#xff0c;留下一个状态&#xff0c;让任何想要在这段时间内进行实验的人可以自由操作&#xff0c;因为我们还没有完全完成这个系统。所以这样做是为了确…...

JavaSE反射机制干货

1.反射(Relection) 理解 定义&#xff1a;程序运行状态,动态地获取程序信息及调用程序功能即为java反射机制 2.获取class对象 掌握 2.1 Java代码的3个阶段 Java代码在计算机中经历的三个阶段:Source源代码阶段-Class类对象阶段-Runt…...

[特殊字符] 第十一讲 | 空间回归模型实战:SAR / SEM / GWR逐个击破

&#x1f4d8; 专栏&#xff1a;科研统计方法实战分享 | 地学/农学人的数据分析工具箱 ✍️ 作者&#xff1a;平常心0715 &#x1f511; 本讲关键词&#xff1a;空间滞后模型&#xff08;SAR&#xff09;、空间误差模型&#xff08;SEM&#xff09;、地理加权回归&#xff08;G…...

AI前沿周报:2025年3月技术深度解析

以下是基于2024-2025年AI技术前沿动态的深度技术周报示例&#xff0c;结合行业最新突破与研究进展&#xff0c;突出技术原理与应用场景分析&#xff1a; AI前沿周报&#xff1a;2025年3月技术深度解析 时间范围&#xff1a;2025年3月1日-3月31日 本期焦点&#xff1a;模型透明…...

aidigu开源微博项目程序,PHP开发的开源微博系统,自媒体个人创业、网盘推广首先

一、软件介绍 文末提供程序和源码下载学习 PHP开发的开源微博系统&#xff0c;采用PHP MySQL开发&#xff0c;框架采用ThinkPHP5.1&#xff0c;用户登录后拥有专属ID&#xff0c;支持表情、关注用户&#xff0c;网盘分享等功能&#xff0c;支持图片上传,视频上传,网盘存储分享…...

Tabnet介绍(Decision Manifolds)和PyTorch TabNet之TabNetRegressor

Tabnet介绍(Decision Manifolds)和PyTorch TabNet之TabNetRegressor Decision ManifoldsTabNet1.核心思想2. 架构组成3. 工作流程4. 优点PyTorch TabNetTabNetRegressor参数1. 模型相关参数`n_d``n_a``n_steps``gamma``cat_idxs``cat_dims``cat_emb_dim`2. 训练相关参数`opti…...

格瑞普Tattu正式成为2025年中国无人机竞速联赛官方赞助商!

格瑞普Tattu正式成为2025年中国无人机竞速联赛官方赞助商! 为飞手赋能&#xff0c;为赛事护航! Tattu是深圳市格瑞普电池有限公司(Grepow)旗下的子品牌之一&#xff0c;专注为无人机、FPV和模型爱好者提供专业可靠的电池和充电器等一站式电源解决方案。凭借卓越的放电性能、稳…...

PySide6 监测设备变更事件

在PySide6中监听系统事件&#xff0c;判断是否有串口设备插拔&#xff0c;进而当串口状态变更时&#xff0c;实现列表数据实时更新。 在Qt中&#xff0c;可以使用 nativeEvent 接口来完成这一操作&#xff1a; [virtual protected] bool QWidget::nativeEvent(const QByteArray…...

嵌入式系统的历史与发展​

目录 引言​ 一、嵌入式系统的早期萌芽​ 1、首个现代嵌入式系统 2、早期未成形嵌入式系统的应用 二、以单片机为主的初级阶段​ 1、工业领域应用 2、大型家电领域应用 三、处理器升级与多样化应用阶段​ 1、数字化电子化设备涌现 &#xff08;1&#xff09;智能仪表…...

mysql调试记录

ALTER USER rootlocalhost IDENTIFIED WITH mysql_native_password BY password; 该命令在调试python使用pymysql连接数据库出现错误时&#xff0c; 报错为pymysql.err.OperationalError: (1045, "Access denied for user rootlocalhost (using password: NO)") m…...

【后端开发】Spring MVC阶段总结

文章目录 快捷引入依赖lombok的使用Lombok依赖Lombok使用Lombok注解 三层架构分层的目的MVC与分层的区别三层架构分层的好处 企业命名规范常见命名命名风格介绍大驼峰风格小驼峰风格包名 常见注解Cookie与Session 快捷引入依赖 这个方法可以快捷引入依赖&#xff0c;但是引入依…...

netty-socketio + springboot 消息推送服务

netty-socketio springboot 消息推送服务 后端1. 目录结构&#xff1a;代码pom文件&#xff1a;application.yml&#xff1a;SocketIOConfig&#xff1a;PushMessage&#xff1a;ISocketIOServiceSocketIOServiceImpl&#xff1a;pushMessageController&#xff1a;启动类&…...

基于 JavaWeb 的 SSM 在线视频教育系统设计和实现(源码+文档+部署讲解)

技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;免费功能设计、开题报告、任务书、中期检查PPT、系统功能实现、代码编写、论文编写和辅导、论文…...

同时打开多个Microchip MPLAB X IDE

0.引用 Microchip 32位MCU CAN驱动图文教程-附源码 - 哔哩哔哩 https://bbs.21ic.com/icview-3391426-1-1.html https://bbs.21ic.com/icview-3393632-1-1.html 1.前言 工作中接触到使用Microchip 的 MPLAB X IDE 开发工具&#xff0c;使用的MCU是Microchip SAMD21J18A MCU…...

dify 500错误

问题 升级到1.2.0 后所有页面接口均报错500, 环境&#xff1a; docker 本地部署 version:1.2.0 解决办法 1.首先关闭服务 docker compose down2.找到docker-compose.yaml里的plugin_daemon&#xff0c;参照下面修改参数 plugin_daemon:environment:PLUGIN_MAX_EXECUTION…...

WPF设计标准学习记录26

画刷名称功能说明SolidColorBrush使用单一的连续颜色填充区域LinearGradientBrush使用线性渐变绘制区域。RadialGradientBrush使用径向渐变绘制区域。 焦点定义渐变的开始,而圆定义渐变的终点。ImageBrush使用图像绘制区域。VisualBrush使用一个视图绘制区域。BitmapCacheBrus…...

cin,cin.get(),getchar(),getline(),cin.get line()异同点

文章目录 1.cin2.cin.get()3.getchar()4.cin.getline()5.getline() 1.cin &#xff08;1&#xff09;cin>>等价于cin.operator>>()&#xff0c;即调用成员函数operator>>()进行读取数据。 &#xff08;2&#xff09;当cin>>从缓冲区中读取数据时&…...

7# 5多线-7 不会停

7# 5多线-7 不会停 分析&#xff0c;明显线接错了&#xff0c;打自动时也能手动启停&#xff0c;打手动无法启停&#xff0c;这时远程只能启ka3,无法启ka4。排查手自转换2上没接线&#xff0c;接到8上了&#xff08;13和12接错了&#xff0c;也就是sac的5和6接错了&#xff09;…...

基于混合编码器和边缘引导的拉普拉斯金字塔网络用于遥感变化检测

Laplacian Pyramid Network With HybridEncoder and Edge Guidance for RemoteSensing Change Detection 0、摘要 遥感变化检测&#xff08;CD&#xff09;是观测和分析动态土地覆盖变化的一项关键任务。许多基于深度学习的CD方法表现出强大的性能&#xff0c;但它们的有效性…...

机器学习 从入门到精通 day_04

1. 决策树-分类 1.1 概念 1. 决策节点 通过条件判断而进行分支选择的节点。如&#xff1a;将某个样本中的属性值(特征值)与决策节点上的值进行比较&#xff0c;从而判断它的流向。 2. 叶子节点 没有子节点的节点&#xff0c;表示最终的决策结果。 3. 决策树的…...

CLAHE算法介绍

限制对比度自适应直方图增强 CLAHE 算法介绍 1. CLAHE算法框图2.直方图clip及重分配2.1 opencv自带2.2 scikit-image2.3 结果对比2.4 clip limit的性质3.插值参考文献上图来自 K. Zuiderveld: Contrast Limited Adaptive Histogram Equalization。 图中可以看到各种直方图均衡的…...

高并发的业务场景下,如何防止数据库事务死锁

一、 一致的锁定顺序 定义: 死锁的常见原因之一是不同的事务以不同的顺序获取锁。当多个事务获取了不同资源的锁,并且这些资源之间发生了互相依赖,就会形成死锁。 解决方法: 确保所有的事务在获取多个锁时,按照相同的顺序请求锁。例如,如果事务A需要锁定表A和表B,事务…...

使用Python从零实现一个端到端多模态 Transformer大模型

嘿&#xff0c;各位&#xff01;今天咱们要来一场超级酷炫的多模态 Transformer 冒险之旅&#xff01;想象一下&#xff0c;让一个模型既能看懂图片&#xff0c;又能理解文字&#xff0c;然后还能生成有趣的回答。听起来是不是很像超级英雄的超能力&#xff1f;别急&#xff0c…...

elestio memos SSRF漏洞复现(CVE-2025-22952)(附脚本)

免责申明: 本文所描述的漏洞及其复现步骤仅供网络安全研究与教育目的使用。任何人不得将本文提供的信息用于非法目的或未经授权的系统测试。作者不对任何由于使用本文信息而导致的直接或间接损害承担责任。如涉及侵权,请及时与我们联系,我们将尽快处理并删除相关内容。 前言…...

倚光科技:以创新之光,雕琢全球领先光学设计公司

在光学技术飞速发展的当下&#xff0c;每一次突破都可能为众多领域带来变革性的影响。而倚光&#xff08;深圳&#xff09;科技有限公司&#xff0c;作为光学设计公司的一颗璀璨之星&#xff0c;正以其卓越的创新能力和深厚的技术底蕴&#xff0c;引领着光学设计行业的发展潮流…...

Linux安装Elasticsearch详细教程

准备工作 下载地址:Download Elasticsearch | Elastic 下载时需要注意es与jdk版本对应关系 ES 7.x 及之前版本&#xff0c;选择 Java 8 ES 8.x 及之后版本&#xff0c;选择 Java 17 或者 Java 18&#xff0c;建议 Java 17&#xff0c;因为对应版本的 Logstash 不支持 Java 1…...

C++字符串操作详解

引言 字符串处理是编程中最常见的任务之一&#xff0c;而在C中&#xff0c;我们有多种处理字符串的方式。本文将详细介绍C中的字符串操作&#xff0c;包括C风格字符串和C的string类。无论你是C新手还是想巩固基础的老手&#xff0c;这篇文章都能帮你梳理字符串处理的关键知识点…...

PromptPro|提示词生成和管理专家

大家好&#xff0c;我是吾鳴。 今天吾鳴给大家分享一个实用的提示词管理网站&#xff0c;它的名称叫做产品化管理提示词&#xff0c;英文名叫做PromptPro&#xff0c;是一个可以帮你管理你的大模型提示词的网站&#xff0c;同时你也可以告诉它你的需求&#xff0c;让它帮你生成…...

计算机视觉图像特征提取入门:Harris角点与SIFT算法

计算机视觉图像特征提取入门&#xff1a;Harris角点与SIFT算法 一、前言二、Harris 角点检测算法​2.1 Harris 角点的定义与直观理解​2.1.1 角点的概念​2.1.2 Harris 角点的判定依据​ 2.2 Harris 角点检测的实现步骤​2.2.1 计算图像的梯度​2.2.2 构建结构张量矩阵​2.2.3 …...

swift菜鸟教程1-5(语法,变量,类型,常量,字面量)

一个朴实无华的目录 今日学习内容&#xff1a;1.基本语法引入空格规范输入输出 2.变量声明变量变量输出加反斜杠括号 \\( ) 3.可选(Optionals)类型可选类型强制解析可选绑定 4.常量常量声明常量命名 5.字面量整数 and 浮点数 实例字符串 实例 今日学习内容&#xff1a; 1.基本…...

02142数据结构导论

初学者&#xff0c;怎样理解这道题&#xff0c;怎样大白话分析 答案解析 00、概念 29、 28、 27、 26、 25、 24、 23、 22、有5个元素&#xff0c;其入栈次序为&#xff1a;A、B、C、D、E,写出以元素C、D最先出栈(即C第一个且D第二个出栈)的各种可能的出栈次序。 (来…...

如何在AMD MI300X 服务器上部署 DeepSeek R1模型?

DeepSeek-R1凭借其深度推理能力备受关注&#xff0c;在语言模型性能基准测试中可与顶级闭源模型匹敌。 AMD Instinct MI300X GPU可在单节点上高效运行新发布的DeepSeek-R1和V3模型。 用户通过SGLang优化&#xff0c;将MI300X的性能提升至初始版本的4倍&#xff0c;且更多优化将…...

【Django】教程-15-注册页面

【Django】教程-1-安装创建项目目录结构介绍 【Django】教程-2-前端-目录结构介绍 【Django】教程-3-数据库相关介绍 【Django】教程-4-一个增删改查的Demo 【Django】教程-5-ModelForm增删改查规则校验【正则钩子函数】 【Django】教程-6-搜索框-条件查询前后端 【Django】教程…...

OpenAI即将上线新一代重磅选手——GPT-4.1

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...