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