leetcode-5-最长回文子串

题解:

回文串:如果一个字符串正着读和反着读都是一样的那这个字符串就是回文串。

对于一个子串而言,如果它是回文串,并且长度大于 2,那么将它首尾的两个字母去除之后,它仍然是个回文串。

1、初始化字典dic_len={}记录回文子串及其长度。其key值代表回文子串的长度,value值代表回文子串;

2、初始化长度为n*n的二维数组dp用来表示子串是否是回文串;由于左边界一定小于或等于右边界,所以只需要对dp的上三角进行赋值。按照下图红色箭头方向进行赋值;

3、dp[i][j]==True代表左边界为i右边界为j的子串是回文串;dp[i][j]==False代表左边界为i右边界为j的子串不是回文串;

4、使用双层for循环对dp[i][j]赋值(其中j>=i);(具体赋值步骤见步骤8)

5、当s[i]!=s[j]时,则dp[i][j]不是回文串直接将dp[i][j]赋值为False;

6、当s[i]==s[j]时,分两种情况:

(1)当子串的长度小于等于3即j-i<3时,子串肯定是回文串则dp[i][j]==True;

 (2)当子串的长度大于3时即j-i>=3时,子串是否为回文串取决于dp[i+1][j-1]即dp[i][j]=dp[i+1][j-1];

7、如果dp[i][j]==True,则更新dic_len的key值为j-i+1,对应的value值为s[i,j+1];

8、循环结束后返回dic_len的最大key对应的value。

9、根据步骤6中的第(2)种情况,所以按照图中箭头的方向依次对dp进行赋值即在j固定的情况下依次增大i且使i<==j对dp进行赋值。使用如下循环模板实现:

 for j in range(n):

        for  i in range(j+1):

                dp[i][j]="XXXXX"

下图:

dp[0][3]的计算逻辑:在s[0]!=s[3],dp[0][3]=False;

dp[0][4]的计算逻辑:在s[0]==s[4]时,子串长度大于3则dp[0][4]=dp[1][3];

dp[1][4]的计算逻辑:在s[1]!=s[4]时,dp[1][4]=False;

核心:使用动态规划解题,动态规划方程如下:

代码:

参考:leetcode-131-分割回文串

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/465516.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python反射API:面向对象编程的“魔法镜”

在Python的世界里&#xff0c;面向对象编程&#xff08;OOP&#xff09;就像是一场盛大的化妆舞会&#xff0c;每个对象都穿着华丽的外衣&#xff0c;隐藏着自己的真实面目。而Python的反射API&#xff0c;就像是一面“魔法镜”&#xff0c;能够让我们窥探这些对象的真实身份和…

Python练习8

Python日常练习 题目&#xff1a; 编写函数&#xff0c;接收两个正整数作为参数&#xff0c;返回一个元组&#xff0c; 其中第一个元数为最大公约数&#xff0c;第二个元素为最小公倍数。 例如&#xff1a; 若输入12&#xff0c;8&#xff0c;则输出如下 【请输入一个…

推荐程序员好用的浏览器插件

推荐程序员好用的浏览器插件 1. 网页颜色控制&#xff1a;Dark Reader安装效果 2. 前端助手&#xff1a;FeHelper安装效果 3. markdown可视化&#xff1a;Markdown Reader安装效果 4. ES插件&#xff1a;Multi Elasticsearch Heads安装效果 1. 网页颜色控制&#xff1a;Dark Re…

希尔排序算法

1、基本思想 希尔排序也称缩小增量排序&#xff0c;是插入排序的一种更高效的改进版本。它的基本思想是先将待排序的数组元素按照一定的间隔&#xff08;称为增量&#xff09;分成若干个子序列&#xff0c;分别对这些子序列进行插入排序&#xff0c;随着迭代的进行&#xff0c;…

太速科技-634-基于3U PXIe的VU3P FMC+数据接口板

基于3U PXIe的VU3P FMC数据接口板 一、产品概述 板卡是一款基于 3U PXIE 总线架构的高性能数据预处理FMC 载板&#xff0c;具有 1 个 FMC&#xff08;HPC&#xff09;接口&#xff0c;1 个 X8 GTH 背板互联接口&#xff0c;可以实现 1 路 PCIe x8。板卡主控芯片采用Xilin…

OpenCV基本操作(python开发)——(8)实现芯片瑕疵检测

OpenCV基本操作&#xff08;python开发&#xff09;——&#xff08;1&#xff09; 读取图像、保存图像 OpenCV基本操作&#xff08;python开发&#xff09;——&#xff08;2&#xff09;图像色彩操作 OpenCV基本操作&#xff08;python开发&#xff09;——&#xff08;3&…

MySQL数据库中的视图

视图 ​ 本篇将开始介绍有关数据库中视图的相关知识点&#xff0c;其中主要包含视图的基本使用&#xff0c;视图规则和限制。 ​ 视图是一个虚拟表&#xff0c;其内容由查询定义。同真实的表一样&#xff0c;视图包含一系列带有名称的列和行数据&#xff0c;视图的数据变化会…

Docker 镜像拉不动?自建 Docker Hub 加速站 解决镜像拉取失败

