[LeetCode 题解]:Palindrome Number

前言

 

【LeetCode 题解】系列传送门:  http://www.cnblogs.com/double-win/category/573499.html

 

1.题目描述

Determine whether an integer is a palindrome. Do this without extra space.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

2. 题意

判断一个整数是否是回文数。要求使用常量空间。

提示:

(1)负数是否是回文数?

(2)注意常量空间复杂度。将数字转换成字符串是不可行的。

3. 思路

如果将整个数字转换再判断是否是回文数,那么就可能出现反转之后的数字越界。

延续这个思路,能否通过某些技巧来避免越界呢?先看下面的例子:

(1) 1234321 / 12344321

将数字分成等长的两部分: 1234 和 4321。那么可以看出 4321 反转之后的数字为1234. 两者相等,所以1234321为回文数。

(2) 12345321

将数字分成等长的两部分: 1234 和 5321。那么可以看出 5321 反转之后的数字为1235.

由于1234!=1235,所以12345321不是回文数。

从上面两个例子可以看出。在处理一个数字是否是回文数的过程中,没有必要将整个数字反转。而只需要判断数字的前后等长的两部分时候相等即可。

那么如何在常量空间复杂度内,将数字分成前后两部分呢?

记 需要判断的数字为x,其前一部分为firstpart=x,后一部分为secondpart=0.

采取依次取firstpart的末位,将其添加到secondpart的尾部的方式,直到firstpart<=secondpart.

firstpart secondpart
1234321 0
123432 1
12343 12
1234 123
123 1234

当firstpart<secondpart时,只需反过来将secondpart最后一位转移到firstpart末位即可。

tmp=1234%10=4;

firstpart=firstpart*10+tmp=123*10+4=1234。

此时secondpart也为1234.

因此1234321为回文数。

4: 解法

class Solution {
public:
bool isPalindrome(int x) {
int first=x,second=0,tmp;
if(x==0) return true; //zero
if(x<0|| x%10==0) return false; //negative number or the number is dividable by 10 while(first>second){ // reverse the number
tmp=first%10;
second= second*10+tmp;
first/=10;
}
if(first==second) return true;
else{ // handle the number with odd digits
tmp = second%10;
first=first*10+tmp;
if(first==second) return true;
else return false;
}
return false;
}
};
作者:Double_Win
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接,否则作者保留追究法律责任的权利。  若本文对你有所帮助,您的关注推荐是我们分享知识的动力!
上一篇:C语言中所有变量和常量所使用的内存总结


下一篇:C语言中堆和栈的区别