LeetCode #9 Palindrome Number 解題思路及翻譯

內容目錄

LeetCode題目翻譯

英文原文如下

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward.

For example, 121 is a palindrome while 123 is not.

中文翻譯

給予一個整數x ，判斷是否為回文數字，並回傳結果( True/False )

一個數字是回文的意思是他從前面讀起跟從後面讀起是一樣的結果

舉例來說，121是回文而123不是

回文的維基百科說明也一併附上

x 為介於-2³¹ 跟 2³¹ -1 之間，即為Int32之範圍

現在來看下範例

範例相對容易理解，我們直接看向範例2

給予的x 為 -121，倒過來為 121- ，雖然數字位置都對但那個負號就對不上了，故應回傳 False

解題思路

這一題筆者我當初馬上就想到了很簡單的方式，把整個字串都倒過來直接比對就好了吧

例如 x變數 12345 我先把他變成 y變數 54321 再直接比 x跟y有甚麼差異就好了吧

話不遲疑，來試試看

C# 解決方案

方案1 – 整個字串翻轉過來

public class Solution {
    public bool IsPalindrome(int x) {
        string first = x.ToString();             //先把int x 轉為string方便後面操作
        char[] charArr1 = first.ToCharArray();   //對照組
        char[] charArr2 = first.ToCharArray();   //為了翻轉整個string故先改為char array
        Array.Reverse(charArr2);                 //Array內建語法 - 全部物件翻轉
     
        return charArr1.SequenceEqual(charArr2); //兩個Array進行比對，一致則回傳true
    }
}

其實最早的版本還要把資料變回string去比較，但轉型對效能又造成了耗損，故改為直接以Array型式比較

方案2 – 遞迴比較

後來想了想下，感覺用單純的遞迴跑應該也可以，而且特定狀況下可能會比較快，所以又嘗試了第二種寫法

從index 0 開始，index 0 跟 index max-1 比較

index 1 跟 index max -2 比較 … 以此類推

把邏輯整理後寫出如下

public class Solution {
    public bool IsPalindrome(int x) {
        string k = x.ToString();        //先把int x 轉為string方便後面操作
        
        for(int i=0;i<k.Length/2;i++)   //跑到一半就好，因為回文前後應該要對應
        {
            if(k[i] != k[k.Length-1-i]) //回文對應的位置
            {
                return false;           //若有不符合的，則回傳 False
            }
        }
        return true;                    //若全部資料都跑完無誤的話，則回傳 True
    }
}

其中要注意的地方就是 k.Length/2 ，因為回文的話前後要相互呼應，故跑到一半長度的字串都沒問題應該就代表整串都沒問題了

舉前面官方的範例1 來說 (x = 121 )

k.Length/2 應該要為1.5，但用Int來除就會只取整數位，故為1

所以流程會如下

i = 0; i <1
- k[0] 跟 k[3-1-0] 比較，分別為 1跟1，相等，故遞迴繼續
i = 1; i <1 並不成立，故遞迴結束

這時候大家會想說不是還有index 1還沒有比較嗎? 沒錯，但只剩一個字，當然不管從左到右或是從右到左都是相同的

若是現在的範例位數改為偶數(如 : 123321 )，狀況就會相對單純

i 會一路跑到 k.Length/2 -1 (因為是小於)，而元素也會一個對上一個的全部對應上

Java解決方案

方案1 ➡ 同C#的第二個解法

class Solution {
    public boolean isPalindrome(int x) {
        String k = String.valueOf(x);
      
        for(int i=0;i<k.length()/2;i++)
        {
            if(k.charAt(i) != k.charAt(k.length()-1-i))
            {
                return false;
            }
        }
        return true;
    }
}

Python3 解決方案

方案1

class Solution:
    def isPalindrome(self, x: int) -> bool:
        return str(x)[::-1] == str(x);

看起來真的超級簡短的!

JavaScript 解決方案

方案1

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    
    let text = x.toString();
    for(var i=0;i<text.length/2;i++)
    {
        if(text.charAt(i) != text.charAt(text.length-1-i))
        {
            return false;
        }

    }
    return true;
};

結論

這題對於有一點程式基礎的朋友來說應該都算是比較不難的題目

但如何在答出答案的同時兼顧效能與邏輯，還是可以好好思考的(如 : 如果k.Length 沒有除2 ，如果要跑到結尾只會浪費整整一倍的時間)

"寫好程式不難，難的是要把程式寫好"

題目連結 : Palindrome Number – LeetCode

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡可以的話，幫我的FaceBook 粉絲專頁按個讚，我會很感謝的

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

最新文章