iT邦幫忙

DAY 20
2

連續30天,挑戰演算法系列 第 20

[Day20] 30 天挑戰演算法 - 迴文數字

題目來源:Palindrome Number

問題:
輸入一個數字並判斷它是否為 迴文(Palindrome), 並且不要使用額外的記憶體。

例子
所謂的 Palindrome Number(迴文數字) 就是互相對應的數字,例如:12321 或 1357531 或 9 。
只要有互相對稱的,就可以判斷成迴文數字。因此,只有一位數的數字,因為本身也是對稱,所以他也算是 Palindrome Number。

想法
既然迴文的條件就是要左右對稱,那麼負數就肯定不是迴文了。因為前面多個 負號,後面不可能再放個負號!
所以由此可推論出第一點:「只要是負數,就不是迴文」。

接著,針對數字如果我們想擷取的是第某位數,我們可以利用 mod 10 或 除以10 甚至 除以10的N次方 來達成我們的目的。( mod 10 代表 除以10取餘數)
我們先以一個例子當作示範,假設輸入的數字是 1325231 ,則我們為了可以取得左右位數的數字我們可以這麼做:

首先取得輸入數字( 1325231 )的位數,得到 7 位數
接著開始進入迴圈,而迴圈的次數則是 7/2 取整數,所以得到的是 3次。

Loop1:
左邊算來第一位: 1325231 除以 10 的 (7-1) 次方 得到 1
右邊算來第一位: 1325231 mod 10 得到 1

Loop2:
左邊算來第二位: 1325231 除以 10 的 (7-2) 次方 得到 13, 再 mod 10 得到 3
右邊算來第二位: 1325231 mod 100 得到 31, 再 除以 10 得到 3

Loop3:
左邊算來第三位: 1325231 除以 10 的 (7-3) 次方 得到 132, 再 mod 10 得到 2
右邊算來第三位: 1325231 mod 1000 得到 231, 再 除以 100 得到 2

經過上面的推算後,我們就可以歸納出判斷迴文數字的主要邏輯:

for (int i = 0; i < loop_times; i++)
{
    int 左邊的數字 = (輸入的數字 / 10 的 (digitCount - (i+1) 次方) ) mod 10;
    int 右邊的數字 = (輸入的數字 mod 10 的 (i+1) 次方) / (10 的 i 次方);

    if (左邊的數字 != 右邊的數字)
        return false;
}

其中,
digitCount 代表輸入數字總共有幾位數
loop_time 就是 digitCount / 2 所得到的次數,也就是一共要比幾次

如此一來,我們就可以順利的從 左/右 取得我們要的數字來做比較了!也不需要在額外宣告記憶體空間。

完整的程式碼如下(Python 版本):

def isPalindrome(x):
    if x < 0:
        return False
            
    // 取得輸入數字一共有幾位數            
    digit_count = 0
    temp = x
    while temp > 0:
        temp = temp / 10
        digit_count += 1
    
    // 取得要比較的次數
    loop_times = digit_count / 2
    
    for i in range(loop_times):
        highDight = (x / (10 ** ( digit_count - (i+1) ) )) % 10
        leftDigit = (x % (10 ** ( i+1 ))) / (10 ** i)
            
        if highDight != leftDigit:
            return False
        
    return True

上一篇
[Day19] 30 天挑戰演算法 - 數數字
下一篇
[Day21] 30 天挑戰演算法 - 迴文
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言