9. 回文数 Palindrome Number
题目描述
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
Example 1:
Input: 121
Output: true
Example 2:
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
Example 3:
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
解释: 从右向左读, 为 01 。因此它不是一个回文数。
Follow up 进阶
Coud you solve it without converting the integer to a string?
你能不将整数转为字符串来解决这个问题吗?
自解_string
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) return false;
string ori = to_string(x);
for (int i = 0; i < ori.length() / 2 + 1; i++){
if (ori[i] != ori[ori.length()-i-1])
return false;
}
return true;
}
};
自解_long
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) return false;
int ori = x;
long long rev = 0;
while (x > 0){
rev = rev * 10 + x % 10;
x = x / 10;
}
return rev == ori? true : false;
}
};
参考官方题解_翻转一半
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0 || (x % 10 == 0 && x != 0)) return false;
int rev = 0;
while (x > rev){
rev = rev * 10 + x % 10;
x = x / 10;
}
return rev == x || rev / 10 == x;
}
};
反转后的数字大于INT_MAX
时,将遇到整数溢出问题。考虑只反转 int 数字的一半,如果该数字是回文,其后半部分反转后应该与原始数字的前半部分相同。
- 反转后半部分的数字的方法与第7题基本一致,当原始数字小于反转后的数字时,就意味着我们已经处理了一半位数的数字。
- 处理特殊情况:x < 0;数字的最后一位是 0,第一位数字也是 0 的只有 0 满足
- 当数字长度为奇数时,由于处于中位的数字不影响回文(它总是与自己相等),可以通过 rev / 10 将其去除。
各种情况验证
- 数字长度为奇数时,最后循环结束一定为 rev 比 x 多一位,由
rev / 10 == x
进行回文判断 - 数字长度为偶数时,当循环到rev与x位数相等时
- 若 x > rev,此时 x 不是回文,但符合循环条件继续进入循环,使得 rev 较 x 多两位,由
rev == x
与rev / 10 == x
进行回文判断, 均不成立,判断正确 - 若 x <= rev,跳出循环,二者位数相等,由
rev == x
进行回文判断
- 若 x > rev,此时 x 不是回文,但符合循环条件继续进入循环,使得 rev 较 x 多两位,由