Leetcode 7: Palindrome Number

Leetcode 7: Palindrome Number

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

 跟前几题类似， 这种string -> int 或者 int -> string的题目，凡是input or output 涉及int的题目，都要注意在计算过程中可能会出现output 的int overflow， 或者在计算过程中的某个变量overflow的情况。 如果是int -> string， 那么输入的数是一定不会overflow, 超过INT_MAX这个值的，要注意的是在计算过程中自定义的某个变量会不会overflow，为了避免这种情况发生，一般将过程中变量定义成long 型！ 如果是 string -> int ， 那么要注意输入的string convert to int的时候，会不会超过INT_MAX， 因为string 是不会overflow的， 为了避免这种情况发生，一般在计算过程中，要提前对overflow的情况进行check。 

这一题属于第一种，input 是int，要对int 进行判断， 要注意过程中自定义的变量会不会overflow。这一题判断palindrome方法想到的是和string的判断方法相似，利用递归/迭代来一一比较首尾字符。
class Solution {
private:
    bool helper(int x, int num) {
        //base case
        if (num <= 1) return true;
        //recursive rule
        //compare first and last num
        int first = x / num;
        int last = x % 10;
        if (first == last) {
            //get the mid nums
            x = (x % num) / 10;
            return helper(x, num/100);
        }else
            return false;
    }
public:
//step1: preprocessing int
//step2: get the first and end num
//step3: recursion compare
    bool isPalindrome(int x) {
        //positive num
        if (x < 0) return false;
        long long num = 1; //num might be overflow, must be long long type
        int n = x;
        while (n) {
            n = n / 10;
            num = num * 10;
        }
        num = num / 10;
        return helper(x, num);
    }
};
time complexity: O(n)
space complexity: O(1)