LC 9、回文数
LeetCode上的 9、回文数，难度为 简单
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。
示例：
输入：x = 121
输出：true
字符串解法
将整数转换为字符串，并且判断是否为回文串，老生常谈的问题，直接给出代码：
class Solution{
bool isPalindrome(int x){
string str = to_string(x);
int l = 0, r = str.size() - 1;
while(l < r){
if(str[l] != str[r]) return false;
l++;
r--;
}
return true;
}
}
- 时间复杂度：数字n的位数，时间复杂度为O(log10n)
- 空间复杂度：是哦那个了字符串作为存储，复杂度为O(log10n)
非字符串解法（完全翻转）
原来 x 的不超过int 的表示范围，反转后值可能会有变化，所以我们使用long 类型的值来接收新的值。
class Solution{
bool isPalindrome(int x){
long long ans = 0;
int t = x;
while(t > 0){
ans = ans * 10 + t % 10;
t /= 10;
}
return ans - x == 0;
}
}
- 时间复杂度：数字n的位数，时间复杂度为O(log10n)
- 空间复杂度：O(1)
进阶（部分翻转）
我们只需要利用回文字符串的性质，前半部分和后半部分相同即可。
但是我们需要考虑一个情况，就是数字的位数问题：
- 奇数：需要考虑中间数字。
- 偶数：我们只需保证数字停在中间就可
所以，我们的数字的末尾，不可以是0，一定要保证产生位数压制。
class Solution{
bool isPalindrome(int x){
if(x < 0 || (x % 10 == 0 && x != 0)) return false;
int t = 0;
while(x > t){
t = t * 10 + x % 10;
x /= 10;
}
// 返回值，前者是指，为偶数的情况，后者是指，我们忽略掉了最中间一位
return x == t || x == t / 10;
}
}
- 时间复杂度：数字n的位数，时间复杂度为O(log10n)
- 空间复杂度：O(1)
Label：回文串，数学