Reverse Integer

LeetCode
subject ： Reverse Integer
Python

Title Description ：

Given a 32-bit signed integer, reverse digits of an integer.

Example ：

Input: 123
Output: 321

There is a special point in the title ：32 position Integers ,32 The range of bit integers is [-2147483648, 2147483647].
If it's beyond that range , Then it's time to go back 0.
And in python in ,a/10 If not completely divisible , The result of direct calculation is floating point number . Need to use int(a/10).
I didn't notice this at the beginning of the question .

The result of solving the problem by yourself , It may be more cumbersome than that of the great God , But the idea is relatively clear ：
1. Treat negative numbers as positive numbers .
2. Store data bit by bit in the list , From the last digit of the original number to the first digit, it is stored in the list . If the list is empty and the last few digits of the original number are 0, Don't put it in the list .
3. Restore data upside down .
4. Judge the range of converted data , Is it a positive number or a negative number , Or more than 32 Range of bit data .

class Solution:
    def reverse(self, x):
        flag = 0
        if x < 0:
            flag = 1
            x = 0 - x
        a = x
        b = []
        while a != 0:
            if len(b) == 0 and a % 10 == 0:
                a = int(a / 10)
                continue
            b.append(a % 10)
        num = 0
        k = 1
        for i in range(len(b)):
            j = len(b) - 1 - i
            num += b[j] * k
            k = k * 10
        if flag == 0 and num <= 2**31-1:
            return num
        elif flag == 1 and num <= 2**31:
            return -num
        else:
            return 0

The complexity of time and space is O(log n)

The correct answer is C++ edition ：
The advantage of the algorithm is The space complexity is O(1) as well as The way to judge .
The space complexity is O(1)：
Get a remainder each time , All directly Previous multiplication 10 Add the new remainder . So you don't have to put the remainder in the list .
The way to judge ：
Before every ride , Judge rev Whether it will exceed 32 The range of bits . If not beyond , Then continue to multiply .

class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
            if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
};

in addition ： The following code can detect whether x There's spillover .

if (x * 10 / 10 !== x) {
   // overflow
}

however Python Written words , You can't follow this completely . because ：
1.a/10 If it's not divisible , What you get is a floating point number This has already been mentioned .
2. stay Python in ,-123%10 be equal to 7, This with C++ and Java The treatment of is different . Therefore, we need to judge the positive and negative numbers in advance .
Python version:

class Solution:
    def reverse(self, x):
        num = 0
        a = abs(x)
        while(a != 0):
            pop = a % 10
            num = num * 10 + pop
            a = int(a / 10)
        if x > 0 and num < 2**31:
            return num
        elif x < 0 and num <= 2**31:
            return -num
        else:
            return 0

Of course, there are more ingenious methods ：
Reverse the order after converting to a string ：

class Solution:
    def reverse(self, x):
        a = int(str(abs(x))[::-1])
        if a > 2**31 or (a == 2**31 and x > 0):
            return 0
        elif x > 0:
            return a
        else:
            return -a