题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

题目链接

最长回文子串

测试用例

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

输入：s = “cbbd”
输出：“bb”

暴力循环判断

思路

1. 为了节省空间，不需要记录回文子串，只需要记录他的开始下标与长度即可
2. 双重for循环，枚举每个子串
3. 只判断 比 当前存储的最长回文子串 长度大的子串（节省时间，否则可能超时）
4. 对字符串进行分割，得到当前的最长回文串

代码实现

class Solution {//暴力求解public String longestPalindrome(String s) {int maxLen = 1;//记录最长回文子串长度int begin = 0;//不用存储子串for(int i=0; i<s.length(); i++){for(int j=i+1; j<s.length(); j++){//只需要判断子串长度比目前最大回文子串长的字符串//否则需要再次判断该子串长度与当前记录的最大回文子串长度的大小//可能会存在超时的现象if(j-i+1>maxLen && isPalindromic(s,i,j)){maxLen = j-i+1;//当前最长回文子串的长度begin=i;//利用maxLen和begin记录了当前最长的回文子串}}}//分割子串String res = s.substring(begin, begin+maxLen);return res;}//验证是否为回文子串public boolean isPalindromic(String s, int left, int right){//退出循环的条件while(left < right){if(s.charAt(left)!=s.charAt(right)){return false;}left++;right--;}return true;}
}

复杂度

1. 时间复杂度
   在两个for循环中还进行了遍历，所以是 O ( n 3 ) O(n^3) O(n3)
2. 空间复杂度
   O ( n 3 ) O(n^3) O(n3)，只用到常数个临时变量

中心扩散法

参考网站

中心扩散法

思路

1. 从中间位置向两端扩散，一共存在两种情况，扩散得到的每个子串有两种情况
   （1）一是子串长度为奇数，在确定初始start与end的时候，直接start=end=i即可【以某个元素为中心进行扩散】
   （2）而是子串长度为偶数，在确定初始start与end的时候，可以将start=i-1, end=i【以某两个元素为中心进行扩散】

2. 首先确定特殊情况，当题目中的字符串长度为0或者1时，直接返回该字符串即可【原字符串为最长回文子串】

3. for循环从字符串首部到尾部进行中心扩散
   每个扩散分为两种情况：子串为奇数或者偶数

4. 返回最长回文子串

5. 中心扩散思路：
   （1）判断当前首部字符与尾部字符是否相等，若相等，向左右扩散
   （2）不相等的话break循环
   （3）重复（1）与（2）直到首部或者尾部越界
   （4）判断由当前位置向中心扩散的最长回文子串长度，如果比以往记录的大，则进行更新

代码

class Solution {//中心扩散法，回文串的枚举可以从中间位置开始int[] range = new int[2];//记录回文子串的开始下标与结束下标public String longestPalindrome(String s) {char[] str = s.toCharArray();//以后会反复的取字符串中的某个元素，通过这种方式会节省时间int length = s.length();//记录字符串长度，不需要在重复计算//本身就是最长回文串if(length<=1){return s;}//从中心扩散//注意是i从1开始，因为如果长度是偶数的话，取中间两个位置，假设取的是当前的i与它左边的i，中心扩散for(int i=1; i<length; i++){//子串长度为偶数helper(str, length, i, i-1);//子串长度为奇数helper(str, length, i, i);}//返回最长回文串,包括range[0]，不包括range[1]  [ )return s.substring(range[0],range[1]);}//不需要有返回值，range为全局的变量，中心扩散找回文串//这里char[] str是引用传递，若为string类型的，则需要不断的复制stringpublic void helper(char[] str, int length, int start, int end){while(start>=0 && end<length){//判断从当前strat，end分别向左向右扩散一个字符，那一个字符是否相等if(str[start]==str[end]){start--;end++;}else{break;}}//判断range中存储的回文串与该循环回文串哪个较长，在range中存储较长的//注意是range[1]-range[0]，因为range[1]中存储的是子串的下标+1，即等价于(range[1]-1 - range[0] +1)if((end-1) - (start+1) +1 > range[1]-range[0]){//在s.substring(start,end)的时候包括start，不包括end//当前满足的回文串的下标为[strat+1,end-1]，而sub时候不包含end，则range[1]中存储end即可range[0] = start+1;range[1] = end;}}
}

动态规划法

• 没看呢没看呢，明天一定补上

java边学边用

字符串

1. 长度s.length()，注意这里有括号

    for(int j=i+1; j<s.length(); j++)
   

2. 分割字符串
   a. public String substring(int beginIndex)
   b. public String substring(int beginIndex, int endIndex)
   beginIndex – 起始索引（包括）, 索引从 0 开始。
   endIndex – 结束索引**（不包括）**
   

   String res = s.substring(begin, begin+maxLen);
   

3. 返回索引处的字符s.charAt(1)

    if(s.charAt(left)!=s.charAt(right))
   

4. 字符串转化为字符数组char[] toCharArray()

   char[] str = s.toCharArray();
   

数组

1. 定义

   int[] range = new int[2];
   

函数的参数传递

当传的是基本类型时，传的是值的拷贝，对拷贝变量的修改不影响原变量；当传的是引用类型时，传的是引用地址的拷贝，但是拷贝的地址和真实地址指向的都是同一个真实数据，因此可以修改原变量中的值【当传的是String类型时，虽然拷贝的也是引用地址，指向的是同一个数据，但是String的值不能被修改，因此无法修改原变量中的值。】

1. 基本类型
   基本数据类型只有8种，可按照如下分类
   ①整数类型：long、int、short、byte
   ②浮点类型：float、double
   ③字符类型：char
   ④布尔类型：boolean
2. 引用类型
   引用数据类型非常多，大致包括：
   类、 接口类型、 数组类型、 枚举类型、 注解类型、 字符串型
   例如，String类型就是引用类型。
   简单来说，所有的非基本数据类型都是引用数据类型。

String

public class testPar {public static void main(String[] args) {String s = "start";System.out.println("执行testString前的s："+s);testString(s);System.out.println("执行testString后的s："+s);}public static void testString(String s){s = "testString";System.out.println("testString中的s："+s);}}

运行结果

执行testString前的s：start
testString中的s：testString
执行testString后的s：start

数组

public class testPar1 {public static void main(String[] args) {int[] arr = {1,2};System.out.println("执行testArr前的arr："+arr[0]+","+arr[1]);testArr(arr);System.out.println("执行testArr后的arr："+arr[0]+","+arr[1]);}public static void testArr(int[] arr){arr[0] = 12;System.out.println("testArr中的s："+arr[0]+","+arr[1]);}
}

执行结果

执行testArr前的arr：1,2
testArr中的s：12,2
执行testArr后的arr：12,2

做题技巧

1. 如果需要重复取字符串中指定位置元素的值的话，提前将字符串变为字符数组，节省时间

   char[] str = s.toCharArray();
   

2. 后期如果经常用到字符串的长度，应该用整数记录

   int length = s.length();
   

3. 定义全局数组

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！