LeetCode 007 Reverse Integer 解题报告

2015-04-09

题目描述：
将一个整型的数字逆转，下面是英文描述

Reverse digits of an integer.

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

TIPs：

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.

Update (2014-11-10):

Test cases had been added to test the overflow behavior.

解题思路

如果你不愿意听我废话，那就先看代码：

int solution007::reverse(int x)
{
    const int max = 2147483647;

    const int min = -2147483648;

    double result = 0;
    while(x)
    {
        if(x > 0 && (result *unsigned(10)) > (max))
            return 0;
        if(x  < 0 && (result *unsigned(10)) < (min))
            return 0;
        result = result * 10 + x % 10;
        x /= 10;
    }
    return int(result);
}

我以前做过清华的ACM训练题，其中有不少都是关于大数计算的，比如求解2000的阶乘，这个问题当时用了一个下午才做出来，而且是用的交容易的方法，用数组来模拟计算过程，所以遇到这个数学模拟题，我的第一想法就是用数组模拟大数，再仔细一看，多虑了，于是顺手写下了下面的代码。

int solution007::reverse(int x)
{
	int result = 0;
    while(x)
    {
        result = result * 10 + x % 10;
        x /= 10;
    }
    return result;
}

结果自然是不能通过的，换做是在2012年，这个方法是可以通过这个测试用例的，在TIPs发现，这个题目在201年被修改过，需要考虑整数反转溢出的情况。
我尝试了各种方法来解决溢出问题，其中最直接的思想就是用一个取值范围更大的类型，来临时存储结果，若这个临时结果在×10后发生越界（大于整型的最大范围，或小于整型的最小值），就返回0（题目要求，在发生溢出的时候返回0）。
我的第一次尝试是用unsigned int，无论如何都不能成功。因为unsigned int所能表达的最大值只不过是int类型的两倍。
long类型是在介绍的时候虽然是比int类型的范围更大，但是在《C++ Primer 第四版》31页有这样的一句话通常在32位机器中int类型的字长与long类型的字长相同，long类型也不行。
最后只能用double类型了。于是有了我上面的代码。

int类型的数字到底有多大

我也记不住到底有多大，用程序输出一下就知道了：

int t = 0x7fffffff;
int tt = 0x80000000;
cout<<int(t)<<endl;
cout<<int(tt)<<endl;

参考

C++如何取得int型的最大最小值