9. Palindrome Number

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.

Example 1:

Input: x = 121
Output: true

Example 2:

Input: x = -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: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

题目会给我们一个整数，并希望我们能够确认这个整数在反转之後，与原来的是否相同，如果相同回传true否则回传false，另外因为像是10这样的数字翻转过来会变01，因此一定与原来不同，-10翻转过来会变01-，也与要求不同，要回传false。

转为字串解法

我们可以藉由题目的要求，简单判断得知，虽然题目是给我们整数型态，但实际上如果我们能将此整数转为字串型态，并与本身翻转後比对是否相同，一样可以达到题目所求。在C++与python都能运用内建函式做到这一点，但因为此方法需要较多步骤，包括转为字串、翻转字串、字串比对，对於电脑较熟悉数字的特性来说，是稍微慢了一点。以下展示python的程序码。

class Solution:
    def isPalindrome(self, x: int) -> bool:
        x = str(x)
        if x[::-1] == x:
            return True
        return False

这样的解法在Leetcode上其实也会跑得蛮快的，但是以练习的角度，用这样快速内建的函式来达成题目的要求，就会比较少机会思考更多其他的解法，以达到练习的效果，所以我也试着用不同的思路去看这一题。

反转整数解法

这个解法的思路主要是希望能基於对於整数的运算，一位数一位数把原本整数的个位数，转到最高位数，而最高位数转到最低位数，其余依此逻辑类推，从而达到将题目所给的整数反转，并且在最後直接比对原先整数和反转後整数是否相同，就能得到答案了。

但这题必须注意的是，一般在C/C++一个整数的资料占用的空间是4个bytes也就是32bit，理论上最大也只能存到2 ^ 32 - 1的数，因此我们在翻转整数的过程，可能会产生Overflow的问题（会出现runtime error），因此我们在设定翻转後的整数时，可以将其设为long的资料型态，因为long是被分配到8bytes的，整整64位元，可以避免Overflow的问题。

以下是C++的程序码

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0){
            return false;  //去除负数的情况
        }
        int m = x;  //先记住原本的x
        long y = 0;  //资料型态要设为long

        while(x != 0){  //透过回圈和运算将整数反转并存进y中
            y = y * 10 + x % 10; 
            x /= 10;
        }
        return m==y;
    }
};

参考资料

https://leetcode.com/problems/palindrome-number/
https://leetcode.com/problems/palindrome-number/discuss/986012/Simple-C%2B%2B-Solution
http://kevin.hwai.edu.tw/~kevin/material/JAVA/PrimitiveDataType.htm