JAVA 牛牛

9. 回文数

  • May 08, 2020
  • 0 views
  • 难度：简单
  • 本题涉及算法： 算数 双向指针
  • 思路： 算数 双向指针
  • 类似题型:

题目 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;
    }
}
Search