9. 回文数(java实现)--3种解法(暴力,数学,反转一半数字)LeetCode

9. 回文数(java实现)--3种解法(暴力,数学,反转一半数字)LeetCode,第1张

9. 回文数(java实现)--3种解法(暴力,数学,反转一半数字)LeetCode

文章目录

题目:解法1:暴力法解法2:数学方法解法3:反转一半数字

题目:

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

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

示例 1:

输入:x = 121
输出:true

示例 2:

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

示例 3:

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

示例 4:

输入:x = -101
输出:false

提示:

-231 <= x <= 231 - 1

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

解法1:暴力法
    public static boolean isPalindrome(int x) {
        String reverse = new StringBuilder(x+"").reverse().toString();
        return reverse.equals(x+"");
    }

时间复杂度:On

空间复杂度:O1

解法2:数学方法
    public static boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        int max = 1;
        while (x / max >= 10) {
            max *= 10;
        }
        int head = 0, end = 0;
        while (x > 0) {
            head = x / max;
            end = x % 10;
            if (head != end) {
                return false;
            }
            x = (x % max) / 10;
            max /= 100;
        }
        return true;
    }

时间复杂度:Ologn

空间复杂度:O1

解法3:反转一半数字
    public static boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        int reverse = 0;
        while (x > reverse) {
            reverse = reverse * 10 + x % 10;
            x /= 10;
        }
        return x == reverse || x == reverse / 10;
    }

时间复杂度:Ologn

空间复杂度:O1

思考:
为什么第一个判断条件要这样设置(x < 0 || (x % 10 == 0 && x != 0))?
因为10,20,。。100,1000。。。这样的数会导致后面奇数判断“x == reverse / 10”为true,必须优先过滤掉。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5721728.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-18
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存