美文网首页
Leetcode:判断一个整数是否是回文数。

Leetcode:判断一个整数是否是回文数。

作者: 星星xingxing1998 | 来源:发表于2020-01-20 20:12 被阅读0次

    题目:回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

    示例 1:
    输入: 121
    输出: true

    思路:

    个人解法(java):

    class Solution {
        public boolean isPalindrome(int x) {
            String s = String.valueOf(x);
            int len = s.length() / 2;
            for(int i = 0; i < len; i++) {
                if(s.charAt(i) != s.charAt(s.length() - i - 1)) {
                    return false;
                }
            }
            return true;       
        }
    }
    

    较优解法(来自leetcode官方):
    算法思想:直接反转数字可能会导致溢出,若该数字为回文数,则前后部分相反,故只反转数字的一半,反转边界:反转数字的部分比原数字剩下部分大
    例:对于数字 1221,如果执行 1221 % 10,我们将得到最后一位数字 1,要得到倒数第二位数字,我们可以先通过除以 10 把最后一位数字从 1221 中移除,1221 / 10 = 122,再求出上一步结果除以 10 的余数,122 % 10 = 2,就可以得到倒数第二位数字。如果我们把最后一位数字乘以 10,再加上倒数第二位数字,1 * 10 + 2 = 12,就得到了我们想要的反转后的数字。如果继续这个过程,我们将得到更多位数的反转数字。
    现在的问题是,我们如何知道反转数字的位数已经达到原始数字位数的一半?
    我们将原始数字除以 10,然后给反转后的数字乘上 10,所以,当原始数字小于反转后的数字时,就意味着我们已经处理了一半位数的数字。

    class Solution {
        public bool IsPalindrome(int x) {
            // 特殊情况:
            // 如上所述,当 x < 0 时,x 不是回文数。
            // 同样地,如果数字的最后一位是 0,为了使该数字为回文,
            // 则其第一位数字也应该是 0
            // 只有 0 满足这一属性
            if(x < 0 || (x % 10 == 0 && x != 0)) {
                return false;
            }
    
            int revertedNumber = 0;
            while(x > revertedNumber) {
                revertedNumber = revertedNumber * 10 + x % 10;
                x /= 10;
            }
    
            // 当数字长度为奇数时,我们可以通过 revertedNumber/10 去除处于中位的数字。
            // 例如,当输入为 12321 时,在 while 循环的末尾我们可以得到 x = 12,revertedNumber = 123,
            // 由于处于中位的数字不影响回文(它总是与自己相等),所以我们可以简单地将其去除。
            return x == revertedNumber || x == revertedNumber/10;
        }
    }
    
    image.png

    相关文章

      网友评论

          本文标题:Leetcode:判断一个整数是否是回文数。

          本文链接:https://www.haomeiwen.com/subject/dqqszctx.html