LeetCode 9. 回文数

题意

判断一个数是否为回文数。

思路

  • 想法1:直接翻转数字,判断翻转后的数字和之前的是否相同。时间复杂度$O(log_{10}(n))$,要注意负数和爆int的问题。但这种做法只击败了37%的提交,考虑优化。
  • 想法2:参考官方题解后发现可以翻转一半的数字,秒啊。时间复杂度$O(log_{10}(n))$。

代码

  • 代码1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
bool isPalindrome(int x) {
if(x < 0)
return false;
int tem = x;
long revx = 0;
while(tem)
{
revx = revx * 10;
revx += tem % 10;
tem /= 10;
}
if(revx == x)
return true;
else
return false;
}
};
  • 代码2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
bool isPalindrome(int x) {
if(x < 0 || (x % 10 == 0 && x != 0))
return false;

int revx = 0;
while(x > revx)
{
revx = revx * 10 + x % 10;
x /= 10;
}

return x == revx || x == revx / 10;
}
};

总结

优化!优化!优化!!

Donate comment here
0%