leetcode：Reverse Integer 及Palindrome Number

Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

我比较认可的做法：

比较简洁，没有涉及到将整型转化为字符串，所以也不用特别处理正负的问题。
class Solution {
public:
    int reverse(int x) {
        int result=0;
        do{
            if((result>214748364)||(result<-214748364))
                return 0;
            result*=10;
            result+=(x%10);
        }while(x=x/10);
        return result;
    }
};

或：

class Solution {
public:
    int reverse(int x) {
        double res = 0;
        while (x){
            res = res * 10 + x % 10;
            x = x / 10;
        }
        return (res > INT_MAX || res < INT_MIN) ? 0 : res;
    }
};

看看几种其他的做法，拓展：

1、

class Solution {
public:
    int reverse(int x) {
    int flag = 0;
    if(x < 0)
    {
        flag = 1;
        x = abs(x);
    }
    string num;
    while(x)
    {
        num += x%10 + '0';     //'0'是空，字符串的结尾处用
        x /= 10;
    }
    int revx = 0;
    revx = std::atoi(num.c_str());    
if(revx%10 != (num[num.size() -1]-'0'))   //判断溢出
        return 0;
    if(flag)
        revx = 0-revx;
    return revx;
}
};

注：atoi()函数原型为: int atoi(char *str),用途是将字符串转换成一个整数值,str是待转化成整数值的字符串.成功则返回转化后的整数值,失败返回0.

c_str()函数原型为:const char *c_str(),如果要将string对象，转化为char*对象，c_str()提供了这样一种方法，它返回一个客户程序可读不可改的指向字符数组的指针。

2、

class Solution {
public:
    int reverse(int x) {

std::string s = std::to_string(x);//to_string函数--int to string
stringstream m;
int  s1;
int d;
int begin=0;
if (s[0]=='-'){
    begin++;
}
int k=s.length()+begin;
for(int i=begin;i<k/2;i++)      //左右两边对换
{
    s1=s[i];
    s[i]=s[k-1-i];
    s[k-1-i]=s1;
}
m<<s;//向流m中传值
m>>d;//向d中写入值

if (d<=-2147483648 || d>=2147483647){
    return 0;
}
return d;
}
};

注：http://blog.163.com/chen_dawn/blog/static/11250632010111215937586/ 中可详见c++stringstream的用法。

Palindrome Number

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.

回文数: 将这个数的数字按相反的顺序重新排列后,所得到的数和原来的数一样。

分析：首先想到，可以利用上一题，将整数反转，然后与原来的整数比较，是否相等，相等则为 Palindrome 的。可是 reverse() 会溢出。

正确的解法是，不断地取第一位和最后一位（10 进制下）进行比较，相等则取第二位和倒数第二位，直到完成比较或者中途找到了不一致的位。

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;//负数显然不是回文数
        int p1 = 0, p2 = x;
        while (p2 > 0) {
            p1 = p1*10 + p2%10;
            p2 /= 10;
        }
        return p1 == x;
    }
};

或：

class Solution {
public:
    bool isPalindrome(int x) {
    if(x<0)
    return false;
    int z=x;
    long y=0;
    while(z!=0)
    {
        y=y*10+z%10;
        z=z/10;
    }
    if(y>INT_MAX || y<INT_MIN || x!=y)
    return false;
    else 
    return true;
}
};