Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Given a 32-bit signed integer x, return the result of reversing the numeric portion of x.

If the reversed integer exceeds the range of 32-bit signed integers [−2 ^31, 2 ^31 − 1], 0 is returned.

Assume that the environment does not allow storage of 64-bit integers (signed or unsigned).

Example 1:
Input: x = 123
Output: 321

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

Example 3:
Input: x = 120
Output: 21

Example 4:
Input: x = 0
Output: 0

hint:

-2 ^31 <= x <= 2 ^31 - 1
1

Algorithm 1, (not considering storing 64-bit integers): string reversal

#include <iostream>
#include <string>
#include <algorithm>
#include <climits>

class Solution {
public:
    int reverse(int x) {
        // 将整数转换为字符串
        std::string str = std::to_string(x);
        
        // 处理负号
        if (x < 0) {
            std::reverse(str.begin() + 1, str.end());
        } else {
            std::reverse(str.begin(), str.end());
        }
        
        // 将反转后的字符串转换回整数
        long rev = std::stoll(str);
        
        // 检查是否超出32位有符号整数范围
        if (rev > INT_MAX || rev < INT_MIN) {
            return 0;
        }
        
        return static_cast<int>(rev);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

It is relatively simple to ignore the situation where 64-bit integers cannot be stored, so I will not go into details.

Algorithm 2: Mathematical method

The complete code is as follows:

class Solution {
public:
    int reverse(int x) {
        int max = 2147483647;
        int min = -2147483648;
        int rev = 0;
        while(x != 0){
            if(rev > max / 10 || rev < min / 10){
                return 0;
            }
            int digit = x % 10;
            x /= 10;
            rev  = rev * 10 + digit;
            
        }
        return rev;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Analysis
The first step is to flip the shape:

// 弹出 x 的末尾数字 digit
digit = x % 10
x /= 10

// 将数字 digit 推入 rev 末尾
rev = rev * 10 + digit
1
2
3
4
5
6

Since x is a 32-bit integer, in order to avoid overflow, it is necessary to determine whether the result after reversal will exceed the range of 32-bit signed integers [−2 ^31, 2 ^31−1] before calculating rev for the last time.

Since the question requires that the environment cannot store 64-bit integers, it cannot be directly−2 ^ 31 ≤ rev⋅10+digit ≤2 ^ 31 −1。
Therefore, some mathematical methods are needed to ensure that the value of the integer does not exceed 32 bits during the calculation process. Here we can decompose the boundary value. Note:

min = −2 ^31 = -2147483648;
max = 2 ^31−1 = 2147483647;
1
2

To break it down:
min = (min/10) * 10 - 8;
max = (max/10) * 10 + 7;

When x>0,
rev * 10 + digit <= (max/10) * 10 + 7
=>
(rev - max/10)*10 <= 7 - digit;

When rev &lt; max/10:
That is, it is true when digit &lt;= 17, and since digit &lt;= 9, the equation is always true.

When rev = max/10:
digit <= 7;
If x can be decomposed at this time, it means that the number of digits in x is the same as max, and digit is the highest digit of x. Since x &lt;= 2 ^31 - 1 = 2147483647, the highest digit of x is 2, that is, digit &lt;= 2, so the equation always holds.

When rev &gt; max/10:
Since we are analyzing the situation when x&gt;0, this situation does not hold.

So it can be simplified to x &lt;= max/10, so in the code, when x&gt;max/10, you can return 0;

---

Next, we can analyze the situation when x&lt;0 in the same way.