Leetcode 009. 回文数

[meibin08]

题目描述:

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

示例 1:

输入: 121
输出: true

示例2:

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

示例 3:

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

进阶:

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

难度：

• 难度：简单
• 支持语言：JavaScript、Java、Python

相关标签

• 数学

相关企业

• 阿里
• 京东
• 拼多多

思路 1（javascript）:

• 使用字符串就是判断回文字符串，很简单。
• 而不是用字符串就是NO.7，反转一个数字，然后比较它们是否相等；
• 注意：如果遇到负数直接返回false。

思路 2:

• 使用除法和求余获得对应位置的数字，无字符串操作。

• 首先获取当前数量级n，公式 n=10⌊log⁡10x⌋n=10^{\left \lfloor\log_{10}{x}\right\rfloor}n=10⌊log10​x⌋，如：x = 24, n = 10; x = 6234, n = 1000。
• 通过x / n 获取首位。
• 通过x % 10 获取末位。
• (x % n) / 10 去除首位和末位，（x % n去除首位，x / 10去除末位），x 位数减 2。
• n /= 100 x 位数减 2， 故n需要除 10210^2102。

• 以 123421 为例，运算过程如下:

x	n	x / n	x % 10
123421	100000	1	1
2342	1000	2	2
34	10	3	4

思路 3:

• 对于数字的末位，直接取余就可以了，对于数字的首位，我们可以这么算。
• 首先用一个变量记录数字的最高位，
• 比如 1232112321，可以标记 help 为 1000010000，
• 第一个末位为 11，第一个首位为 12321/10000=1，
• 接下来我们需要计算 232232 是否为回文，怎么计算呢？
• 我们需要去掉首位和末位。
• 可以采用 x % help / 10 的方式
• 12321%10000==2321 可以将最高位去掉，然后 2321/10==232 可以将最低为去掉。
• 最后不要忘记将 help/100。

思路 3 (py):

1. 转成字符串:
   a. 双向队列
   b. 双指针
2. 不转字符串:
   a. 模拟字符串的双向队列(使用math库的log函数 获取整数的位数)
   b. 反转后面一半的整数(使用math库的log函数 获取整数的位数)
   c. 反转后面一半的整数(不适用log函数) (通过原整数x 与 reverse_x 的大小判断)

复杂度分析

• 时间复杂度：O(\log n)O(logn)，对于每次迭代，我们会将输入除以 1010，因此时间复杂度为 O(\log n)O(logn)。
• 空间复杂度：O(1)O(1)。我们只需要常数空间存放若干变量。

代码

JavaScript 实现

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
  if(x<0)return false
  let n=x
  let rev=0
  while(n>0){
    let t=n%10
    rev=rev*10+t
    n=~~(n/10)
  }
  return rev===x
};

/**
 * @作者：lvshanke
 * @链接：https://leetcode-cn.com/problems/palindrome-number/solution/zhi-xing-yong-shi-chao-guo-9496nei-cun-xiao-hao-ch/
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    if(x < 0) return false;
    if(x < 10) return true;
    let right = 1;
    let left = 0;//初始为 x的总位数
    let sum = x;
    while(sum >= 1){//算出总位数
        sum /= 10;
        left++;
    }
    //获取第n位的数
    let getNum = (_x, n) => {
        return Math.floor(_x % Math.pow(10, n) / Math.pow(10, n - 1));
    }
    while(left > right){
        if(getNum(x, left) != getNum(x, right)) return false;
        left--;
        right++;
    }
    return true;
};

/**
 * @作者：Alexer-660
 * @链接：https://leetcode-cn.com/problems/palindrome-number/solution/9-hui-wen-shu-jiang-ti-jie-fu-zhi-dao-liu-lan-qi-k/
 */
var isPalindrome = function(x) {
    if(x<0 || (x%10 == 0 && x!=0)){
        return false;
    }
    var reverseNumber = 0;
    while(x>reverseNumber){
        reverseNumber = reverseNumber*10 + x%10;
        x = parseInt(x/10);
    }
    return x == reverseNumber || x == parseInt(reverseNumber/10)
};

Java 实现

/**
 * @作者：MisterBooo
 * @链接：https://leetcode-cn.com/problems/palindrome-number/solution/dong-hua-hui-wen-shu-de-san-chong-jie-fa-fa-jie-ch/
 */

