9. Palindrome Number

Leetcode 問題: 9. Palindrome Number

題目

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.

傳入正負整數 n,判斷是否為 Palindrome 整數 ,如果是的話回傳 true,不是的話回傳 false

Example

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.
Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

演算法

1. 負正數因為有「- 負數符號」,所以都沒辦法變成 Palindrome 整數

-xxx 裡面的負號只有一個,所以一定無法找到成對的 - 負號

所以 負整數 一定不是 Palindrome 整數

2. 取得最左右邊數字進行比較

取得左邊數字

要取得最左邊數字,必須除以剛好小於那個數字的最大 10 的次方數字,再無條件捨去

數字 最左邊數字 運算 divider 分母
11 1 Math.floor(11 / 10) 無條件捨去 10
121 1 Math.floor(121 / 100) 無條件捨去 100
1221 1 Math.floor(1221 / 1000) 無條件捨去 1000
12321 1 Math.floor(12321 / 10000) 無條件捨去 10000

所以 divider 分母1 開始 乘以10,直到剛好小於數字即可

取得右邊數字

要取得最右邊數字,必須mod % 10,取 10 的餘數

數字 最左邊數字 運算
11 1 11 % 10
121 1 121 % 10
1221 1 1221 % 10
12321 1 12321 % 10

比較左右的數字,如果是一樣的話,就可能為 Palindrome 整數,所以繼續比較

如果不一樣,則不是 Palindrome 整數

3. 計算下一個要比較的數字

去除左邊數字

將原本的數字 mod % divider 分母,即可將最左邊方數字去除

數字 去除左邊數字後的數字 運算 divider 分母
11 1 11 % 10 10
121 21 121 % 100 100
1221 221 1221 % 1000 1000
12321 2321 12321 % 10000 10000

去除右邊數字

將原本去除左邊數字後的結果除以 10,並無條件捨去,就可以將最右邊數字去除

去除左邊數字後的數字 去除左右邊數字後的數字 運算
1 0 Math.floor(1 / 10) 無條件捨去
21 2 Math.floor(21 / 10) 無條件捨去
221 22 Math.floor(221 / 10) 無條件捨去
2321 232 Math.floor(2321 / 10) 無條件捨去

記得要先去除左邊再去除右邊,避免數字去除發生錯誤

然後去除完左右邊數字後,就可以在繼續比較左右邊的數字是否相同,直到比較的數字為 0 找不到可以再 比較的數字了

答案

JavaScript

TypeScript

function isPalindrome(checkNumber: number): boolean {
    if (checkNumber < 0) {
        // 負數都會有「- 負數符號」,所以都沒辦法變成 Palindrome 整數
        return false;
    }

    // 取得計算左側數字 divider 分母
    let divider = 1;
    while (checkNumber >= divider * 10) {
        // 假如分母 * 10 還是小於原本數字,表示分母還可以繼續加
        divider *= 10;
    }


    while (checkNumber) {
        // 右側數字
        let rightDigit = checkNumber % 10;
        // 左側數字
        let leftDigit = Math.floor(checkNumber / divider);

        if (leftDigit != rightDigit) {
            // 假如數字不相同,表示這個不是 Palindrome 整數
            return false;
        }

        // 取得下一個要檢查的整數,去除原數字的左右數字
        // 取餘數:去除最左邊數字
        checkNumber = checkNumber % divider;
        // 除以 10:去除最右邊數字
        checkNumber = Math.floor(checkNumber / 10);
        // 取得去除左右數字後,下一個檢查的分母
        divider = divider / 100;
    }

    return true;
};

參考資料