Leetcode-回文数

题目描述

回文数

1
2
3
4
5
6
7
8
9
10
11
12
13
判断一个整数是否是回文数。不能使用辅助空间。

点击查看提示

一些提示:

负整数可以是回文数吗?(例如 -1)

如果你打算把整数转为字符串,请注意不允许使用辅助空间的限制。

你也可以考虑将数字颠倒。但是如果你已经解决了 “颠倒整数” 问题的话,就会注意到颠倒整数时可能会发生溢出。你怎么来解决这个问题呢?

本题有一种比较通用的解决方式。

分析

这道题目难点就在于不能使用额外的空间,否则直接转换成字符串然后检查这个字符串时候相等就可以了.

所以如果不采用额外的空间,那就是假设这个数是回文数,那么就可以根据回文性质得到一个新的数,然后对比这两个数是不是相等的即可.

巧妙的是,如果一个数是回文数,那么最后一位就是第一位,所以可以通过正常的构建数的方法来构建,非常巧妙。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
bool isPalindrome(int x) {
if(x<0)
return false;
int raw_x = x;
int new_x = 0;
while(x!=0){
new_x = new_x*10 + x%10;
x /= 10;
}
return raw_x == new_x ;
}
};

当然一开始我的想法比较的挫,是先判断出位数,然后选择一半,如果这个数是回文数,通过较低一半的数就能构造出整个数.

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
class Solution {
public:
bool isPalindrome(int x) {
if(x<0)
return false;
//获取这个数字的位数
int length = 1;
long long int ten_multi = 10;
while(x/ten_multi){
ten_multi *= 10;
length += 1;
}
int new_num = 0;
int low_ten_multi = 1;
int half_length = length/2;
int raw_x = x;
for(int i=0;i<half_length;i++){
int low_position = x%10;
ten_multi /= 10;
new_num += low_position*low_ten_multi + low_position*ten_multi;
low_ten_multi *= 10;
x = x/10;
}
if (length%2){
new_num += (x%10)*low_ten_multi;
}
return new_num == raw_x;
}
};