昨晚被某厂实习笔试算法题完虐,在有限时间内的算法编程简直渣到不行,本身不是很难的题竟然也没做出来。总结只有一点,代码量不够。还是得多多锻炼,提高快速编程的思维能力。
笔试题目的第一题就是LeetCode中的这道算法题,心里不由的碎碎念:要是勤快一点先做了,就会是另外一个情况了。
题目描述很简单:就是在一个字符串中寻找最长子回文字符串。
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
定义
回文,就是一个字符串正着念和反着念都一样,比如“abcba”,比如“上海自来水来自还上”,比如“明天到操场….”。
对于这道算法题研究的英文字符串来说,有奇数回文和偶数回文两种情况。奇数回文是指回文字符串是奇数个,比如abcba
;偶数回文是指回文字符串是偶数个,比如abba
。在设计算法的时候应该把这两种情况都考虑在内。
思路
- 将字符串
String
处理成字符数组char[]
; - 逐个字符遍历数组,比如遍历到下标为i的字符时:
- 奇数回文判断:ci-1是否等于ci+1,如果等于则继续向两头递增,记录最长度;
- 偶数回文判断:ci-1是否等于ci,如果等于则继续向两头递增,记录最长度。
- 遍历结束后判断最长的字符串是偶数回文还是奇数回文,按照长度和下标生成返回回文字符串。
实现
我的算法比较简单,个人感觉比较好理解,代码如下:
|
|