3.3　回文數

題目描述（第9題）

判斷一個整數是否是回文數。回文數是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數。

示例1

輸入：121

輸出：True

示例2

輸入：-121

輸出：False

解釋：從左向右讀為-121，從右向左讀為121-，因此它不是一個回文數。

示例3

輸入：10

輸出：False

解釋：從右向左讀為01，因此它不是一個回文數。

進階

你能不將整數轉化為字符串來解決這個問題嗎？

如果將整數轉化為字符串，問題就轉化為前面講過的判斷字符串的回文算法。我們可以不將整數轉化為字符串來解決這個問題嗎？當然可以，并且也十分簡單。

思路

在計算機程序中，整數中的各位數字不能像數組那樣被隨機訪問，因此采用頭/尾指針的方法行不通。

如果我們能夠得到原數的倒序，那么只需要和原數進行比較，觀察是否相同就可以了。一個簡單的做法是將其轉化為字符串然后讓字符串逆序，但是這種做法還不如轉化為字符串之后直接使用雙指針，并且題目進階中要求不將整數轉化為字符串來解決這個問題，問題的關鍵在于得到原數的倒序。一個思路是從高位到低位依次得到整數每一位上的值，然后從低位到高位構建新的值。

不妨假設要判斷的整數為x，我們可以通過x%10（取余操作）獲取x的最后一位，然后將x整除10得到的商更新到x。這樣不斷循環直到x等于0為止。最后只要判斷從后往前取的數和原來的數是否相同即可。

簡單來說，檢驗一個整數是否為回文數，對于正數只需要檢查它是否等于它的倒序即可，而構造一個整數的倒序，可以按位處理（這里假設倒序的整數不會越界）。

代碼

復雜度分析

●　時間復雜度：O(n)，其中n為整數的位數。

●　空間復雜度：O(1)。