题目描述

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

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

示例 1:

输入:x = 121
输出:true
1
2

示例  2:

输入:x = -121
输出:false
1
2

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

示例 3:

输入:x = 10
输出:false
1
2

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

示例 4:

输入:x = -101
输出:false
1
2

链接:回文数open in new window

解法

for

思路:

  • 遍历时,从右至左,分别判断是否相同。
  • 比如 121,遍历时,判断 0 位和 2 位是否相同
    • 如果相同则继续判断,一直到中间是一位或者遍历完,return true。
    • 如果不同则 return false。
var isPalindrome = function(x) {
  typeof x == "number" ? (x = x + "") : x;
  let len = x.length;
  let logLen = Math.floor(len / 2);
  for (let i = 0; i < logLen; i++) {
    let isEqual = x[i] === x[len - (i + 1)];
    if (!isEqual) {
      return false;
    }
  }
  return true;
};
1
2
3
4
5
6
7
8
9
10
11
12

复杂度分析

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

二分法+翻转字符串

思路:

  • 将数字分割为两半,然后翻转另一份,然后进行比较。
  • 判断是否是奇数,如果是,截取一位再去比较。
  • 判断两个字符串,如果相同,则 return turn,否则 return false。
var isPalindrome = function(x) {
  typeof x == "number" ? (x = x + "") : x;
  let len = x.length;
  let isZhiNum = len % 2;
  let logLen = Math.floor(len / 2);
  let strArr = x.split("");
  let leftStr = strArr.splice(0, logLen);
  if (isZhiNum == 1) {
    strArr.splice(0, 1);
  }
  let rightStr = strArr.reverse();
  console.log(isZhiNum, logLen, leftStr, strArr);
  return leftStr.toString() === rightStr.toString();
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

复杂度分析:

  • 时间复杂度:O(1)
  • 空间复杂度:O(1)

总结

基础很重要,熟练掌握字符串、数学、数组方法。

上次更新: 7/30/2021, 8:16:54 AM