leetcode回文系列

leetcdoe回文字系列

这篇是记录在刷题时候遇到一些回文字符串或者回文数系列的题目,有着一定的共性,值得记录总结学习一下。

#5最长回文子串

这个题之前面试的时候遇到过,题目如下,还是蛮重要的一道题

image-20200519114450840

思路:这里不仅仅是验证是否是回文,还要你给回最长的子字符串,有种最优解的感觉,所以想必是可以使用动态规划来做的,验证状态方程的判断条件就使用以往的回文数的判定方法。借助双指针,这里的双指针是跟随双指针,不是之前的左右遍历双指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
//动态规划
//关键在于找到状态方程以及转移方程
public String longestPalindrome(String s) {

//先定义好一开始的一些变量
int size = s.length();
if(size < 2){
return s;
}
int start = 0;
int end = 0;
int max = 1;
// 定义好布尔类型的二维数组
boolean[][] pali = new boolean[size][size];
//遍历
for(int r = 1; r < size; r++){
for(int l = 0; l < r; l++){
//想要判断当前的指针指针指向
if((s.charAt(l) == s.charAt(r)) && ((r - l <= 2) || pali[l+1][r-1]) ){
pali[l][r] = true;
//符合回文
//这里有这一项是因为题目要求给出最长的子字符串,所以每次找到回文的就要
//判断一下它是否比之前的长
if(r-l+1 > max){
max = r- l+1;
start = l;
end = r;
}
}
}
}
//返回结果
return s.substring(start,end+1);

}

}

#9回文数

题目如下,简单判断是否是回文数。顺着来和逆着来是一个数的意思。

image-20200519121315800

思路

  1. 首先是可以转换为字符串来做,暴力法或者是字符串双指针都是可以的
  2. 建议使用数学法,感觉更加高效一点,采用除余的方法来判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public boolean isPalindrome(int x) {
if(x < 0)
return false;
int cur = 0;
int num = x;
while(num != 0) {
cur = cur * 10 + num % 10;
num /= 10;
}
return cur == x;
}
}

#680 验证回文字符串2

题目如下,这道题有点特殊是,它可以允许删除一个字符来满足回文。

image-20200519113824107

思路是用双指针来做,左右指针移动来完成条件的筛选,还借助了一个函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public boolean validPalindrome(String s) {
int size = s.length();
//首先是总体的移动
for( int l = 0,r = size-1; l < r; l++,r--){
//找到不合适的地方,这里是允许删除一个字符来满足
if(s.charAt(l) != s.charAt(r)){
//选择删掉左边的一个字符或者是右边的字符来满足
return valid(s,l+1,r) || valid(s,l,r-1);
}
}
return true;

}
//删除左边的是这种abcca
//删除右边的是这种abbca
public boolean valid(String s, int l, int r){
while(l < r){
//这里删完了之后。查找就像以前的回文字符串验证一样,遍历完看看是否全部符合就行了
if(s.charAt(l++) != s.charAt(r--)){
return false;
}
}
return true;

}
}

评论