LeetCode 4, 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?

Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

cover-image

思考:

这道题我的思考过程是先想办法读取出这个整数的每一位，然后在组装，其间也有很多弯路慢慢完善。

一开始想到要判断符号位,在最后组装的时候可以保证符号位的准确，然后怎么读取出每一位呢？我只能想到笨办法，就是不停的对这个输入的整数以10为基做取模操作，比如321，先对10取余我们能得到末尾的1，然后以32再取余就能得到2，最后就能得到3了，而且这个顺序刚好就是我们要的顺序, 这样我们通过一个循环就能够得到我们需要的每一位数字了。

得到我们要的数字之后，怎么把它再按照要求的数序组装回去呢？这个地方我饶了些弯路，首先我刚开始是通过strlen的方法来读取命令行参数的长度，在以是否为负数来判断数字的长度，然后就可以组装了，但是当我以为这个方法可行的时候，发现原来LeetCode的输入就是整形不能用判断字符串长度的方法来搞，哈，这下傻了，看来还待在想想。

按照取每一位数字的方法，我们也可以以这种方式来给取到的每一位数字做乘积，也就是把它放到合适的位置上去。比如说321，我们拿到1之后，应该把它放到哪里去呢？我还是只想到了这个笨办法，就是在嵌套一个for循环，让321不停的被10除，直到最后比10小为止，在这个例子里，当拿到1之后，321 能被10 除两次，那么它的base就是100， 最后的计算结果就是1 * 100 = 100了。

按照这个思路写出的可以被Accept的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int reverse(int x) {
        int num = x;
        int rev = 0;
        while (num / 10 != 0)
        {
            int a = num % 10;
            int base = 1;
            for (int i = num; i >= 10 || i <= -10; i = i / 10)
            {
                base = base * 10;
            }
            rev = rev + a * base;
            num = num / 10;
        }
        return (rev + num);
    }
};

到这里，虽然结果能被接收，没有正负数，以及末尾的0的问题，但是对溢出还是没有考虑到，如果输入1000000003 结果就会溢出, 对溢出的行为应该怎么办呢？

网上看到了一个比较好的版本，基本思路是一样的，但是比我的代码精简了很多，而且比较清晰，我怎么就这么笨呢，人家一个while就搞定了，我还费事的搞两个，怎么就没有想到其实第一次拿到1之后放在第二次x10和第三次x10也是可以的啊，小学数学没过关啊。优化后的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int reverse(int x) {
    int num = x;
    long int rev = 0;
    int sign = 0;
    num > 0 ? sign = 1 : sign = -1;
    while (num / 10 != 0)
    {
        int a = num % 10;
        rev = rev * 10 + a;
        num = num / 10;
    }
    if (rev + num > INT_MAX)
        return INT_MAX;
    if (rev + num < INT_MIN)
        return INT_MIN;
    return (rev + num);
};