今天刷LeetCode，遇到一道简单算法题，Palindrome Number，但解题过程比较有意思，借此文记录下。
解析题目
问题描述： Determine whether an integer is a palindrome. Do this without extra space. 判断一个int类型的数是否为回文数？ 不使用额外空间。
关于什么是回文数？给个定义：正反方向输出的值相等的数称为回文数。 没理解到的，可以去网上搜下。
举例：1、1221、11211等是回文数；-1、0、12、123323等就不是回文数。
那什么是回文字符串呢？可以参考这篇文章【算法】Longest Palindromic Substring。
分析思路
理解题目后，总共想到三个思路：
- 按位比较： 1. 计算整数的位数（长度）， 2. 从第一位和最后一位开始依次递增和增减循环比较。
- 反转输入int，与原数比较看是否相等。 之前有道题是：反转一个int数，其中需要考虑溢出问题。
- 转成字符串，按位比较。 但题目限制不能占用额外内存。
考虑使用第一种思路，这道题比较简单，有了思路后，按说就可以编码了，但为了养成好习惯，别着急编码还是想下case情况先。我只想到两个：1.负数不是回文数。 2. 考虑位数奇偶数情况。虽然少，过程不能省。
开始编码，贴下我第一版代码。
public boolean isPalindrome(int x) {
if (x < 0) { // 负数情况
return false;
}
final int originX = x;
int bitCount = 1;
// 算出有多少位（长度）
while (x >= 10) {
x /= 10;
bitCount++;
}
int l = 0;
int r = bitCount - 1;
// 依次比较
while (getBitNum(originX, bitCount, l) == getBitNum(originX, bitCount, r)) {
l++;
r--;
if (l >= r) {
return true;
}
}
return false;
}
// 去取原数对应位下标的数值
int getBitNum(int num, final int len, int index) {
int temp = 1;
while (len - index > 1) {
temp *= 10;
index++;
}
return (num / temp) % 10;
}
LeetCode上类似白板编程，代码比较龊，请见谅。编写完了自测case，好都没问题，这么简单那就提交吧，提交是通过了，但提示该算法击败了1.7%的其它用户提交，也就是说效率很差，垫底了。这样怎么行呢，毕竟咋还是有追求的程序猿对吧。于是分析代码，其中三处循环，还有嵌套；估算时间复杂度为：O(nlog10n)。* （ps:时间复杂度计算，不是很清楚，有知道的大神请留言指教，谢谢。）
怀着焦虑的心情，点开了官方推荐解法页面。看到一半，哎呀，这不是上文中我想到的第二条思路吗，反转int整数。但官方建议只反转int的一半，然后与剩下一半比较，如果相等则是回文数。这就完美避开了Integer.MAX_VALUE溢出问题，不得不服。
想着先不看其代码实现，自己写一下再说，于是在之前基础上改出了下面的代码。
boolean isPalindromeNum(int x) {
if (x < 0) {
return false;
}
final int originX = x;
int bitCount = 1;
while (x >= 10) {
x /= 10;
bitCount++;
}
int index = 0;
int halfNum = 0;
final int halfLen = bitCount / 2;
int tempX = originX;
while (index < halfLen) {
halfNum = halfNum * 10 + tempX % 10;
tempX /= 10;
index++;
}
// 判断奇偶情况
return halfNum == (bitCount % 2 == 0 ? tempX : tempX / 10);
提交跑起来，嗯快了不少，击败了48%，感觉不错对吧。这会去看官方给出的C#代码实现，看完感觉受到一万点伤害，吐血了。不说了，贴代码。
boolean isPalindromeNumOfficial(int x) {
// Special cases:
// As discussed above, when x < 0, x is not a palindrome.
// Also if the last digit of the number is 0, in order to be a palindrome,
// the first digit of the number also needs to be 0.
// Only 0 satisfy this property.
if (x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int revertedNumber = 0;
while (x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
// When the length is an odd number, we can get rid of the middle digit by revertedNumber/10
// For example when the input is 12321, at the end of the while loop we get x = 12, revertedNumber = 123,
// since the middle digit doesn't matter in palidrome(it will always equal to itself), we can simply get rid of it.
return x == revertedNumber || x == revertedNumber / 10;
}
注释写的很清楚了，主要有三点：1. 判断尾数为0的情况 2. 取消判断位数的逻辑 3. 聪明处理奇偶位数情况。
小结
小小一道简单的算法题，都能频繁带给你刺激，是不是很过瘾。想想平时我们写的代码，是不是应该翻出来再斟酌斟酌，哈哈哈。
最后贴下转字符串思路实现的代码。
// 转字符串在比较 ，速度是很快的
public boolean isPalindromeForString(int x) {
String num = String.valueOf(x);
if (num == null || num.length() == 0) return true;
int start = 0, end = num.length() - 1;
while (start < end) {
if ((char) num.charAt(start) != (char) num.charAt(end)) return false;
start++;
end--;
}
return true;
}
以上代码均由Java实现，项目地址https://github.com/yangjiantao/DSAA。
