Condivisione della tecnologia

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

Dato un intero con segno a 32 bit x, restituisce il risultato dell'inversione della parte numerica di x.

Se l'intero invertito supera l'intervallo di un intero con segno a 32 bit [−2 ^31, 2 ^31 − 1], viene restituito 0.

Supponiamo che l'ambiente non consenta l'archiviazione di interi a 64 bit (con o senza segno).

Esempio 1:
Ingresso: x = 123
Produzione: 321

Esempio 2:
Ingresso: x = -123
Produzione: -321

Esempio 3:
Ingresso: x = 120
Produzione: 21

Esempio 4:
Ingresso: x = 0
Uscita: 0

suggerimento:

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

Algoritmo 1 (indipendentemente dalla memorizzazione di numeri interi a 64 bit): capovolgimento di stringhe

#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 semplice non considerare la situazione in cui gli interi a 64 bit non possono essere archiviati, quindi non entrerò nei dettagli.

Algoritmo 2: Metodo matematico

Il codice completo è il seguente:

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

analizzare
Il primo passo è capovolgere la forma:

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

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

Poiché x è un intero a 32 bit, per evitare overflow, è necessario determinare se il risultato invertito supererà l'intervallo di un intero con segno a 32 bit [−2 ^31, 2 ^31−1] prima di calcolare rev per l'ultima volta.

Poiché la domanda richiede che l'ambiente non possa memorizzare numeri interi a 64 bit, non può essere direttamente−2 ^ 31 ≤ rev⋅10+digit ≤2 ^ 31 −1。
Pertanto, è necessario adottare alcuni metodi matematici per evitare che durante il processo di calcolo appaiano valori superiori a 32 bit interi. Qui i valori limite possono essere scomposti. Ricordare:

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

Per scomporlo:
minimo = (min/10) * 10 - 8;
massimo = (massimo/10) * 10 + 7;

Quando x>0,
rev * 10 + cifra <= (max/10) * 10 + 7
=>
(giro - max/10)*10 <= 7 - cifra;

Quando giri < max/10:
Cioè, può essere vero quando la cifra <= 17. Poiché la cifra <= 9, l'equazione vale sempre.

Quando giri = max/10:
cifra <= 7;
Se x può ancora essere disassemblato in questo momento, significa che il numero di cifre in x è uguale a max, e cifra è la cifra più alta di x E poiché x <= 2 ^31 - 1 = 2147483647, la cifra più alta. di x è 2. Cioè cifra<=2, quindi l'equazione vale sempre.

Quando giri > max/10:
Poiché l'analisi in questo momento è la situazione in cui x>0, questa situazione non è valida.

Quindi può essere semplificato in x <= max/10, quindi nel codice, quando x>max/10, puoi restituire 0;

---

Successivamente, la situazione in cui x<0 può essere analizzata allo stesso modo.