Java练习—-》求字符串中的最长回文子串

Java练习—-》求字符串中的最长回文子串手贱,做了一道对于我来说挺难的题目嘿嘿!挺有意思的,分享一下文章目录前言一,题目二,思路图形解析代码前言第一次把自己的解题思维写出来,可能写的不太好,请给位原谅,哈哈哈哈额,如果有错的,请各位大佬帮我指出来哈,谢谢!!(^U^)ノ~YO一,题目求一串字符串的最长回文子串,这里以cabacabae为例二,思路图形解析第一步:观察这串字符串—》第二步:找出最长回文子串,并设数—》说明:在这里,假设知道最长回文子串,那这里的resCenter和maxRigth,reslengthgs

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

手贱,做了一道对于我来说挺难的题目
嘿嘿!
挺有意思的,分享一下
请添加图片描述

前言

第一次把自己的解题思维写出来,可能写的不太好,请给位原谅,哈哈哈哈额,如果有错的,请各位大佬帮我指出来哈,谢谢!!(^U^)ノ~YO
请添加图片描述

一,题目

求一串字符串的最长回文子串,这里以cabacabae为例

二,思路图形解析

第一步:观察这串字符串—》
在这里插入图片描述
第二步:找出最长回文子串,并设数—》
在这里插入图片描述
说明:在这里,假设知道最长回文子串,那这里的resCenter和maxRigth,reslengthgs和maxRight都是固定的了,但是实际上我们不知道,所以这里说它是动态的。
第三步:假设我们不知道最长回文子串的情况下—-》
在这里插入图片描述
这里我举了个例子,resCenter是从左到右走的,同样我们可以观察到有对称的j,也就是在一个对称范围内左边和右边是一样的。
所以resCenter有3中情况:
第四步:
在这里插入图片描述
在这一步,只是知道resLength的范围内部分,其他不在这范围内的我们不知道,所以只能一步一步对比

第五步:
在这里插入图片描述
此时左边的resCenter和j的resLength相等,为1.
第六步:
在这里插入图片描述
可以看出此时的resCenter到最左边界的长度为6,设下标为1的元素为x,下标为9的元素为y,此时数组b中的b[x]==b[y],设下表为17的元素为z,那么从上面几种情况判断以及j的位置,有b[x]!= b[z],所以b[y]!=b[z]。

注意:上面图中的resCenter的痕迹和j的痕迹是一致的,我这样比较好看出来两者的对称关系。所以,这里设出来的所有参数的每次移动的位置只有一个,j只是我画比较好理解的,,不要理解错了哈!嘻嘻~~
你也可以理解为一根绳子,找到对称点,阶段之后,再找对称点,从对称点(每一点都可以理解为对称点)开始,对比对称点前后是否是一样的,一样的则继续,遇到粗细不一样的就停止,这就相当于一个回文,记录下来,然后又继续…直到到最后一个。
所以这里需要重头开始,那时间复杂度就是o(n),空间复杂度就是o(1)。
(不想改图了,那个resLength的长度是动态的,因为在这之前我们是不知道最长回文子串的,但是我们可以假设,上面图没有交代,哈哈哈额)

代码

所以,根据上面的分析,我们如果限定了maxRigth和j的位置,那不就可以分析各种情况了嘛!因为maxRigth和j的范围不同,其他的也会不同,所以有以下代码—-》
在这里插入图片描述

