`
qiemengdao
  • 浏览: 275875 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

判断一个整数是否是回文数

 
阅读更多

问题

判定一个正整数是否是一个回文数。例如12121是回文数,而1231不是回文数。


解法1:转换成字符串再判断

要判断一个整数是否是回文数,最自然的想法是把整数转换成一个字符串,然后根据回文的对称特性进行判断。数字转换为字符串可以通过itoa函数实现,判断字符串是否为回文字符串代码如下:

bool isPalindrome(string &str)
{
    int begin = 0, end = str.length()-1;
    while (begin < end) {
        if (str[begin] == str[end]) {
            begin++;
            end--;
        } else {
            return false;
        }
    }
    return true;
}

解法2:数字翻转法

因为是整数,所以可以求出该整数的翻转后的数值,看是否与原来整数相等。如果相等,则是回文数,否则不是。翻转整数代码如下,返回值为翻转后的整数。如12321翻转后为12321,所以是回文数;而1231翻转后为1321,与1231不相等,所以不是回文数。

int reverse(int num) 
{
  assert(num >= 0); 
  int rev = 0;
  while (num != 0) {
    rev = rev * 10 + num % 10;
    num /= 10;
  }
  return rev;
}
但是这里有个潜在的问题就是翻转后的整数可能会溢出,当然我们可以用long long之类的类型来保存翻转结果。但是这个解法总的来看并不完美,我们需要找一个更通用的解法。


解法3:数字位判断法

我们可以找到一个更通用的解法,那就是先比较整数的第1位和最后1位是否相等,如果不等,则直接返回false;若相等,则接下去判断剩下的位置,如同回文字符串判断的过程一样。代码如下:

bool isPalindrome(int x) 
{
  if (x < 0) return false;
  int div = 1;
  while (x / div >= 10) {
    div *= 10;
  }
  while (x != 0) {
    int l = x / div;  
    int r = x % 10;
    if (l != r) return false;
    x = (x % div) / 10;
    div /= 100;
  }
  return true;
}
如整数为121,则div初始会设为100,因此l=21/100=1是整数的第1位,而r=121%10=1是最后1位。这两位相等,则继续循环,设置x为第2为2,此时div除以100变成1,之所以div除以100是因为每次比较了两个位。



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics