最长回文子串
问题
给你一个字符串 s
,找到 s
中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
示例 1:
输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd" 输出:"bb"
提示:
1 <= s.length <= 1000
s
仅由数字和英文字母组成
题解
方法1:动态规划
对于一个子串而言,如果它是回文串,并且长度大于 222,那么将它首尾的两个字母去除之后,它仍然是个回文串。例如对于字符串 “ababa”,如果我们已经知道 “bab” 是回文串,那么 “ababa” 一定是回文串,这是因为它的首尾两个字母都是“a”。
那么我们就可以写出动态规划的状态转移方程:
![]() | if len(s)<=2 |
| else |
中心扩展算法
- 确定中心回文子:P(i,j)中心子串是指长度大于等于1的相同字符组成的子串,例如“bab”的“a”,“baab”的“aa”,“baaab”的“aaa”等
- 从每一种边界情况开始「扩展」,也可以得出所有的状态对应的答案。
class Solution:def longestPalindrome(self, s: str) -> str:max_longest=0max_longest_s=""s_len=len(s)longest=[[0]*s_len for _ in range(s_len)]for i in range(s_len):longest[i][i] = 1left_i,right_i=i-1,i+1while right_i<s_len and s[i]==s[right_i]:longest[i][right_i]=1right_i+=1while left_i>=0 and right_i<s_len:if s[left_i]==s[right_i]:longest[i][right_i] = 1longest[i][left_i] = 1left_i-=1right_i+=1else:breakif right_i-1-left_i-1+1>max_longest:max_longest_s=s[left_i+1:right_i]max_longest=right_i-1-left_i-1+1# print(longest,max_longest_s)return max_longest_s
方法2 Manacher算法
请自学
相关文章:

最长回文子串
问题 给你一个字符串 s,找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。 示例 1: 输入:s "babad" 输出:"bab" 解释:"aba" 同…...

从瀑布模式到水母模式:ChatGPT引领软件研发的革新之路
ChatGPT引领软件研发的革新之路 概述操作建议本书优势 内容简介作者简介专家推荐读者对象目录直播预告写在末尾: 主页传送门:📀 传送 概述 计算机技术的发展和互联网的普及,使信息处理和传输变得更加高效,极大地改变了…...

一种使用wireshark快速分析抓包文件amr音频流的思路方法
解决方案: 1. 使用wireshark过滤amr,并导出原始数据文件; 2.使用ue的二进制编辑模式,编辑该文件,添加amr头,6个字节数据“#!AMR”,字节数据为 23 21 41 4D 52 0A 3.修正格式:通过抓包发现&#…...

银河麒麟x86版、银河麒麟arm版操作系统编译zlmediakit
脚本 # 安装依赖 gcc-c.x86_64 这个不加的话会有问题 sudo yum -y install gcc gcc-c libssl-dev libsdl-dev libavcodec-dev libavutil-dev ffmpeg git openssl-devel gcc-c.x86_64mkdir -p /home/zenglg cd /home/zenglg git clone --depth 1 https://gitee.com/xia-chu…...
InnoDB - 双写机制
双写机制用于提高数据持久性和可靠性。 双写机制的核心思想是,将写操作先写入一个临时缓冲区,然后再写入实际的数据文件。这个临时缓冲区通常是固定大小的内存缓冲区,称为双写缓冲。这个机制的主要目的是避免数据文件在写入时出现损坏或数据…...

【蓝桥杯选拔赛真题08】C++最大值最小值平均值 青少年组蓝桥杯C++选拔赛真题 STEMA比赛真题解析
目录 C/C++最大值最小值平均值 一、题目要求 1、编程实现 2、输入输出 二、算法分析</...
软考高级系统架构设计师系列之:系统开发基础知识、项目管理、信息安全和网络安全、计算机网络章节选择题详解
软考高级系统架构设计师系列之:系统开发基础知识、项目管理、信息安全和网络安全、计算机网络章节选择题详解 一、产品配置二、需求管理三、需求跟踪四、软件生命周期五、RUP六、耦合与内聚七、软件文档八、软件需求九、软件活动十、项目时间管理十一、需求管理十二、项目范围…...