在这里插入图片描述
重点部分分析:假设我们知道了最长的回文子串,那么resCenter则确定了,resLength也就确定了,同样maxRigth和maxCenter也确定了。那么在没确定之前,我们可以观察到在待定的最长回文子串中,resCenter的变化和j的变化是一样的,那我们可以用j来表示,其实resCenter 向后走的时候,也就是j。所以我们可以在j到maxRigth之内找到其元素的回文。那么在maxRigth之外的,我们有所不知,需要一个一个的去配对,同时在这里我们需要注意数组越界问题,所以要限定边界。在最左边界为j-c[j],肯定要大于等于0;最右边界为j+c[j]【这里的数组c[j]表示的是b[i]为中心的回文子串的半径】,就要小于length,同时因为在整个字符数组都左右的最后一个元素都是“#”,所以最左边界的值和最右边界的值是相等的,这个一定要限定!!。如果右边界越界了,那就更新一下maxRigth和maxCenter就可以了。
写代码的方式有很多种,也可以不这样写
ヽ( ̄ω ̄( ̄ω ̄〃)ゝ
请添加图片描述

应该就这样了吧,不知道有没有表达清楚( ´・・)ノ(._.`),不知道在哪里做动图,额,,你们知道在哪里弄动图的,可以告诉我一声哈,我啥也不会,哈哈哈哈额?
那就这样吧。。
请添加图片描述
先不要走哈,留下三连嘛!!嘻嘻

请添加图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/181197.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • thinkPHP框架中执行原生SQL语句的方法

    thinkPHP框架中执行原生SQL语句的方法

    2021年10月21日
  • 声源定位专项_声源定位算法

    声源定位专项_声源定位算法之前发布了一款声源定位机器人,但是其中还包括图像处理和超声波传感器,以及单片机开发的内容,对于专门想要研究声源定位的朋友可能过于复杂。这次把声源定位的程序摘取出来,并且保证可以独立运行(只需要放到镜像里项目文件夹下),给想研究声源定位的朋友参考。#!/usr/bin/envpythonimportsocketimportsysimportthreadingimportr…

  • 数据接口-免费版(股票数据API)「建议收藏」

    获取股票数据的源头主要有:数据超市、雅虎、新浪、Google、和讯、搜狐、ChinaStockWebService、东方财富客户端、证券之星、网易财经。数据超市2016年5月6日更新。根据最近频繁出现的数据超市,可以无限制获取相关数据,而不再需要使用爬虫等方式获取,这样不仅节省了极大资源,也有利于遍历数据。具体的方法不再赘述,列出来相关网站清单,开发者可自行到这些网站查询调用方法。聚合数据 htt…

  • android:layout_gravity和android:gravity的区别

    android:layout_gravity和android:gravity的区别1.首先来看看android:layout_gravity和android:gravity的使用区别。android:gravity:这个是针对控件里的元素来说的,用来控制元素在该控件里的显示位置。例如,在一个Button按钮控件中设置如下两个属性,android:gravity=”left”和android:text=”提交”,这时Button上的文字“提交”将会位于Button的左

  • java ajax教程_JAVA AJAX教程第一章—初识AJAX

    java ajax教程_JAVA AJAX教程第一章—初识AJAX既然是认识AJAX,理论和实践相结合,这样让自己学的更快,理解更深入,我分一下几点:1、认识传统的同步交互方式和AJAX解决方案2、AJAX使用到的技术3、实例体验AJAX一、同步交互方式和AJAX解决方案传统的WEB应用是同步交互的方式,这种同步交互方式的处理过程如下图什么是同步交互方式:首先,用户向HTTP服务器提交一个处理请求。接着,服务器端接收到请求后,按照预先编写好的程序中的…

  • 解决NVIDIA显卡驱动 图形驱动程序安装失败 问题

    解决NVIDIA显卡驱动 图形驱动程序安装失败 问题本教程是在当你尝试一般的教程都无法解决问题的前提下使用,比如使用DDU工具卸载原显卡驱动后重新安装无效,找不到独立显卡的情况。退出火绒等杀毒软件win+R输入services.msc进入服务。将WindowsUpdata启动类型改为自动,并启动服务。win+R输入gpedit.msc进入本地策略编辑器。在计算机配置-模板管理-系统-设备安装-设备安装限制中双击图中第三个将其改为未配置或禁用重新安装显卡驱动即可…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号