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)


相关推荐

  • android开发之Intent.setFlags()_让Android点击通知栏信息后返回正在运行的程序

    在应用里使用了后台服务,并且在通知栏推送了消息,希望点击这个消息回到activity,结果总是存在好几个同样的activity,就算要返回的activity正在前台,点击消息后也会重新打开一个一样的activity,返回好几次才能退出,而不能像qq之类的点击通知栏消息回到之前存在的activity,如果存在就不再新建一个activity说的有点绕,如果是遇到此类问题的肯定能懂,没遇到过

  • web网页设计代码模板_web网页设计源代码

    web网页设计代码模板_web网页设计源代码代码分享:https://pan.baidu.com/s/1xf4AQlfM8e6Nvw2oXUdbrA提取码:ap1v

  • Batch Normalization批量归一化[通俗易懂]

    Batch Normalization批量归一化[通俗易懂]深度学习捷报连连、声名鹊起,随机梯度下降成了训练深度网络的主流方法。尽管随机梯度下降法对于训练深度网络简单高效,但是它有个毛病,就是需要我们人为的去选择参数,比如学习率、参数初始化、权重衰减系数、Dropout比例等。这些参数的选择对训练结果至关重要,以至于我们很多时间都浪费在这些的调参上。那么学完这篇文献之后,你可以不需要那么刻意的慢慢调整参数。批量标准化一般用在非线性…

  • java queryinterface_C++ COM编程之QueryInterface函数(一)

    java queryinterface_C++ COM编程之QueryInterface函数(一)前言组件对外公布的是接口;一个组件可以实现多个接口,也就是说可以对外公布多个接口,之前也总结过了,你很少会100%的去完全了解一个组件的所有接口,就像你去学习编程一样,你几乎不可能去成为编程中的全才。那么,既然我们不能去完全的了解一个组件提供的所有接口,那么我们在实际开发中,如何去判断一个组件是否提供对应的接口呢?看文档?是的,是个好主意,在文档的海洋,找到一个知识点,真的很难,浪费时间和精力;其…

  • 大数据开发面试题及答案(在美团点评的开发岗怎么样)

    此面试题来自牛客网友分享的美团优选一面,面试时长一小时。网友情况:海外水本,在某三线中厂工作2年。参考答案由本公众号提供。如有错误,欢迎指正!以下为面试过程中提问,岗位为大数据开发,根据提…

  • pycharmpip不是内部或外部命令,也不是可运行程序_pip安装的包pycharm识别不了

    pycharmpip不是内部或外部命令,也不是可运行程序_pip安装的包pycharm识别不了解决pip不是内部或外部命令问题

发表回复

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

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