Leetcode9回文数

9回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121
输出: true

示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

进阶:

你能不将整数转为字符串来解决这个问题吗？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/palindrome-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

把数字按位分解并比较
时间复杂度：O(n) {约1.5n}
执行用时：4 ms
内存消耗：5.4 MB

bool isPalindrome(int x)
{
    if (x < 0)
        return false;
    int bits[10] = {0};
    int i = 0, j = 0;
    while (x != 0)
    {
        bits[i++] = x % 10;
        x /= 10;
    }
    while (j < i)
    {
        if (bits[j++] != bits[--i])
            return false;
    }
    return true;
}

Solution 2

反转一半数字
时间复杂度：O(n) {约0.5n}
执行用时：16 ms
内存消耗：5.3 MB

bool isPalindrome(int x)
{
    if (x < 0)
        return false;
    if (x % 10 == 0 && x != 0)
        return false;
    int inverse = 0;
    while (inverse < x)
    {
        inverse = inverse * 10 + x % 10;
        x /= 10;
    }
    if (inverse == x)
        return true;
    if (inverse / 10 == x)
        return true;
    return false;
}