0009 - Palindrome Number（回文數）

大意說明

簡單來說就是找到類似於  121 的回文數（就是往前讀往後讀都是 121，英文會長得類似是 abcba 這種東東）

自己的思考過程（逆向字串解）

有幾種想法，一開始先想到透過轉成字串陣列，然後用迴圈做起頭和尾巴的不斷比較，迴圈範圍為字串陣列長度  / 2。

但很顯然地這個會先碰到不同語言對於除法小數的問題，導致無法過關。

例如以下 Python Code 就會卡到 / 2 的問題：

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False

        number_str = str(x)
        result = False
        for i in range(0, int(len(number_str) / 2)): # 如果遇到 0 <= x <= 9，len / 2 會是 0
            if number_str[i] == number_str[len(number_str) - 1 - i]:
                result = True
            else:
                result = False
        return result

所以後來改開新的 list，倒轉加入之後再把 list 合併成一個字串，就過了：

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False

        number_str = str(x)
        reverse_num = []
        for i in range(0, len(number_str), 1):
            reverse_num.append(number_str[len(number_str) - 1 - i])

        return "".join(reverse_num) == number_str

但如果要逆向字串的話，Python 對於字串有內建方法 - Slice：

class Solution:
    def isPalindrome(self, x: int) -> bool:
        num_str = str(x)
        reversed_num = num_str[::-1] # Reverse slice
        return reversed_num == num_str

Java 版本一開始想到的比較麻煩，轉成 String 之後，又要轉成 Char Array 之後才能做逆向加入，且還要開 StringBuilder (不開也可以但就很耗能):

class Solution {
    public boolean isPalindrome(int x) {
        String numStr = String.valueOf(x);
        char[] numChrArray = numStr.toCharArray();
        StringBuilder builder = new StringBuilder();

        for(int i = 0;i < numChrArray.length; i++){
            builder.append(numChrArray[numChrArray.length - 1 - i]);
        }

        return numStr.equals(builder.toString());
    }
}

後來查到可以用 String.charAt()，於是可以少開一個 Char Array:

class Solution {
    public boolean isPalindrome(int x) {
        String numStr = String.valueOf(x);
        StringBuilder reverseNum = new StringBuilder();

        for(int i = 0;i < numStr.length(); i++){
            reverseNum.append(numStr.charAt(numStr.length() - 1 - i));
        }

        return numStr.equals(reverseNum.toString());
    }
}

有效率的解法 : 數學解

不要做字串轉換，直接做數學計算

除法模數解

• 先判斷是不是小於  0 （因為負數不可能是回文數）
• 跑迴圈
• 用模數取得個位數 (% 10)
• 把個位數加入到另外一個變數當中
• 跑下一次迴圈
• 前面步驟一樣，用模數取得個位數，但是在加入到另外一個變數之前，另外一個變數要先進位 (x 10)
• 跑下一次迴圈
• 迴圈結束條件：當所有的位數都取完了就結束
• 另外一個變數跟原本的數字去比較

相關程式碼如下，以下範例為 Java：

class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0){
            return false;
        }

        long temp = x;
        long reversed  = 0;

        while(temp != 0){
            long y = temp % 10;
            reversed = reversed * 10 + y;
            temp /= 10;
        }

        return x == reversed;
    }
}

一半數字解

道理跟前面解法差不多，但是只有算一半，可以減少時間複雜度和空間複雜度，只是

• 要多做先前判斷：像 10 這種可以被 10 整除但模數等於 0 的數字絕對不可能是回文數
• 因為位數有奇偶，如果遇到奇數位數，最後判斷的時候要捨去一個位數，因為最後一次加入的數字是中間數（反正中間數肯定是一樣的）
• 迴圈結束條件會變成當逆向數大於等於原先數字被不斷除以 10 的結果

以下為範例程式碼：

class Solution {
    public boolean isPalindrome(int x) {
        if((x < 0) || (x != 0 && x % 10 == 0)){ // 多做一個 x 不是 0 但是模數 10 卻是 0 的狀況（這不可能是回文數）
            return false;
        }
        long reversed  = 0;

        while(x > reversed){ // 如果 x 被 10 除到最後小於等於 reversed，結束 loop
            long y = x % 10;
            reversed = reversed * 10 + y;
            x /= 10;
        }

        return (x == reversed) || (x == reversed / 10); // reversed / 10 捨去一位的原因是，最後一位往往都是奇數位數的中間
    }
}