6-回文数

题目

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

示例 1:

输入: 121 输出: true

示例 2:

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

示例 3:

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

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

解答

转成str

思路是这样的，先排负数的情况，然后开始验证是否回文 具体做法，是再造一个反转的str，然后i从0到str长度的中间，一头一尾地比对。有错就return，循环完了就true

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
  if (x < 0) {
    // 负数不会是回文
    return false;
  }
  const str = x.toString();
  const reverseStr = str
    .split("")
    .reverse()
    .join("");
  for (let i = 0; i < Math.round(str.length / 2); i++) {
    if (str[i] !== reverseStr[i]) {
      return false;
    }
  }
  return true
};

执行用时 :404 ms, 在所有 JavaScript 提交中击败了58.78%的用户

内存消耗 :46.3 MB, 在所有 JavaScript 提交中击败了13.56%的用户

似乎一般般，占用的空间太大了。

优化

1. 最后一位不能是0，除非只有一位，即0

增加一个一开始判断的边界条件

...
  if (x < 0 || (x % 10 === 0 && x !== 0)) {
    // 负数不会是回文
    // 最后一位不能是0，除非x是一位的0
    return false;
  }
...

2. 无需反转全部的str，只需反转后半部分

...
    const half = Math.round(str.length / 2);
  const reverseStr = str
    .slice(half - 1)     // 留下最后那一半，再多一位，以免for循环跑不到
    .split("")
    .reverse()
    .join("");
  for (let i = 0; i < half; i++) {
    ...
  }
...

优化后的代码：

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
  if (x < 0 || (x % 10 === 0 && x !== 0)) {
    // 负数不会是回文
    return false;
  }
  const str = x.toString();
  const half = Math.round(str.length / 2);
  const reverseStr = str
    .slice(half - 1)
    .split("")
    .reverse()
    .join("");
  console.log("=test=>", "reverseStr", reverseStr);
  for (let i = 0; i < half; i++) {
    if (str[i] !== reverseStr[i]) {
      return false;
    }
  }
  return true;
};

执行用时 :508 ms, 在所有 JavaScript 提交中击败了18.74%的用户

内存消耗 :47.8 MB, 在所有 JavaScript 提交中击败了5.01%的用户

反而好像更加不划算了。。 可能因为切字符串需要更多的时间和空间吧

进阶：纯粹用数字做

那么数字怎么切出最后一位？

var a = 123
var b = a % 10     
// b = 3

a = Math.floor(a / 10)
// floor向下取整

那么数字怎么push一位？

var c = c * 10 + b

那么怎么知道有没有切剩下一半？ 只要比对一下切下来的长度，和原来x的长度。如果比x要长了，那么自然就超过一半了

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
  if (x < 0 || (x % 10 === 0 && x !== 0)) {
    // 负数不会是回文
    return false;
  }
  let reverseInt = 0;
  while (reverseInt < x) {
    reverseInt = reverseInt * 10 + (x % 10);
    x = Math.floor(x / 10);
  }
  return x === reverseInt || x === Math.floor(reverseInt / 10);
};

执行用时 :244 ms, 在所有 JavaScript 提交中击败了99.93%的用户

内存消耗 :44.7 MB, 在所有 JavaScript 提交中击败了95.92%的用户

惊呆了，快得一批

测试代码

/**
 *
 * @param {number} condition：输入的answer
 * @param {boolean} target：答案
 * @param {string} label：报错标记符
 */

const ensure = (condition, target, label) => {
  if (condition !== target) {
    wrongMsg(condition, target, label);
  }
};

const testData = [
  {
    nums: 121,
    ans: true
  },
  {
    nums: -121,
    ans: false
  },
  {
    nums: 10,
    ans: false
  },
  {
    nums: 102,
    ans: false
  }
];

// ========== test ===========
const test = () => {
  for (let index = 0; index < testData.length; index++) {
    const test = testData[index];
    const ans = isPalindrome(test.nums);

    ensure(ans, test.ans, "reverse" + index);
  }
};