回文数 Leecode 9. Palindrome Number

超、凢脫俗 2022-03-10 04:53 226阅读 0赞

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:
    
    Input: 121
    Output: true
    Example 2:
    
    Input: -121
    Output: false
    Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
    Example 3:
    
    Input: 10
    Output: false
    Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:  
Coud you solve it without converting the integer to a string?

我们先写几个数字：

-12321 //不是回文数
    6 //是回文数
    10 //不是回文数
    123454321 //是回文数
    12344321 //是回文数

设传入的数为x。这里我们需要判断一个数是否为回文数，首先小于10的数肯定是回文数，负数肯定不是回文数，十的倍数肯定不是回文数，这里我们可以提前确定。

if(x<0) return false;
    if(x<10) return true;
    if(x%10==0) return false;

以上条件是可以一眼看出来的，那大于10的回文数怎么判断呢，可以观察一下回文数的特性。

123454321

最高位等于最低位，次高位等于次低位，依次下去。我们想取得高位很麻烦，取到低位倒是很简单，可以用x%10获取到最低位。再用x/=10，我们可以通过循环从最低位到最高位依次获取到1,2,3,4,5,4,3,2,1。我们将这些获得到的数字\*10+下一位到最后不就是x？即设获取到的数是num，num = num\*10 + x%10；x = x/10；这种办法是行的通的，见下面代码

class Solution{ 
        public boolean isPalindrome(int x) { 
            if (x < 0 || (x != 0 && x%10 == 0)) return false;//小于0,10的倍数都不是回文数
            if (x < 10) return true;//小于10大于等于0的是回文数
            int num = 0;
            int temp = x;
            while (x != 0){ 
                num = num*10 + x%10;//从最低位开始算x的倒置值
                x = x/10;//除以10等下次循环获取次低位
            } 
            return num==temp;//如果倒置值等于x的值则是回文数返回true，否则false
        }
    }

这个方法将整个回文数都遍历一遍，很明显回文数是具有对称性的，有没有什么办法可以只遍历一半的回文数解决问题。

如果回文数位数是偶数位的话，例如123321，我们从最低位算倒置数时，遍历到一半，123 等于此时x（123），此时可以判定123321是回文数。

如果回文数位数是奇数位的话，例如1234321，我们从最低位算倒置数时，遍历到一半，123 ，剩下的x为1234，此时怎么判定呢？不管中间数（4）是多少只要此时倒置数等于x/10也能判定此数是回文数。

class Solution{ 
        public boolean isPalindrome(int x) { 
            if (x < 0 || (x != 0 && x%10 == 0)) return false;
            if (x < 10) return true;
            int num = 0;
            while (x > num){ //此时num不能大于x
                num = num*10 + x%10;
                x = x/10;
                if(num == x/10)return true;//奇数位回文数会在这里退出
            } 
            return x == num;//偶数位回文数会在这里退出
        }
    }

另一种写法：因为num不能大于等于x，num >= x时会跳出循环，此是如果x == num/10也是回文数（此时回文数是奇数位）。num == x时也是回文数（此时回文数是偶数位）。

class Solution{ 
        public boolean isPalindrome(int x) { 
            if (x < 0 || (x != 0 && x%10 == 0)) return false;
            if (x < 10) return true;
            int num = 0;
            while (x > num){ 
                num = num*10 + x%10;
                x = x/10;
            } 
            return x == num || x == num/10;
        }
    }