9. Palindrome Number
难度:Medium
刷题内容
原题连接
- https://leetcode.com/problems/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.
Example 3:
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Follow up:
Coud you solve it without converting the integer to a string?
解题方案
思路1 **- 时间复杂度: O(N)*- 空间复杂度: O(1)***
这题的难度不大，由于是数字，判断回文只需要求出倒过来的数字，判断两者是否相等，不过要注意负数一定不是回文
class Solution {
public:
bool isPalindrome(int x) {
long long ret = 0;
int num = x;
if(x < 0)
return false;
while(num)
{
ret = 10 * ret + num % 10;
num /= 10;
}
if(ret == x)
return true;
return false;
}
};
思路2 **- 时间复杂度: O(N)*- 空间复杂度: O(1)***
计算出数字的长度，用双指针法，一个指针指向头，另一个指向尾，相等就前一个指针加一，后一个指针减一，若不相等则返回 false
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0)
return false;
int cnt = 0;
long fac = 1;
int div = INT_MAX;
while (div != 0) {
cnt++;
fac *= 10;
div = x/fac;
}
fac /= 10;
for (int i=0; i<cnt/2; i++) {
int last = x%10;
int first = x/fac;
if (first != last)
return false;
x = x % fac;
x = (x-last)/10;
fac /= 100;
}
return true;
}
};
这两种方法的时间复杂度都取决于输入的数字的长度
