哪些网站做任务可以赚钱,网站建设九步走,seo整站优化外包公司,公众平台 wordpress前言
回文子串是练习数据结构和算法比较好的使用场景#xff0c;可以同时练习到双指针、动态规划等一些列算法。
实现原理
中心扩散算法实现。这里定义最长回文子串长度的大小为maxLen#xff0c;起点位置为0.
奇数个数为中心点和偶数个数为中心点分别计算回文长度大小。…前言
回文子串是练习数据结构和算法比较好的使用场景可以同时练习到双指针、动态规划等一些列算法。
实现原理
中心扩散算法实现。这里定义最长回文子串长度的大小为maxLen起点位置为0.
奇数个数为中心点和偶数个数为中心点分别计算回文长度大小。注意while退出条件为不匹配回文子串计算长度时需回退right和left。此时长度计算公式为(right-1)-(left1)1
得到最长回文长度大小后再计算起点位置。i-(maxLen-1)/2
具体代码实现
class Solution {public String longestPalindrome(String s) {int maxLen1;int begin0;char[] charArrays.toCharArray();for(int i0;icharArray.length-1;i){int oneNumvalidCicle(charArray,i,i);int twoNumvalidCicle(charArray,i,i1);int maxMath.max(oneNum,twoNum);if(maxLenmax){maxLenmax;begini-(maxLen-1)/2;}}return s.substring(begin,beginmaxLen);}public int validCicle(char[] charArray,int left,int right){while(left0rightcharArray.length){if(charArray[left]charArray[right]){left--;right;}else{break;}}return (right-1)-(left1)1;}
}
QA:待定