9. 回文数

  • 难度简单
  • 本题涉及算法算数 双向指针
  • 思路算数 双向指针
  • 类似题型:

题目 9. 回文数

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

示例 1:

输入: 121
输出: true

示例 2:

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

示例 3:

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

进阶:

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

方法一 算数

  • 解题思路:
    • 数值反转
  • 复杂度分析:
    • 时间复杂度 $O(n)$ ,$N$ 表示数值包含元素长度
    • 空间复杂度 $O(1)$

java

class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0) // 如果为负数,直接返回 false
            return false;
        int cur = 0;
        int num = x;
        while(num != 0) {
            cur = cur * 10 + num % 10;
            num /= 10;
        }
        return cur == x; // 最后比较 数值反转前后是否相等
    }
}

python

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0: # 如果为负数,直接返回 false
            return False
        num = x
        cur = 0
        while num !=0:
            cur = cur*10 + num%10
            num //=10
        return cur == x # 最后比较 数值反转前后是否相等

方法二 双向指针

  • 解题思路:
    • 数值转成字符串,遍历元素
    • 首尾各一个指针,向中间靠拢,每次元素是否相等
  • 复杂度分析:
    • 时间复杂度 $O(n/2)$ ,$N$ 表示数值包含元素长度 ,如果数值是回文数 最多需要遍历 $O(n/2)$ 次
    • 时间复杂度 $O(1)$

java

class Solution {
    public boolean isPalindrome(int x) {
        if(x<0){ // 如果为负数,直接返回 false
            return false;
        }
        String strNum = String.valueOf(x);
        for(int i = 0;i<=strNum.length()/2;i++) {
            int a = strNum.charAt(i);
            int b = strNum.charAt(strNum.length()-1-i);
            if(a != b) {
                return false;
            }
        }
        return true;

    }
}

python

class Solution(object):
    def isPalindrome(self, x):
        nums = str(x)
        for i in range(len(nums)):
            if nums[i] != nums[len(nums)-1-i]:
                return False
        return True

方法三 取出后半段数字进行翻转

  • 解题思路具体步骤
    • 每次进行取余操作 ( %10),取出最低的数字:y = x % 10
    • 将最低的数字加到取出数的末尾:revertNum = revertNum * 10 + y
    • 每取一个最低位数字,x 都要自除以 10
    • 判断 x 是不是小于 revertNum ,当它小于的时候,说明数字已经对半或者过半了
    • 最后,判断奇偶数情况:如果是偶数的话,revertNum 和 x 相等;如果是奇数的话,最中间的数字就在revertNum 的最低位上,将它除以 10 以后应该和 x 相等。
  • 主要事项
    • 这里需要注意的一个点就是由于回文数的位数可奇可偶,所以当它的长度是偶数时,它对折过来应该是相等的;当它的长度是奇数时,那么它对折过来后,有一个的长度需要去掉一位数(除以 10 并取整)。
  • 复杂度分析:
    • 时间复杂度 $O(n/2)$ ,$N$ 表示数值包含元素长度 ,如果数值是回文数 最多需要遍历 $O(n/2)$ 次
    • 时间复杂度 $O(1)$
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;
    }
}