算法-字符串-5.最长回文子串

一、题目:

二、思路解析 

        1.思路:

                最长子串——动态数组

        2.常用方法:

                a.字符串的截断

res=s.substring(start,end+1);

        3.核心逻辑:

                1.特殊情况:字符串为空或字符串的长度为0

if(s==null||s.length())return "";

                2.一般情况:

                       (1) 采用滑动窗口方法:

                                要素:

                                        a.子串长度,即窗口len

                                        b.窗口开始,start<=size-len

                                        c.窗口结束,end=len+start-1;

                       (2)讨论

                                a.当窗口长度为1,即len==1时,此时该窗口范围的子串都是回文子串

if(len==1){dp[start][end]=true;
}

                              b.当窗口长度不为1时

                                        len==2:只需判断两个字符是否相等即可判断是否为会为子串

                                        len>2:除了要判断首尾字符是否相等外,还需要判断除去首尾的子串是否为回文子串

if(len==2&&s.charAt(start)==s.charAt(end)){dp[start][end]=true;
}else if(s.charAt(start)==s.charAt(end)&&dp[start+1][end-1]){dp[start][end]=true;
}else{dp[start][end]=false;
}

简化版:

if(s.charAt(start)==s.charAt(end)&&(len==2||dp[start+1][end-1])){dp[start][end]=true;}else{dp[start][end]=false;}

 

 三、代码实现    

class Solution {public String longestPalindrome(String s) {if(s==null||s.length()==0)return "";int size=s.length();String res="";boolean[][]dp=new boolean[size][size];for(int len=1;len<=size;len++){for(int start=0;start<=size-len;start++){int end=start+len-1;if(len==1){dp[start][end]=true;}else if(len==2&&s.charAt(start)==s.charAt(end)){dp[start][end]=true;}else {dp[start][end]=s.charAt(start)==s.charAt(end)&&dp[start+1][end-1];}if(dp[start][end]&&len>res.length()){res=s.substring(start,end+1);;}}}return res;}
}

 

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

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

相关文章

【3D AIGC】Img-to-3D、Text-to-3D、稀疏重建(2024年文章汇总)

文章目录 1. Wonderworld&#xff1a;拓展图片边界&#xff0c;生成3D场景2. 3DTopia-XL&#xff1a;扩散模型辅助生成3. 3DGS-Enhancer: 通过视图一致2D Diffusion&#xff0c;提升无界3D Gaussian Splatting (NlPs2024 Spotlight)4. L3DG&#xff1a;Latent 3D Gaussian Diff…

基于图神经网络的个性化医疗决策算法研究:结合GNN与MSF-CNN,实现95.21%诊断准确率的个性化医疗方案

基于图神经网络的个性化医疗决策算法研究&#xff1a;结合GNN与MSF-CNN&#xff0c;实现95.21%诊断准确率的个性化医疗方案 论文大纲理解要点1. 确认目标2. 问题分解基础问题层技术问题层 3. 实现步骤4. 效果展示5. 金手指分析应用案例&#xff1a; 全流程分析多题一解分析一题…

C语言(一维数组练习)

键盘录入一组数列&#xff0c;利用冒泡排序将数据由大到小排序 #include <stdio.h>int main(int argc,char *argv[]) {int i,j,tmep;int arr[10];printf("请输入10个测试整数&#xff1a;\n");int lensizeof(arr)/sizeof(arr[0]);for(i0;i<len;i){scanf(&q…

webpack 题目

文章目录 webpack 中 chunkHash 和 contentHash 的区别loader和plugin的区别&#xff1f;webpack 处理 image 是用哪个 loader&#xff0c;限制 image 大小的是...&#xff1b;webpack 如何优化打包速度 webpack 中 chunkHash 和 contentHash 的区别 主要从四方面来讲一下区别&…

银行项目网上支付接口调用测试实例

&#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 公司最近有一个网站商城项目要开始开发了&#xff0c;这几天老板和几个同事一起开着需求会议&#xff0c;讨论了接下来的业务规划和需求策略&#xff0c;等技术需求…

软体机器人动态手内笔旋转研究

人工智能咨询培训老师叶梓 转载标明出处 软体机器人因其在安全互动方面的优势而备受关注&#xff0c;但在高速动态任务中却面临挑战。最近&#xff0c;卡内基梅隆大学机器人研究所的研究团队提出了一种名为SWIFT的系统&#xff0c;旨在通过学习和试错来实现软体机器人手的动态…

Spark实训

实训目的: 介绍本实训的基本内容,描述知识目标、,以及本实训的预期效果等。 1、知识目标 (1)了解spark概念、基础知识、spark处理的全周期,了解spark技术是新时代对人才的新要求。 (2)掌握Linux、hadoop、spark、hive集群环境的搭建、HDFS分布文件系统的基础知识与应用…

