[LeetCode] 9. Palindrome Number

题目

Palindrome Number | LeetCode OJ

描述

判断一个数是否是回文数。所谓回文数，即是从数的高位往低位看与从低位往高位看，所看到的数字出现的顺序是一样的。

举例

1、121、123321、13531 等是回文数，但 12、135631 等就不是了。

提示

• 负数能是回文数吗？（比如 -1）；
• 如果采用整数逆序的方式，但整数会溢出，可能会使问题变得复杂；
• 考虑采用一种更通用的办法来解问题；

要求

• 不要转换成字符串来判断（不要分配额外的空间）；

思路

假设这个数是 x = 12345，那么 x / 10000 == 1 为其最高位（MSB），x % 10 == 5 为其最低位（LSB）。

代码

class Solution{
public:
	bool isPalindrome(int x){
        // 负数都不是回文数
		if( x<0 ) return false;

        // 先找到与其位数相同的最小的数
		long long base = 1;
		while(base < x) 
			base *= 10;
		if(base>=10) 
			base /= 10;

        // 循环并判断当前的最高位与最低位是否相等
		while( x != 0 ){
			auto msb = x / base;
			auto lsb = x % 10;

			if( msb != lsb )
				return false;

			x %= base;
			x /= 10;

			base /= 100;
		}
		
		return true;
	}
};