[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;
	}
};

发表于:2014年10月31日 ,阅读量:485 ,标签:LeetCode

版权声明:若非特别注明,本站所有文章均为作者原创,转载请务必注明原文地址。