Compartilhamento de tecnologia

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

Dado um inteiro assinado x de 32 bits, retorne o resultado da inversão da parte numérica de x.

Se o número inteiro invertido exceder o intervalo de um número inteiro com sinal de 32 bits [−2 ^31, 2 ^31 − 1], 0 será retornado.

Suponha que o ambiente não permita o armazenamento de números inteiros de 64 bits (assinados ou não assinados).

Exemplo 1:
Entrada: x = 123
Saída: 321

Exemplo 2:
Entrada: x = -123
Saída: -321

Exemplo 3:
Entrada: x = 120
Saída: 21

Exemplo 4:
Entrada: x = 0
Saída: 0

dica:

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

Algoritmo 1 (independentemente de armazenar inteiros de 64 bits): inversão de string

#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

É relativamente simples não considerar a situação em que números inteiros de 64 bits não podem ser armazenados, por isso não entrarei em detalhes.

Algoritmo 2: Método matemático

O código completo é o seguinte:

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

analisar
O primeiro passo é inverter a forma:

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

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

Como x é um número inteiro de 32 bits, para evitar estouro, é necessário determinar se o resultado revertido excederá o intervalo de um número inteiro assinado de 32 bits [−2 ^31, 2 ^31−1] antes de calcular rev pela última vez.

Como a questão exige que o ambiente não possa armazenar números inteiros de 64 bits, ela não pode ser diretamente−2 ^ 31 ≤ rev⋅10+digit ≤2 ^ 31 −1。
Portanto, alguns métodos matemáticos precisam ser adotados para evitar que valores superiores a números inteiros de 32 bits apareçam durante o processo de cálculo. Aqui os valores limite podem ser decompostos. lembrar:

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

Para decompô-lo:
mínimo = (min/10) * 10 - 8;
máx = (máx/10) * 10 + 7;

Quando x>0,
rev * 10 + dígito <= (máx./10) * 10 + 7
=>
(rev - máx/10)*10 <= 7 - dígitos;

Quando rev <máx/10:
Ou seja, pode ser verdade quando o dígito <= 17. Como o dígito <= 9, a equação sempre é válida.

Quando rev = máx/10:
dígito <= 7;
Se x ainda puder ser desmontado neste momento, significa que o número de dígitos em x é igual ao máximo, e neste momento o dígito é o dígito mais alto de x, e porque x <= 2 ^31 - 1 = 2147483647, o dígito mais alto de x é 2. Ou seja, dígito <= 2, então a equação sempre é válida.

Quando rev > máx/10:
Como a análise neste momento é a situação em que x>0, esta situação não se sustenta.

Portanto, pode ser simplificado para x <= max/10, portanto, no código, quando x>max/10, você pode retornar 0;

---

A seguir, a situação em que x<0 pode ser analisada da mesma forma.