leetcode筆記：Palindrome Number

一. 題目描述

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

Some hints:
Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

二. 題目分析

該題的大意是，判斷一個整數是否為回文數。該題給出了很多提示。其中包括要求空間復雜度只能是O(1)，所以不能考慮把整數轉化為字符串然後reverse比較的方法。

另外，如果使用reverse integer一題的方法，可能會造成數據溢出的問題，所以也是不可行的。

這裡的思路也比較簡單，每次取出整數的最高位和最低位進行比較，如果相等，去掉這兩位，繼續比較整數的最高位和最低位，知道整數為0為止。

三. 示例代碼

#include 

using namespace std;

class Solution
{
public:
    bool isPalindrome(int x) 
    {
        if (x < 0) return false;
        int SIZE = 1;
        // 以下操作用於確認x的最高位
        while (x / SIZE >= 10) SIZE *= 10;
        while (x > 0)
        {
            int left = x / SIZE;
            int right = x % 10;
            if (left != right) return false;
            // 去除x的最高位和最低位
            x = x % SIZE / 10;
            SIZE /= 100; // 位數減2
        }
        return true;
    }
};

四. 小結

這並不算高效的方法，提交後發現有耗時更少的方法，只能繼續研究了。