9. Palindrome Number
Leetcode 問題: 9. Palindrome Number
Categories:
題目
Given an integer
x
, return true ifx
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;
};