[算法] - 回文数

[renjie-run]

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

示例 1:

输入: 121
输出: true

示例 2:

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

示例 3:

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

思路 了解完回文数的概念便可以设计出相应的算法，解法有很多种，其中也有很多可以优化的点。

可以首先排除一些不是回文数的情况：

• 小于 0 的整数。
• 不为 0 且末尾为 0 的整数。

排除完不是回文数的情况，也可以确定一些是回文数的情况：

• 小于 10 的整数。

解法一 将整数转为字符串，并拆分为字符列表，利用数组反转方法，再将原整数列表和反转后的整数列表，转为字符串直接对比即可。这也是最简单粗暴的一种方式了。

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
  if (x < 0 || (x % 10 === 0 && x !== 0)) {
    return false;
  }
  if (x < 10) return true;
  let numberStrings = (x + '').split('');
  let reversedNumberStrings = [...numberStrings].reverse();
  return numberStrings.toString() === reversedNumberStrings.toString();
};

解法二 这个解法其实也是利用了数字转字符串的方式来处理的，这里的核心思想是逐个对比第一个和最后一个数字，但是只需要对数值字符串遍历一半即可，所以性能上要比解法一要好一些，具体看代码。

var isPalindrome = function(x) {
  ...
  let numberStrings = x + '';
  let isPalindrome = true;
  let numberStringsLength = numberStrings.length;
  let halfNumberStringsLength = numberStringsLength / 2;
  for (let i = 0; i < halfNumberStringsLength; i++) {
    if (numberStrings[i] !== numberStrings[numberStringsLength - 1 - i]) {
      isPalindrome = false;
      break;
    }
  }
  return isPalindrome;
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/palindrome-number