leetcode:Palindrome Number

leetcode:Palindrome Number

一、 題目

試確定一個整數是否為回文數。並不使用額外的空間。

提示：

負整數可能是回文數嗎？（例如 -1）

如果你想要將整數轉換成字符串，那麼你注意到不能使用額外的空間的限制。

可能你嘗試翻轉整數，但是，如果你已經解決這個問題“逆向整型”，你要知道，顛倒整數可能會溢出的情況。那麼你會如何處理這樣的情況呢？

要有解決這個問題的一種更通用的方法。

二、 分析

了解題目的意思後，其實問題本身很簡單的，一想到回文數腦海中立刻想到翻轉整數、雙指針等方法，但是難度在它的提示，即不能使用額外的空間和溢出的情況。原本我看是整數，就想到使用itoa()，不過此時不能使用，使用翻轉整數的方法雖然提示會溢出，不過這是最初想到的方法，leetcode也過了，如下：

1、每次將flag求余10，目標整數res = res * 10 + flag % 10；

2、flag /= 10，直到為0；

3、判斷目標整數和原整數是否相等。

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        int flag = x;
        int res = 0;
        while(flag > 0){
        	res = res * 10 + flag % 10;
        	flag /= 10;
        }
        if(x == res) return true;
        return false;
    }
};

另外一種方法是首先求出x的階數count,比較x頭尾兩個對應的數字是否相等即可，如下：

1、求出x的階數count；

2、比較x/count 和 x%10 不相等返回false；

3、x %= count，x /= 10，count /= 100，直到x = 0;

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        int a = x;
        int count = 1;
        while(a >= 10){
        	count *= 10;
        	a /= 10;
        }
        while(x > 0){
        	if(x/count != x%10)
        		return false;
        	x %= count;
        	x /= 10;
        	count /= 100;
        }
        return true;
    }
};