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 palindrome while 123 is not.

這道題求回文數字：和第7題一樣，這道題也是可以用字元串解法和代數解法。

字元串解法：轉化成字元串（含符号），逆轉再比較

class Solution {
    public boolean isPalindrome(int x) {
        String str = Integer.toString(x);
        String reversed_x = new StringBuilder().append(str).reverse().toString();
        return reversed_x.equals(str);
    }
}
           

代數解法：

這個思路我是看答案以後才明白，還是需要一點技巧的。

class Solution {
    public boolean isPalindrome(int x) {
        if ((x<0) || ((x%10==0)&&(x!=0))){
            return false;
        }
        int reversed_x =0;
        while (x > reversed_x){
            int remainder = x%10;
            reversed_x = reversed_x * 10 + remainder;
            x=x/10;
        }
        return (x==reversed_x) ||(x==reversed_x/10);
    }
}
           

思路分析： 要點有兩個，首先要人工排除肯定不是的兩種情況：（1） 負數 （2）除了數字0以外結尾是0的。

處理方法：對x求除以10的餘數，可獲得個位數，如果想獲得十位數，則需要把x/10，再重複以上求餘步驟，以此類推獲得百位數字，千位數字。。。（這裡用到了一個隐性的知識點，就是整型的相除會舍棄小數點，例如12345/10=1234）。如果不借助堆棧，求完的餘數要立刻用到reversed裡面，方法是reversed10+餘數（為什麼要乘以10呢，是因為每一次在後面續位時，前面的幾位要紛紛向左讓位，即10。比如147*10=1470，相當于把個位的位置讓出來給下一個要進來的數）。再有就是通過while （x > reversed_x）控制這個數字在處理到一半的時候停止，如果位數是奇數，循環停止時reversed會比x長一位；若位數為偶數，則循環停止時reversed和x位數相同。這時候再比較x與reversed，正如剛剛說的，若位數為奇數，成為回文數字的條件是reversed/10 = x （因為reversed長一位是以要除以十再比較）；或者位數為偶數時，成為回文數字的條件是reversed = x。必為兩者之一，否則不是回文數字。