LeetCode腾讯精选练习50题-009.回文数

2022-04-06
阅读量 | 字数：638字 | 预计阅读时长：2分钟

题目描述

给定一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
进阶：不将整数转为字符串来解决这个问题

example
input  : 121
output : true
input  : -121
output : false

解题思路

先把一些很明确的情况排除掉
负数直接返回false即可，肯定不是回文数
[1, 10]内的数和10的倍数都肯定不是回文数

思路1 借助字符串

转成字符串后取其反转，再使用equals()函数做对比
时间复杂度：O(n)
空间复杂度：O(1)

思路2 同时取前后对比

先计算出x的长度len
借助循环，每一步都取出当前x的首位和末尾做对比
- 只要有一组不想等则直接返回false
- 每一步中若相等则将x先去掉首位再除以10获取新的x，并将len除以100，对应于新的x长度
时间复杂度：O(log(n))
空间复杂度：O(1)

思路3 反转一半后对比

将x的后半部分逐步取下，并通过数学运算不断拼接成新的整数 half
当x不再大于后半部分（x的长度比half短，或者长度相等但是x<=half）时结束拼接
判断以下两种情况是否成立，有一个成立则证明是回文数，可以返回true；两组都不成立则不是回文数
- 当前x 和 half 相等（原 x 长度为偶数）
- 当前x 和 half / 10 相等（原 x 长度为奇数；中间的数值x不论是几，x都是回文数）
时间复杂度：O(log(n))
空间复杂度：O(1)

代码（Java）

思路1代码

public class Solution1 {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0) && x != 0) {
            return false;
        }
        String sb = new StringBuffer(String.valueOf(x)).reverse().toString();

        return sb.equals(x + "");
    }
}

思路2代码

public class Solution2 {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0) && x != 0) {
            return false;
        }
        int len = 1;
        int y = x;
        while (y >= 10) {
            len *= 10;
            y /= 10;
        }
        y = x;
        while (y != 0) {
            if (y / len != y % 10) {
                return false;
            }
            y = (y % len) / 10;
            len /= 100;
        }
        return true;
    }
}

思路3代码

public class Solution3 {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0) && x != 0) {
            return false;
        }
        int rightHalf = 0;
        int y = x;
        while (y > rightHalf) {
            rightHalf = rightHalf * 10 + y % 10;
            y /= 10;
        }
        // 前者是偶数位数，后者是奇数位数
        return y == rightHalf || y == rightHalf / 10;
    }
}

本文作者： whtli
本文链接： https://hexo.whtli.cn/archives/688ebbf7.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。