009-回文数

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/palindrome-number

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

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

例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121

输出：true

示例  2：

输入：x = -121

输出：false

解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

输入：x = 10

输出：false

解释：从右向左读, 为 01 。因此它不是一个回文数。

提示：

-231 <= x <= 231 - 1

二、解法

2.1 解法 1

不难得知：

1. 负数一定不是回文数
2. 10 以内的正整数和 0 一定是回文数。

转为字符串，然后第一个与最后一个比较，第二个与倒数第二个比较，一直比较到中间。

2.2 解法 1 代码

Java 代码

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }

        if (x < 10) {
            return true;
        }

        String digit = String.valueOf(x);
        int length = digit.length();
        for (int i = 0; i < length / 2; i++) {
            if (digit.charAt(i) != digit.charAt(length-1-i)) {
                // 只要有一次不等于就不是回文数
                return false;
            }
        }
        return true;
    }
}

JavaScript 代码

/**
 * 判断回文数
 *
 * @param {number} x
 * @return {boolean} true: 回文数, false: 不是回文数
 */
var isPalindrome = function (x) {
  if (x < 0) {
    return false;
  }

  if (x < 10) {
    return true;
  }

  let digit = x.toString();
  for (let i = 0; i < digit.length / 2; i++) {
    if (digit[i] != digit[digit.length - 1 - i]) {
      // 只要有一次不等于就不是回文数
      return false;
    }
  }
  return true;
};

C++ 代码

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) {
            return false;
        }

        if (x < 10) {
            return true;
        }

        // 转为字符串
        string num = to_string(x);
        int size = num.length();
        int i;
        for (i = 0; i < (size / 2); i++) {
            if(num[i] != num[size - 1 - i]) {
                return false;
            }
        }
        if (i >= (size / 2)) {
            return true;
        }
        return false;
    }
};

2.2 解法 2

1. 先算出整数值有几位
2. 然后第一个与最后一个比较，第二个与倒数第二个比较，一直比较到中间。

比如 12321，先算出是个 5 位数，然后算出万位的值是 12321 / 10000 % 10 = 1。个位的值是 12321 / 1 % 10 = 1。相比较，不同直接 return false。

第二步算出千位的值 12321 / 1000 % 10 = 2。十位的值 12321 / 10 % 10 = 2。然后相比较，一直到中间。

2.3 解法 2 代码实现

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) {
            return false;
        }

        if (x < 10) {
            return true;
        }

        int y = x;
        int count = 0;

        // 算出 x 有几位
        while (y) {
            count++;
            y = y / 10;
        }
        int len = count;
        int i;
        for (i = 0; i <= count / 2; i++) {
            int m = pow(10, len - 1);
            if(m != 0) {
                int first = x / m  % 10;
                int end = (x / int(pow(10, i))) % 10;
                if (first != end) {
                    return false;
                }
                len--;
                if(len == 0) {
                    break;
                }
            }
        }
        if (i >= count / 2) {
            return true;
        }else {
            return false;
        }
    }
};

2.3 解法三

对整数值进行后半部分反转，如果相等说明是回文数。

比如 456654，后半部分为 654 经过反转变为 456，然后与前半部分相比较，相同表明是回文数。

特殊考虑数字的长度是奇数的时候，比如 45654，后半部分是 654，反转成 456，只要比较前两个相同就好，中间的 6 是无关的。

代码实现：

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) {
            return false;
        }

        if (x < 10) {
            return true;
        }

        int y = x;
        int count = 0;
        // 算出 x 有几位
        while (y) {
            count++;
            y = y / 10;
        }

        if (x % 10 == 0 && x / int(pow(10, count - 1)) != 0) {
            // 100 50 末尾为 0，第一个位的不为 0，不是回文数
            return false;
        }

        int reverseValue = 0;
        while (x > reverseValue) {
            reverseValue = reverseValue * 10 + x % 10;
            x = x / 10;
        }

        if (count % 2 == 0) {
            // 偶数位，比较是否相等
            if (x == reverseValue) {
                return true;
            } else {
                return false;
            }
        } else if (count % 2 == 1) {
            // 奇数位，反转值丢弃最后一位，然后与 x 比较
            if (reverseValue / 10 == x) {
                return true;
            } else {
                return false;
            }
        }
        return true;
    }
};