大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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账号...