【每日算法Day 10】回文数
Wallace Xu 2020-06-10 数组算术
# 题目链接
LeetCode 9. 回文数 (opens new window)
# 题目描述
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。进阶:你能不将整数转为字符串来解决这个问题吗？
# 示例
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 解题思路
回文数和回文字符串的定义相同，故最直接的想法是将其转为字符串（字符数组）再分别从字符串首尾向中间扫描，两指针相遇时都吻合就为true。
public boolean isPalindrome(int x) {
String s=String.valueOf(x);
for (int l = 0, r = s.length()-1; l <= r; l++, r--) {
if (s.charAt(l)!=s.charAt(r))
return false;
}
return true;
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
或者将其转为整形数组：
public boolean isPalindrome2(int x) {
if (x<0) return false;
//计算位数创建对应大小的数组
int y=x,length=0;
do {
length++;
y/=10;
}while (y!=0);
int[] array=new int[length];
//填充每一位至数组中
for (int i = length-1; i >=0; i--) {
array[i]=x%10;
x/=10;
}
//同上
for (int l = 0, r = length - 1; l <= r; l++, r--) {
if (array[l]!=array[r]) return false;
}
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
使用整形数组比字符串在实际执行是要快一些，但是二者都需要额外O(log(10,x))的额外空间和O(logx)的时间。
为了避免使用非常数级的额外空间，可考虑对这个int值本身进行翻转。为避免整个数翻转溢出，可只翻转一半：
public boolean isPalindrome3(int x) {
if (x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int revertedHalf = 0;
//x<=revertedHalf时，已经翻转了原数字长度一半
while (x > revertedHalf) {
revertedHalf = revertedHalf * 10 + x % 10;
x /= 10;
}
//原数字有偶数位则直接比较两值，奇数位则除去翻转数字新加的最后一位再比较x
return x == revertedHalf || x == revertedHalf / 10;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13