回文数

题目描述#

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

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

思路#

看到回文，最初直接想到的方案就是，字符串反转，然后做相等比对即可，这样的操作，不仅能处理回文数，~~连回文诗都能处理~~🤦‍♂️。对应的时间复杂度便是 O(n)。但是这是一个数学题，我们期望可以做一些对应的优化。

反转一半数字#

既然是回文数，那么说明前面一半的数字和反转后的另一半的数字会是相同的，例如: 123321，则前面一部分 123 与 321 反转后是相同的。奇数个数字的时候，例如：12321，我们则可以取12与321反转后的123去掉3做对比即可。

基于此思路，我们可以反转到一半之后，就开始比对是否相等，或者减去一个数字后的值是否相等（奇数个时）。

边界情况：对于负数(-12321)，因为有符号的存在则永远不可能是回文数；对于10的倍数，因为没有0开头的数字，则永远不可能是回文数，0除外。因此我们可以将该边界条件提前返回 false

这样我们便得到时间复杂度为O(log₁₀(n))的方法。

如何计算出一个 O(logn) 的时间复杂度，可以参考该文章：时间复杂度 O(log n) 意味着什么？

参考答案#

function isPalindrome(x: number): boolean {
  if (x < 0 || (x % 10 === 0 && x !== 0)) {
    return false;
  }

  let reverseX = 0;
  while ( reverseX < x ) {
    reverseX = reverseX * 10 + x % 10;
    x = Math.floor(x / 10);
  }

  return reverseX === x || Math.floor(reverseX / 10) === x;
}