class Solution {
    public boolean isPalindrome(int x) {
        //思考：这里大家可以思考一下，为什么末尾为 0 就可以直接返回 false
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        return x == revertedNumber || x == revertedNumber / 10;
    }
}

/**
 * @作者：reedfan
 * @链接：https://leetcode-cn.com/problems/palindrome-number/solution/ji-bai-liao-99de-javayong-hu-dai-ma-you-ya-by-reed/
 */


 public boolean isPalindrome(int x) {
    if (x < 0) {
        return false;
    }
    int help = 1;
    int tmp = x;
    while (tmp >= 10) {
        help *= 10;
        tmp /= 10;
    }
    while (x != 0) {
        if (x % 10 != x / help) {
            return false;
        }
        x = x % help / 10;
        help /= 100;
    }
    return true;
}

Python 实现

# 作者：kerwin-2wghdeNo1V
#链接：https://leetcode-cn.com/problems/palindrome-number/solution/jing-xin-hui-zong-python3de-5chong-shi-xian-fang-f/

class Solution:

    # 方法一: 将int转化成str类型: 双向队列
    # 复杂度: O(n^2) [每次pop(0)都是O(n)..比较费时]
    def isPalindrome(x: int) -> bool:
        lst = list(str(x))
        while len(lst) > 1:
            if lst.pop(0) != lst.pop():
                return  False
        return True


    # 方法二: 将int转化成str类型: 双指针 (指针的性能一直都挺高的)
    # 复杂度: O(n)
    def isPalindrome(x: int) -> bool:
        lst = list(str(x))
        L, R = 0, len(lst)-1
        while L <= R:
            if lst[L] != lst[R]:
                return  False
            L += 1
            R -= 1
        return True


    # 方法三: 进阶:不将整数转为字符串来解决: 使用log来计算x的位数
    # 复杂度: O(n)
    def isPalindrome(self, x: int) -> bool:
        """
        模仿上面字符串的方法:分别取'第一位的数'与'第二位的数'对比
                        (弊端是:频繁计算,导致速度变慢)(下面的方法三只反转一半数字,可以提高性能)
        """
        if x < 0:
            return False
        elif x == 0:
            return True
        else:
            import math
            length = int(math.log(x, 10)) + 1
            L = length-1
            print("l = ", L)
            for i in range(length//2):
                if x // 10**L != x % 10:
                    return False
                x = (x % 10**L) //10
                L -= 2
            return True

    # 方法四: 进阶:不将整数转为字符串来解决: 使用log来计算x的位数
    # 复杂度: O(n)
    def isPalindrome(self, x: int) -> bool:
        """
        只反转后面一半的数字!!(节省一半的时间)
        """
        if x < 0 or (x!=0 and x%10==0):
            return False
        elif x == 0:
            return True
        else:
            import math
            length = int(math.log(x, 10)) + 1
            reverse_x = 0
            for i in range(length//2):
                remainder = x % 10
                x = x // 10
                reverse_x = reverse_x * 10 + remainder
            # 当x为奇数时, 只要满足 reverse_x == x//10 即可
            if reverse_x == x or reverse_x == x//10:
                return True
            else:
                return False

    # 方法五: 进阶:不将整数转为字符串来解决: 不使用log函数
    # 复杂度: O(n)
    def isPalindrome(self, x: int) -> bool:
        """
        只反转后面一半的数字!!(节省一半的时间)
        """
        if x < 0 or (x!=0 and x%10==0):
            return False
        elif x == 0:
            return True
        else:
            reverse_x = 0
            while x > reverse_x:
                remainder = x % 10
                reverse_x = reverse_x * 10 + remainder
                x = x // 10
            # 当x为奇数时, 只要满足 reverse_x//10 == x 即可
            if reverse_x == x or reverse_x//10 == x:
                return True
            else:
                return False





x = 10
x = 10001
print(Solution().isPalindrome(x))

其他

• 原题leetcode链接：https://leetcode-cn.com/problems/string-to-integer-atoi/
• 合作方：JavaScript中文网 – 全球极客挚爱的技术成长平台
• 说明：leetcode 题解 | 每日一题🔥 所有题目并非全部为本人解答，部分为在复习学习中整理提取其他解题作者的优秀笔记，便于大家学习共同进步，如有侵权，请联系删除。