[Leetcode] Palindrome Number 回文數(shù)

lixiang 發(fā)布于2019-08-14 14:03 / 3043人閱讀

摘要：首尾比較法復(fù)雜度時間空間，為所求的長度思路先求記為的長度根據(jù)長度制造掩碼循環(huán)當(dāng)當(dāng)最高位等于最低位還有數(shù)字等待判斷最高位通過掩碼和整除取得，最低位通過取余取得判斷過后更新掩碼，刪掉最高位，刪掉最低位注意求長度的如何取得一個的最高位假設(shè)答設(shè)置一

Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

首尾比較法 復(fù)雜度

O(Length) 時間 O(1) 空間， Length為所求Integer的長度

思路

先求Integer (記為x) 的長度len

根據(jù)長度制造掩碼 (mask)

循環(huán)當(dāng)：當(dāng)最高位等于最低位 && x還有數(shù)字等待判斷(x != 0)

最高位通過掩碼和整除取得(646/100=6)，最低位通過取余取得(646%10=6)

判斷過后更新掩碼(mask/=100)，刪掉最高位(x%=mask)，刪掉最低位(x/=10)

注意

求Integer長度的utility:

int len = 0;
while (x != 0) {
    len++;
    x /= 10;
}
return len;

如何取得一個Integer的最高位？假設(shè)x = 688
答：x / mask. 設(shè)置一個和x位數(shù)一樣的mask，mask = 100，然后用x/mask，表示x里面有幾個mask，即是最高位數(shù)字. 688里有6個100，即為6.

如何刪去一個Integer的最高位？假設(shè)x = 688
答：x = x % mask. 還是用這個mask，用 x = x % mask 即可得到688除以100的余數(shù)，這個余數(shù)其實等于刪掉了x的最高位剩下的數(shù).

如何取得一個Integer的最低位？假設(shè)x = 688
答：x % 10.

如何刪去一個Integer的最低位？假設(shè)x = 688
答：x = x / 10.

代碼

public class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0)
            return false;
        int len = getIntegerLength(x);
        int mask = (int)Math.pow(10, len - 1);
        while (x != 0) {
            if (x % 10 != x / mask)
                return false;
            x %= mask;  //去最高位
            x /= 10;    //去個位
            mask /= 100;    //mask要丟掉兩個零，不是一個！
            
        }
        return true;
    }
    public int getIntegerLength(int x) {
        int len = 0;
        while (x != 0) {
            x /= 10;
            len++;
        }
        return len;
    }
}