Leetcode 009 题
Difficulty:Easy
Tag: Math
题目
题目原址：https://leetcode.com/problems/palindrome-number/#/description
Determine whether an integer is a palindrome. Do this without extra space.
思路分析
判断一个整数是不是回文数，有两个直观的思路
- 转换成字符串处理，然后利用字符串的反转操作即可.
- 整数反转，循环取模乘以10.
直观上说，思路1更简单，但是，题目限制了 不适用额外的空间 . 也就是要求空间复杂度为O(1), 而思路1的空间复杂度是O(n).
代码
class Solution {
public:
bool isPalindrome(int x) {
if(x < 0) return false;
int palindrome = 0;
int tmp = x;
while(x != 0)
{
palindrome = palindrome * 10 + (x % 10);
x = x / 10;
}
return palindrome == tmp;
}
};
代码-优化
将上段代码优化。 思路，根据回文数字的特性，反转一半得到的数或者得到的数的除以10的结果和剩下的数应该相等， 因为存在回文数的位数是奇数还是偶数的问题。
下面的例子可以清楚的解释
当 回文数的位数是偶数时，
124421 回文数
反转一半,此时
palindrome = ((1 * 10 + 2) * 10) + 4 = 124
x = 124
当 回文数的位数是奇数时，
12421 回文数
反转一半
palindrome = ((2 * 10 + 1) * 10) + 4 = 124 / 10 = 12
x = 12
class Solution {
public:
bool isPalindrome(int x) {
if(x < 0 || (x != 0 && x % 10 == 0)) return false;
int palindrome = 0;
while(x > palindrome)
{
palindrome = palindrome * 10 + (x % 10);
x = x / 10;
}
return (x == palindrome || x == palindrome / 10);
}
};