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());
    }
}

有效率的解法 : 數學解

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

除法模數解

相關程式碼如下,以下範例為 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;
    }
}

一半數字解

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

以下為範例程式碼:

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 捨去一位的原因是,最後一位往往都是奇數位數的中間
    }
}


Revision #2
Created 1 July 2024 02:43:47 by Nesquate
Updated 8 July 2024 03:16:38 by Nesquate