回文數

題目連結

leetcode

題目描述

給你一個整數 x ，如果 x 是一個回文整數，傳回 true ；否則，傳回 false 。

回文數是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數。例如，121 是回文，而 123 不是。

示例 1：

輸入：

x = 121
輸出：
true
示例 2：
x = -121

false
解釋：
從左向右讀, 為 -121 。從右向左讀, 為 121- 。是以它不是一個回文數。
示例 3：
x = 10

從右向左讀, 為 01 。是以它不是一個回文數。
示例 4：
x = -101

題目解法

第一種解法：使用字元串反轉函數，把數字添加進StringBuilder裡面，在反轉，然後轉換為整數在比較

public static boolean isPalindrome(int x) {
        //如果數字比0小就不是回文，除了0以外，如果個位數為0的話，也不是回文
        if(x < 0 || (x != 0 && x % 10 == 0)) {
            return false;
        }
        StringBuilder str = new StringBuilder();
        str.append(x);
        //反轉
        str.reverse();
        /* 有可能會溢出 */
        if(x == Integer.parseInt(str.toString())) {
            return true;
        }
        return false;

        /*Stack<Character> stack = new Stack<Character>();
        String s = Integer.valueOf(x).toString();
        for(int i = 0;i<s.length();i++) {
            stack.add(s.charAt(i));
        }
        StringBuilder str = new StringBuilder();
        while (!stack.isEmpty()){
            str.append(stack.pop());
        }
        if(s.equals(str.toString())) {
            return true;
        }
        return false;*/
    }

第二種解法：反轉一半的數字

官網給的解析：

思路

映入腦海的第一個想法是将數字轉換為字元串，并檢查字元串是否為回文。但是，這需要額外的非常量空間來建立問題描述中所不允許的字元串。

第二個想法是将數字本身反轉，然後将反轉後的數字與原始數字進行比較，如果它們是相同的，那麼這個數字就是回文。

但是，如果反轉後的數字大于int.MAX，我們将遇到整數溢出問題。

按照第二個想法，為了避免數字反轉可能導緻的溢出問題，為什麼不考慮隻反轉int 數字的一半？畢竟，如果該數字是回文，其後半部分反轉後應該與原始數字的前半部分相同。

例如，輸入 1221，我們可以将數字 “1221” 的後半部分從 “21” 反轉為 “12”，并将其與前半部分 “12” 進行比較，因為二者相同，我們得知數字 1221 是回文。

算法

首先，我們應該處理一些臨界情況。所有負數都不可能是回文，例如：-123 不是回文，因為 - 不等于 3。是以我們可以對所有負數傳回 false。除了 0 以外，所有個位是 0 的數字不可能是回文，因為最高位不等于 0。是以我們可以對所有大于 0 且個位是 0 的數字傳回 false。

現在，讓我們來考慮如何反轉後半部分的數字。

對于數字 1221，如果執行 1221 % 10，我們将得到最後一位數字 1，要得到倒數第二位數字，我們可以先通過除以 10 把最後一位數字從 1221 中移除，1221 / 10 = 122，再求出上一步結果除以 10 的餘數，122 % 10 = 2，就可以得到倒數第二位數字。如果我們把最後一位數字乘以 10，再加上倒數第二位數字，1 * 10 + 2 = 12，就得到了我們想要的反轉後的數字。如果繼續這個過程，我們将得到更多位數的反轉數字。

現在的問題是，我們如何知道反轉數字的位數已經達到原始數字位數的一半？

由于整個過程我們不斷将原始數字除以 10，然後給反轉後的數字乘上 10，是以，當原始數字小于或等于反轉後的數字時，就意味着我們已經處理了一半位數的數字了。

public static boolean isPalindrome1(int x) {
        //如果數字比0小就不是回文，除了0以外，如果個位數為0的話，也不是回文
        if (x < 0 || (x != 0 && x % 10 == 0)) {
            return false;
        }
        int reverse = 0;
        while (x > reverse) {
            reverse = reverse * 10 + x % 10;
            x /= 10;
        }
        //      偶數直接比較     奇數去掉最後一位再比較
        return x == reverse || x == reverse / 10;
    }