7. Reverse Integer，反转整数

整数默认是signed，在申明时，如果需要unsigned，反而是需要将unisgned写出来。很多时候我们使用int32_t或uint32_t这类定义，容易忽略了默认signed的事实！

输入一个32位的signed integer，按位反转，保持符号不变，去掉反转后前面的0，如果反转后的数字overflow，返回0。要求不允许使用64位整数。（这个要求对Python无效，这个地方也是用C/C++的难点，如何判断溢出）

Example 1:
Input: x = 123
Output: 321

Example 2:
Input: x = -123
Output: -321

Example 3:
Input: x = 120
Output: 21

Python的大干快上

没啥算法，按照题意直接写，利用slicing操作反转：（Python这样的高高级语言，没有unsigned的概念）

class Solution:
    def reverse(self, x: int) -> int:
        a = int(str(abs(x))[::-1]) * (1 if x>=0 else -1)
        return a if -0x80000000<=a<0x80000000 else 0

$ python -m timeit -p -s 's=1;a=1234' '(-a,a)[s==1]'
5000000 loops, best of 5: 55.5 nsec per loop
$ python -m timeit -p -s 's=1;a=1234' 'a if s==1 else -a'
20000000 loops, best of 5: 19.9 nsec per loop

及时判断溢出

在拼装反转int的过程中，及时判断是否溢出。Python的实现作为参考，主要看C/C++的实现和速度。

Python

class Solution:
    def reverse(self, x: int) -> int:
        sign = 1 if x>=0 else -1
        x = abs(x)
        a = 0
        if x//(10**9) == 0:
            while x:
                a = a*10 + x%10
                x //= 10
        else:
            ob = (2,1,4,7,4,8,3,6,4)+((7,) if sign==1 else (8,))
            edge = True
            for i in range(10):
                b = x % 10
                if edge:
                    if b < ob[i]:
                        edge = False
                    elif b > ob[i]:
                        return 0
                a = a*10 + b
                x //= 10
        return sign * a

发现一个细节，Python代码中那些作为常量的顺序结构，用tuple的速度比list快很多：

$ python -m timeit -p '(1,2,3,4,5)'
50000000 loops, best of 5: 6.64 nsec per loop
$ python -m timeit -p '[1,2,3,4,5]'
5000000 loops, best of 5: 43.3 nsec per loop
$ python -m timeit -p '(1,2,3,4,5)+(6,7,8)'
50000000 loops, best of 5: 6.59 nsec per loop
$ python -m timeit -p '[1,2,3,4,5]+[6,7,8]'
2000000 loops, best of 5: 105 nsec per loop

C++

class Solution {
public:
    int reverse(int x) {
        if(x == 0x80000000)
            return 0;
        int mask { x>>31 };
        int sign { (x!=0)|mask };
        x = (x^mask) - mask;
        int a {};
        if(x/1000000000 == 0)
            while(x){
                a = a*10 + x%10;
                x /= 10;
            }
        else{
            vector<int> obits {2,1,4,7,4,8,3,6,4,7};
            obits[9] -= mask;
            bool overflow {true};
            for(int i{}; i<10; ++i){
                int b {x % 10};
                if(overflow){
                    if(b > obits[i])
                        return 0;
                    else if(b < obits[i])
                        overflow = false;
                }
                a = a*10 + b;
                x /= 10;
            }
        }
        return sign * a;
    }
};

开头直接处理唯一的一种特殊情况，因为这个最大的负数做abs是不合适的。请看下面示例：

#include <iostream>
using namespace std;

int main(void) {
    int a { (int)0x80000000 };
    int b { a+1 };
    a = abs(a);
    b = abs(b);
    cout << a << endl;
    cout << b << endl;
    return 0;
}

-2147483648
2147483647

int reverse(int x){
    if(x == 0x80000000)
        return 0;
    int mask = x >> 31;      // 0, -1
    int sign = (x!=0)|mask;  // -1, 0, 1
    x = (x^mask) - mask;     // abs
    int a = 0;
    if(x/1000000000 == 0)
        while(x){
            a = a*10 + x%10;
            x /= 10;
        }
    else{
        int obits[10] = {2,1,4,7,4,8,3,6,4,7};
        obits[9] -= mask;  // +0, +1
        bool overflow = true;
        for(int i=0; i<10; ++i){
            int b = x % 10;
            if(overflow){
                if(b > obits[i])
                    return 0;
                else if(b < obits[i])
                    overflow = false;
            }
            a = a*10 + b;
            x /= 10;
        }
    }
    return sign * a;
}

模运算也能得到负值（C）

int reverse(int x){
    int r = 0;
    while(x){
        if(r>INT_MAX/10 || r<INT_MIN/10)
            return 0;
        r = r*10 + x%10;
        x /= 10;
    }
    return r;
}

这段代码为什么OK？因为当x为负数的时候，x%10可以得到负值。具体请参考：模运算（求余）的坑。这个算法仅C/C++，Python没有缘分。我喜欢这个简单简洁的算法！

7. Reverse Integer，反转整数

题目分析

Python的大干快上

及时判断溢出

Python

C++

C

模运算也能得到负值（C）