[数据结构与算法]LeetCode #9 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

输入：x = 121
输出：true

https://leetcode-cn.com/problems/palindrome-number/

一、字符串法

最简单的方法就是将数字转换成字符串，这样既避免了超出INT_MAX的问题，而且使用起来也简单易懂。

代码：

bool isPalindrome(int x) {
        auto str = std::to_string(x);
        int half = str.length() / 2;
    
        for(int i = 0; i < half; ++i)
        {
            // 奇数和偶数个字符都是同样的情况
            if(str[i] != str[str.length() - i -1])
            {
                return false;
            }
        }
        return true;
    }

二、取半法

这种方法类似于字符串方法，也仅仅比较一半，但使用的还是数字进行比较，且有效避免了溢出。

需要注意首先要排除数字为10倍数的情况（不为零）。

代码：

bool isPalindrome(int x) {
        // 排除了负数和x为10倍数的情况，因为若为10倍数，会导致最后cur/10为0
        if(x < 0 || (x % 10 == 0 && x != 0)) return false;
        int num = x, cur = 0;
        while(cur < num)
        {
            cur = num % 10 + cur * 10;
            num /= 10;
        }
        return num == cur || cur / 10 == num;
    }

会溢出的代码，如果使用java则不会有此问题：

bool isPalindrome(int x) {
        if(x < 0) return false;
        int num = x, cur = 0;
        while(num != 0)
        {
            cur = num % 10 + cur * 10;
            num /= 10;
        }
        return x == cur;
    }

?