9. Palindrome Number 回文數

題目：Palindrome Number 回文數

難度：簡單

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true
      

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
      

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
      

Follow up:

Coud you solve it without converting the integer to a string?

題意解析：

确定整數是否是回文，當一個整數向後讀取與向前讀取的内容相同時，它就是一個回文。

解題思路一：

幾乎所有人都能想到的就是将整數轉換成字元串，然後對字元串進行判斷即可。

public boolean isPalindrome(int x) {
        String s = String.valueOf(x);
        int i=0,j = s.length()-1;
        while (i<=s.length()-1 && j >= 0){
            if (s.charAt(i) != s.charAt(j)){
                return  false;
            }
            i++;
            j--;
            if (i >= j){
                return true;
            }
        }

        return true;
    }
           

此算法時間複雜度O(n/2)

送出代碼之後：

Runtime: 8 ms, faster than 99.62% of Java online submissions for Palindrome Number.

Memory Usage: 34.8 MB, less than 100.00% of Java online submissions for Palindrome Number.

解題思路二：

不做字元轉換，在原地進行判斷，定義一個整數y，從x的個位數依次向前取數，每次取一個新的數字時，就将y目前的數值擴大10倍再加上需要相加的數字，直到 y >= x即結束。将我們的整數分為前後兩部分，那麼當整數的位數為奇數時，後面的部分除以10跟前面相等，

如12321，前面 12後面123。當個數為偶數時，前面的整數跟後面相等，如1221，前面12，後面12

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

        return x == y || x == y / 10 ? true : false;
    }
           

此算法時間複雜度也是O(n/2)，不過勝在沒有做字元串的轉換。

送出代碼之後，

Runtime: 6 ms, faster than 100.00% of Java online submissions for Palindrome Number.

Memory Usage: 34.4 MB, less than 100.00% of Java online submissions for Palindrome Number.