Compartir tecnología

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

Dado un entero x de 32 bits con signo, devuelve el resultado de invertir la parte numérica de x.

Si el entero invertido excede el rango de un entero con signo de 32 bits [−2 ^31, 2 ^31 − 1], se devuelve 0.

Supongamos que el entorno no permite el almacenamiento de enteros de 64 bits (con o sin signo).

Ejemplo 1:
Entrada: x = 123
Salida: 321

Ejemplo 2:
Entrada: x = -123
Salida: -321

Ejemplo 3:
Entrada: x = 120
Salida: 21

Ejemplo 4:
Entrada: x = 0
Salida: 0

pista:

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

Algoritmo 1 (independientemente de almacenar números enteros de 64 bits): inversión de cadenas

#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

Es relativamente sencillo no considerar la situación en la que no se pueden almacenar números enteros de 64 bits, por lo que no entraré en detalles.

Algoritmo 2: método matemático

El código completo es el siguiente:

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

analizar gramaticalmente
El primer paso es voltear la forma:

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

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

Dado que x es un entero de 32 bits, para evitar el desbordamiento, es necesario determinar si el resultado invertido excederá el rango de un entero de 32 bits con signo [−2 ^31, 2 ^31−1] antes de calcular rev por última vez.

Dado que la pregunta requiere que el entorno no pueda almacenar números enteros de 64 bits, no se puede resolver directamente.−2 ^ 31 ≤ rev⋅10+digit ≤2 ^ 31 −1。
Por lo tanto, es necesario adoptar algunos métodos matemáticos para evitar que aparezcan valores superiores a enteros de 32 bits durante el proceso de cálculo. Aquí se pueden descomponer los valores límite. recordar:

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

Para desglosarlo:
mín = (mín/10) * 10 - 8;
máx = (máx/10) * 10 + 7;

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

Cuando rev < máx/10:
Es decir, puede ser cierto cuando el dígito <= 17. Como el dígito <= 9, la ecuación siempre se cumple.

Cuando rev = máx/10:
dígito <= 7;
Si x todavía se puede desmontar en este momento, significa que el número de dígitos en x es el mismo que el máximo, y en este momento el dígito es el dígito más alto de x, y debido a que x <= 2 ^31 - 1 = 2147483647, el dígito más alto de x es 2. Es decir, dígito <= 2, por lo que la ecuación siempre se cumple.

Cuando rev > máx/10:
Dado que el análisis en este momento es la situación en la que x>0, esta situación no se cumple.

Por lo tanto, se puede simplificar a x <= max/10, por lo que en el código, cuando x>max/10, puede devolver 0;

---

A continuación, la situación en la que x<0 se puede analizar de la misma manera.