本文首发于只抄博客&#xff0c;欢迎点击原文链接了解更多内容。 前言 众所周知&#xff0c;6 月份的时候&#xff0c;Docker Hub 的镜像就已经无法正常拉取&#xff0c;那会随手用 Nginx 反代了一下 Docker Hub&#xff0c;建了个自用的镜像站&#xff0c;一直用到了 9 月份&…

应对传统能源企业管理人员青黄不接问题:搭建系统完善的招聘管理体系

应对传统能源企业管理人员青黄不接问题&#xff1a;搭建系统完善的招聘管理体系 对于很多传统能源企业由于成立时间久&#xff0c;发展到现在&#xff0c;往往都面临着一个共性问题&#xff0c;即未来三到五年&#xff0c;老员工退休后&#xff0c;新员工如何接续的问题。这个…

C++进阶-->红黑树的实现

1、红黑树的概念 红黑树是一棵二叉搜索树&#xff0c;他和前面AVL树不同的是红黑树不是通过平衡因子来保证树的平衡&#xff0c;而是在树结点的处加多了个记录颜色的变量&#xff0c;这个变量可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束&…

Linux操作系统开机引导

linux操作系统的开机引导的过程 linux操作系统开机流程图 1、开机自检&#xff1a;根据bios的设置&#xff0c;对cpu、内存、显卡、键盘等设备进行初步检测&#xff0c;如果以上检测设备正常工作&#xff0c;系统会把控制权移交到硬盘 总结&#xff1a;检测包含系统启动操作系…

DataX 的安装配置和使用 (详细版)

1&#xff0c;上传解压 1&#xff0c;开始上传安装包到你虚拟机上放置安装包的文件夹 2&#xff0c;开始解压 ,配置环境变量 1、上传 /opt/modules 2、解压 tar -zxvf datax.tar.gz -C /opt/installs 3、修改 vi /etc/profile 配置环境变量&#xff1a; export DAT…

蓝桥杯第21场小白入门赛补题

5.蓝桥派对 思路 &#xff1a;一个区间与多少个其他区间有关联&#xff0c;先对所有区间左端点和右端点从小到大排序&#xff0c;对于每个询问&#xff0c;我们先算出[1,r]这个区间里有多少个区间的起点即区间总数&#xff0c;使用upper_bound函数&#xff0c;然后使用lower_bo…

Linux篇(常见入门命令)

目录 一、开启终端 二、Linux命令格式 1. 什么是Linux 的命令&#xff1f; 三、Linux下的命令补全 四、切换用户 五、uname&#xff1a;查看操作系统信息 六、ls&#xff1a;查看目录下文件 1. 用法一 2. 用法二 3. 用法三 七、pwd&#xff1a;显示当前路径 八、cd&…

7.qsqlquerymodel 与 qtableview使用

目录 qtableview 委托QStyledItemDelegateQAbstractItemDelegateCheckBoxItemDelegate使用 qtableview 委托 //设置单元格委托 void setItemDelegate(QAbstractItemDelegate *delegate); QAbstractItemDelegate *itemDelegate() const;//设置列委托 void setItemDelegateForCol…

AMD显卡低负载看视频掉驱动(chrome edge浏览器) 高负载玩游戏却稳定 解决方法——关闭MPO

2024.11.6更新 关闭MPO有点用但是还是驱动掉到恶心&#xff0c;找到终极方法了视频输出直接插主板走核显&#xff0c;稳得一笔&#xff0c;3dmark跑了个分几乎没变化。核显负责桌面浏览器&#xff0c;独显就专心只跑游戏。等24.11驱动再看看 问题 折磨的开始是天下苦黄狗久矣&…

VS2022远程连接调试编译Linux环境下的C++代码

工具&#xff1a;VS2022 虚拟机&#xff1a;RHEL 8.0 一、下载必要工具 1.VS2022组件安装 打开VS2022Installer&#xff0c;点击修改下载必要工具。 选择Linux 和嵌入式开发&#xff0c;然后点击右下角的修改&#xff01; 等待安装........ 安装完成后&#xff0c;创建Linu…

AI笔筒操作说明及应用场景

AI笔筒由来&#xff1a; 在快节奏的现代办公环境中&#xff0c;我们一直在寻找既能提升效率、增添便利&#xff0c;又能融入企业文化、展现个人品味的桌面伙伴。为此&#xff0c;我们特推出专为追求卓越、注重细节的您设计的AI笔筒礼品版&#xff0c;它集高科技与实用性于一身…

爱普生 SG–WriterⅡ 石英可编程手工烧录器

在电子制造与研发的复杂世界中&#xff0c;爱普生 SG–WriterⅡ 石英可编程手工烧录器犹如一把神奇的钥匙&#xff0c;开启了石英晶振编程的无限可能&#xff0c;为众多领域的电子设备注入了精准与稳定的灵魂。 作为手工烧录器&#xff0c;SG–WriterⅡ 独具特色。在当今多样化…

数据库->索引

目录 一、索引是什么 二、索引的数据结构 1.HASH 2.二叉搜索树 3.N叉树(B树) 4.B树 5.B树与B树的区别 三、MYSQL的页 1.页文件头与页文件尾 2.页主体 3.页目录 4.数据页头 四、B在MYSQL索引中的应用 1.应用 2.计算三层树⾼的B树可以存放多少条记录 五、索引分类…