0基础学习PyFlink——时间滑动窗口(Sliding Time Windows)
在《0基础学习PyFlink——时间滚动窗口(Tumbling Time Windows)》我们介绍了不会有重复数据的时间滚动窗口。本节我们将介绍存在重复计算数据的时间滑动窗口。 关于滑动窗口,可以先看下《0基础学习PyFlink——个数滑动窗口(Sliding Count Windows&#x…...

API安全之《大话:API的前世今生》
写在前面:本文结合API使用的业界现状,系统性地阐述API的基本概念、发展历史、表现形式等基础内容,主要包含以下内容: 1.什么是API 2.API的发展历史 3.现代API常用消息格式 4.top N 互联网企业API 使用现状 当前的世界是一个信…...
H5或者Vue实现二维码识别
前言 1、扫码识别库采用开源的zxing/library 2、支持js,Vue,lit等实现 原文章地址和代码仓库地址 1、在界面创建video标签用来显示摄像头内容 <!-- 视区 --><!-- lit写法 --> <video ${ref(this.videoRef)} class"xy-scan-wrap…...

stm32整理(三)ADC
1 ADC简介 1.1 ADC 简介 12 位 ADC 是逐次趋近型模数转换器。它具有多达 19 个复用通道,可测量来自 16 个外部 源、两个内部源和 VBAT 通道的信号。这些通道的 A/D 转换可在单次、连续、扫描或不连续 采样模式下进行。ADC 的结果存储在一个左对齐或右对齐的 16 位…...

Redis-持久化+主从架构
文章目录 Redis的持久化RDB模式异步持久化的实现AOF模式总结 Redis的主从架构1.端口以及文件调试测试2.主从配置3.数据同步原理(第一次同步为全局同步)4.增量同步5.主从配置优化6.问:master主机怎么判断从机slave是不是第一次同步数据? Redis…...

STM32H750之FreeRTOS学习--------(四)中断管理
四、FreeRTOS中断管理 中断的概念不再过多叙述,学习过逻辑的都知道 中断的执行过程 中断请求 外设产生中断请求(GPIO外部中断、定时器中断等)响应中断 CPU停止执行当前程序,转而去执行中断处理程序(ISR)…...

Macroscope安全漏洞检测工具简介
学习目标: 本介绍旨在帮助感兴趣者尽快了解 Macroscope,这是一款用于安全测试自动化和漏洞管理的企业工具。 全覆盖应用程序安全测试: 如下图所示,如果使用多种互补工具(SAST/DAST/SCA 等)来检测应用程序…...

【Linux】Nignx的入门使用负载均衡动静分离(前后端项目部署)---超详细
一,Nignx入门 1.1 Nignx是什么 Nginx是一个高性能的开源Web服务器和反向代理服务器。它使用事件驱动的异步框架,可同时处理大量请求,支持负载均衡、反向代理、HTTP缓存等常见Web服务场景。Nginx可以作为一个前端的Web服务器,也可…...

【入门Flink】- 04Flink部署模式和运行模式【偏概念】
部署模式 在一些应用场景中,对于集群资源分配和占用的方式,可能会有特定的需求。Flink为各种场景提供了不同的部署模式,主要有以下三种:会话模式(Session Mode)、单作业模式(Per-Job Mode&…...
react面试要点
# React面试知识点 ## React是什么?谈一谈你对react的理解 1 React是一个网页UI库 2 react的特点是 声明式 组件化 通用性 3 react优点: 简单,低耦合高内聚,由于虚拟dom概念,可以做到一次学习到处使用。 …...

在Google Kubernetes集群创建分布式Jenkins(一)
因为项目需要,在GKE的集群上需要创建一个CICD的环境,记录一下安装部署一个分布式Jenkins集群的过程。 分布式Jenkins由一个主服务器和多个Agent组成,Agent可以执行主服务器分派的任务。如下图所示: 如上图,Jenkins Ag…...

【Python全栈_公开课学习记录】
一、初识python (一).Python起源 Python创始人为吉多范罗苏姆(荷兰),Python崇尚优美、清晰、简明的编辑风格。Python语言结构清晰简单、数据库丰富、运行成熟稳定,科学计算统计分析领先。目前广泛应用于云计算、Web开发、科学运算…...

uniapp循环列表单选框实现单选
目录 图片源码参考最后 图片 源码 参考 大佬 最后 感觉文章好的话记得点个心心和关注和收藏,有错的地方麻烦指正一下,如果需要转载,请标明出处,多谢!!!...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...

跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...

HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...

沙箱虚拟化技术虚拟机容器之间的关系详解
问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西,但是如果把三者放在一起,它们之间到底什么关系?又有什么联系呢?我不是很明白!!! 就比如说: 沙箱&#…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践
在 Kubernetes 集群中,如何在保障应用高可用的同时有效地管理资源,一直是运维人员和开发者关注的重点。随着微服务架构的普及,集群内各个服务的负载波动日趋明显,传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...
人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型
在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重,适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解,并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...

DAY 45 超大力王爱学Python
来自超大力王的友情提示:在用tensordoard的时候一定一定要用绝对位置,例如:tensorboard --logdir"D:\代码\archive (1)\runs\cifar10_mlp_experiment_2" 不然读取不了数据 知识点回顾: tensorboard的发展历史和原理tens…...