Reverse Integer

 

第二道简单题，这道题主要是取余的思想，但我们平常遇到的位数较少的数字只要对个十百分别取余再拼起来就行了，这道题的话因为最大位数可以是[-2³¹,2³¹-1]，所以就要用到循环取余。

1. Given an integer x

以下循环，直到X为0：

2. X对10取余，获得其个位数

3. X/10 获得整数部分

4. 个位数乘以10，变为新数字的第一个数

这里值得注意的是，在C++里，-123/10=-12； -123%10 = -3。我记得和Python有所区别。（待查证）

class Solution {
public:
    int reverse(int x) {
        long long res=0;
        while(x){
            res = res*10+x%10;
            x = x/10;
        }
        return (res<INT_MIN ||res>INT_MAX)? 0:res; // don't forget to check overflow!!
    }
};

 非常容易错误的一个点就是数字的范围。我原来用int来存储res是明显不对的。

2^32是4294967296。题目里用的输入data type 是int就让我有些不解了..常用的几种数据类型存储范围如下：

• short int and int : -32,767 to 32,767. (-2¹⁵ +1 , 2¹⁵-1)
  
• unsigned short int and unsigned int : 0 to 65,535. (0, 2¹⁶-1)
• long int : -2,147,483,647 to 2,147,483,647. (-2³¹ +1 , 2³¹-1)
• unsigned long int : 0 to 4,294,967,295 (0, 2³²-1)

看了一下这个范围，即使是long int也没法满足我们的要求呀。所以我们要用到long long int，范围是

• long long int: -9,223,372,036,854,775,807 to 9,223,372,036,854,775,807 .(-2⁶⁴,2⁶⁴)
• unsigned long long int: 0 to 18,446,744,073,709,551,615

嘛，实际上远超过我们的要求了。但位数能用的也就是它了。最后用(res<INT_MIN ||res>INT_MAX)? 0:res; 来check overflow就行了。

我试了一下 res设置成long的话能够打败86.38%的人，但设置成long long的话只能打败55%的人了。这说明存储的数据类型也十分影响我们的running time的。在可行的范围内尽可能选择小的存储类型。不过话说我还是觉得这题根据题目要求应该选择long long啦，可能只是test case没有涉及到那么大的数吧。