自己买个服务器做网站,微网站 留言板,网游开发软件,广州越秀区租房废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【最长回文子串】#xff0c;使用【字符串】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为…废话不多说喊一句号子鼓励自己程序员永不失业程序员走向架构本篇Blog的主题是【最长回文子串】使用【字符串】这个基本的数据结构来实现这个高频题的站点是CodeTop筛选条件为目标公司最近一年出现频率排序由高到低的去牛客TOP101去找只有两个地方都出现过才做这道题CodeTop本身汇聚了LeetCode的来源确保刷的题都是高频要面试考的题。
名曲目标题后附上题目链接后期可以依据解题思路反复快速练习题目按照题干的基本数据结构分类且每个分类的第一篇必定是对基础数据结构的介绍。
最长回文子串【MID】
一道中心扩展思想解决的MID题目
题干 解题思路 每个字符都可以尝试作为中心点看会出现两种情况可能是类似 aba 的字符串也可能是类似 abba 的情况只需要分别计算出以一个和两个字符作为中心点的子串取出较大的长度即可从left到right开始向两边扩散、比较如果相等则继续扩散比较如果不相等则剪枝不用再继续扩散比较计算每次比较的回文子串长度取最大
代码实现
给出代码实现基本档案 基本数据结构字符串 辅助数据结构无 算法迭代 技巧双指针、中心扩散法 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param s string字符串* return int整型*/public String longestPalindrome(String s) {// 1 边界条件判断if (s.length() 2) {return s;}// 2 初始化参数结果参数的第一位存储起始位置第二位存储长度int maxLength 0;int[] result new int[2];// 3for (int i 0; i s.length(); i) {// 中心位置奇数情况下扩展结果int[] odd centerSpread(s, i, i);// 中心位置偶数情况下扩展结果int[] even centerSpread(s, i, i 1);// 当前中心位置最大子串int[] curMax odd[1] even[1] ? odd : even;// 当前中心位置最大子串如果大于历史记录最大子串则暂存最大值及预期返回结果if (curMax[1] maxLength) {maxLength curMax[1];result curMax;}}// 截取返回结果本来如果起点是1长度是2那么结尾下标应该212-1这里结尾为123是因为3不会被计入因为substring左闭右开区间所以计算为12-11为开区间1123return s.substring(result[0], result[0] result[1]);}// 扩散的核心方法public int[] centerSpread(String s, int left, int right) {// 双指针在边界内且满足扩散条件while (left 0 right s.length() - 1 s.charAt(left) s.charAt(right)) {left--;right;}// 回文子串为左右指针开区间内的部分right-1-(left1)1right-left-1return new int[] {left 1, right - left - 1};}
}复杂度分析
时间复杂度 O(N^2)平均需要遍历每个结点作为中心点O(N)还需要从中心点向左右扩散比较O(N) 空间复杂度 O(1)只用到常量