二叉树的深搜(不定期更新。。。。。)

二叉树的深搜 验证二叉搜索树 给你一个二叉树的根节点 root &#xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下&#xff1a; 节点的左 子树 只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉…

# 深入浅出 快速认识JAVA常用数据结构【栈, 队列, 链表, 数组】

快速认识JAVA常用数据结构【栈, 队列, 链表】 前言 什么是数据结构 一种用来存储和组织数据的方法&#xff0c;描述了数据之间的关系和操作方式。通过合理选择和使用数据结构&#xff0c;可以大幅提高程序的运行效率、存储效率以及代码可维护性。 数据结构的重要性 数据结构…

负载均衡OJ项目中遇到的问题

1、续行符问题 关于换行符 &#xff0c;代码在使用了换行符后无法编译文件&#xff0c;也没有爆出任何错误&#xff0c;更没有按照我们的代码打印出如下类似内容 &#xff1a;[ERROR][compiler.hpp][66][1732635247]编译失败,没有形成可执行程序 随机排查才发现。 代码中的 \ …

android编译assets集成某文件太大更新导致git仓库变大

不知道大家有没有类似的困扰&#xff0c;你的工程assets文件过大&#xff0c;我曾经在某度车机地图团队工作过一段时间时候&#xff0c;每次发包会集成一个上百MB的文件。工作一段时间你的git仓库将会增加特别多。最后&#xff0c;你会发现你如果重新git clone这个仓库会非常大…

关闭windows11的“热门搜索”

win10搜索栏热门搜索怎么关闭&#xff1f;win10搜索栏热门搜索关闭方法分享_搜索_onecdll-GitCode 开源社区 注册表地址是&#xff1a;计算机\HKEY_CURRENT_USER\SOFTWARE\Policies\Microsoft\Windows\ 最后效果如下&#xff1a;

【数字电路与逻辑设计】实验五 4人表决器

文章总览&#xff1a;YuanDaiMa2048博客文章总览 【数字电路与逻辑设计】实验五 4人表决器 一、实验内容二、设计过程&#xff08;一&#xff09;设置变量&#xff08;二&#xff09;真值表&#xff08;三&#xff09;表达式 三、源代码&#xff08;一&#xff09;代码说明&…

Yeeco成长型一体化数智赋能平台:科技矩阵重塑企业数字生态

随着科技的飞速发展&#xff0c;我们正在步入一个被称为“数智化时代”的新时代。在这个时代中&#xff0c;数据处理和分析的能力被提升到一个前所未有的高度&#xff0c;而这种变化背后的重要推动力量就是各种新兴的技术趋势。 为了在激烈的市场竞争中脱颖而出&#xff0c;Yee…

PlantUML——类图

背景 类图是UML模型中的静态视图&#xff0c;其主要作用包括&#xff1a; 描述系统的结构化设计&#xff0c;显示出类、接口以及它们之间的静态结构和关系。简化对系统的理解&#xff0c;是系统分析与设计阶段的重要产物&#xff0c;也是系统编码和测试的重要模型依据。 在U…

LabVIEW热阻炉温度控制

在工业自动化和控制系统领域&#xff0c;温度的精确控制对于保障生产过程的稳定性和产品质量非常重要。热阻炉作为一个典型的受控对象&#xff0c;其温度控制系统的设计和实现涉及多个技术层面&#xff0c;包括硬件选择、控制策略的设计以及软件的实现。项目使用LabVIEW软件开发…

MongoDB在自动化设备上的应用示例

发现MongoDB特别适合自动化检测数据的存储。。。 例如一个晶圆检测项目&#xff0c;定义其数据结构如下 #pragma once #include <vector> #include <QString> #include <QRectF> #include <string> #include <memory>class tpoWafer; class tp…

day04-产品原型-学习计划

1. 分析整体业务流程 2. 提交学习记录-接口 2.1 需求 在课程学习页面播放视频时或考试后&#xff0c;需要提交学习记录到服务器保存&#xff0c;如用户播放视频的进度、学过的章节等。 2.1 接口详情 请求方式&#xff1a;POST 请求路径&#xff1a;/learning-record 请求…

基于Matlab的卷积神经网络(CNN)苹果分级检测系统

本研究提出了一种基于卷积神经网络&#xff08;CNN&#xff09;的自动化苹果分级系统&#xff0c;该系统根据苹果的视觉特征进行分类。系统采用了预训练的深度学习模型&#xff0c;使用包含不同等级苹果的图像数据集进行训练。研究方法包括图像预处理、特征提取和苹果等级分类。…