LeetCode每日一练（回文数）
LeetCode每日一练（回文数）
题目如下：
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
判断一个数是否为回文数，首先想到的办法就是将其转为字符串，再通过反转字符串来判断是否相同，比如：
反转后字符串不相同，则不是回文数。
反转后数字相同，则是回文数。由此得代码如下：
public class Solution {
public static void main(String[] args) {
System.out.println(isPalindrome(121));
}
public static boolean isPalindrome(int x) {
// 将数字转为字符串
String str = String.valueOf(x);
// 将其反转
String newStr = new StringBuilder(str).reverse().toString();
return str.equals(newStr);
}
}提交到LeetCode：
题目的最后还提出了一个进阶要求：
进阶： 你能不将整数转为字符串来解决这个问题吗？
不借助字符串该如何实现呢？其实也非常简单，通过计算直接反转数字即可，以1234举例，首先我们需要获得该数字的个位数4，如何获取呢？求余10即可：
接下来获取十位数3，先让1234除以10，这样就得到数字123，再让123求余10即可得到3：
以此类推，就能够得到数字中的每一位：
再让每一位分别乘以对应的进位即可，那既然是要反转，我们就要反着来，将4看成千位，3看成百位，2看成十位，1看成个位：
由此得到反转后的数字：4 * 1000 + 3 * 100 + 2 * 10 + 1 = 4321。
代码如下：
public class Solution {
public static void main(String[] args) {
System.out.println(isPalindrome(121));
}
public static boolean isPalindrome(int x) {
int num = x;
int result = 0;
// 将数字反转
while (x > 0) {
result *= 10;
result += x % 10; // 求得每一位
x /= 10;
}
return num == result;
}
}但这个程序还有一个小漏洞，就是越界问题，当某个数字反转后大于了int的最大值，那么程序就会出错：
此时result因为超过了int能表示的最大值，已经变成了一个负值，它永远不可能与输入的值相等，所以程序就无法准确判断输入的值是否为回文数了。
为了解决这一问题，我们可以不反转所有的数字，而是反转其中的一半，因为回文数的性质，使得我们只需要知道其中的一半相同，那么它就一定是回文数。
我们需要分两种情况讨论一下，首先是奇数长度的数字，以12321举例：
我们得到反转后一半长度的数字：
将它与反转前一半长度的数字比较，发现均为12，表明12321就是一个回文数。
若是偶数长度的数字，以1221举例：
仍然得到反转后一半长度的数字：
将其与反转前一半长度的数字比较即可。
那么关键在于如何进行数字的切割和获取呢？我们将奇数长度和偶数长度的数字放在一起讨论一下：
首先让其求余10即可得到最后一位数：
接着让原来的数除以10即可舍去最后一位：
再求余10得到最后一位：
再让原来的数除以10舍去最后一位：
到这里就应该停止操作了，因为偶数长度情况的数已经获取到了一半长度的数字，对于偶数情况，直接比较新生成的数字是否与原数字相等即可；而对于奇数长度情况，虽然获取到了一半长度的数字，但原数字中的长度为3，所以我们应该再获取一次：
由此可得，循环的终止条件为当原来的数小于或者等于新生成的数，而对于奇数情况，我们需要去除最后一位数再与原数字比较，所以让新生成的数字除以10再比较。
综上所述，得到代码：
public class Solution {
public static void main(String[] args) {
System.out.println(isPalindrome(12321));
}
public static boolean isPalindrome(int x) {
// 负数一定不是回文数
if (x < 0 || (x % 10 == 0 && x != 0)) {
// 若是数字的最后一位是0，则如果是回文数，那该数的第一位一定为0，满足情况的数字只有0
// 所以若是最后一位为0，但该数又不是0，则直接返回false
return false;
}
int newNum = 0;
// 当原数字小于或等于新生成的数字时停止循环
while (x > newNum) {
newNum *= 10;
newNum += x % 10;
x /= 10;
}
// 比较新生成的数字是否与原数字相等
return x == newNum || x == newNum / 10;
}
}提交到LeetCode：
