每日一道Leetcode（9）

问题描述¹

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:

输入: 121
输出: true

示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

进阶:

你能不将整数转为字符串来解决这个问题吗？

解决

思路： 可以把该数拆分成两半，一半是从左到右，一半是从右到左。但是可以小优化，即读到中间即可。我是把整数转换成字符串来做。

    public static boolean isPalindrome(int x) {
        // 如果小于0的数肯定不是回文数
        if(x < 0){
            return  false;
        }
        // 把整型x转换成String型
        String str = String.valueOf(x);
        int mid = str.length() / 2;
        int i = 0, j = str.length() - 1;
        // 判断是否是偶数
        // 在下面的循环中 i <= mid, 如果是偶数，比如4，那么len=2，那么下面的循环会多读一位
        if(x % 2 == 0){
            mid = mid - 1;
        }
        // 从左向右读 和 从右向左读，读到中间，如果比较有不相等则返回false
        while(i <= mid){
            // 如果
            if(str.charAt(i) != str.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        // 否则说明是回文数
        return true;
    }

如果要以整数来直接做，那么可以使用一个表达式，来从整数最后一位读起，读到前面，可以优化，就是读到中间。
比如：11211，读取最后一位数字：11211 % 10 即可读出，那么读取第二位数字呢？先执行 11211 / 10 = 1121，再执行 1121 % 10就可以得到，依次类推。如何取得反转后的数，只需要把最后一位数乘以10再加上第二位数，即 1 * 10 + 1 = 11。

    public static boolean isPalindrome(int x) {
        // 如果小于0的数肯定不是回文数
        // 并且需要排除掉所有0结尾的，如果不排除，下面的算法对于数据以0结尾的会算错。当然以0结尾的也肯定不是回文数
        // 只有0满足
        if(x < 0 || (x % 10 == 0 && x != 0)){
            return  false;
        }
        // 如果小于10的数肯定是回文数
        if(x >= 0 && x < 10){
            return true;
        }
        int reverse = 0; // 存储反转后的数
        // 优化：也是读一半。终止条件是：当x的位数 = reverse的位数就停止循环，即x > reverse
        while(x > reverse) {
            reverse = reverse * 10 + x % 10;
            x /= 10;
        }
        // x == reverse / 10 来处理 奇数情况，奇数情况下会多读一位
        return x == reverse || x == reverse / 10;
    }

---

1. 力扣（LeetCode）链接：https://leetcode-cn.com/problems/palindrome-number ↩︎