Teknologian jakaminen

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

Kun annetaan 32-bittinen etumerkillinen kokonaisluku x, palauta x:n numeerisen osan invertointitulos.

Jos käänteinen kokonaisluku ylittää 32-bittisen etumerkillisen kokonaisluvun alueen [−2 ^31, 2 ^31 − 1], palautetaan 0.

Oletetaan, että ympäristö ei salli 64-bittisten kokonaislukujen (merkittyjen tai etumerkittömien) tallentamista.

Esimerkki 1:
Syöte: x = 123
Tulos: 321

Esimerkki 2:
Syöttö: x = -123
Lähtö: -321

Esimerkki 3:
Syöte: x = 120
Lähtö: 21

Esimerkki 4:
Syöte: x = 0
Lähtö: 0

vihje:

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

Algoritmi 1 (riippumatta 64-bittisten kokonaislukujen tallentamisesta): Merkkijonojen kääntäminen

#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

On suhteellisen helppoa olla ottamatta huomioon tilannetta, että 64-bittisiä kokonaislukuja ei voi tallentaa, joten en mene yksityiskohtiin.

Algoritmi 2: Matemaattinen menetelmä

Täydellinen koodi on seuraava:

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

jäsentää
Ensimmäinen vaihe on muodon kääntäminen:

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

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

Koska x on 32-bittinen kokonaisluku, ylivuodon välttämiseksi on ennen kierroksen laskemista määritettävä, ylittääkö käänteinen tulos 32-bittisen etumerkillisen kokonaisluvun alueen [−2 ^31, 2 ^31−1] viimeisen kerran.

Koska kysymys edellyttää, että ympäristö ei voi tallentaa 64-bittisiä kokonaislukuja, se ei voi olla suoraan−2 ^ 31 ≤ rev⋅10+digit ≤2 ^ 31 −1。
Siksi joitain matemaattisia menetelmiä on käytettävä, jotta estetään 32-bittisiä kokonaislukuja ylittävien arvojen ilmestyminen laskentaprosessin aikana. Täällä raja-arvot voidaan hajottaa. muistaa:

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

Purkaa se seuraavasti:
min = (min/10) * 10 - 8;
max = (max/10) * 10 + 7;

Kun x>0,
kierros * 10 + numero <= (max/10) * 10 + 7
=>
(kierros - max/10)*10 <= 7 - numero;

Kun kierrosluku < max/10:
Eli se voi olla totta, kun numero <= 17. Koska numero <= 9, yhtälö pätee aina.

Kun kierrosluku = max/10:
numero <= 7;
Jos x voidaan vielä purkaa tällä hetkellä, se tarkoittaa, että x:n numeroiden määrä on sama kuin max, ja tällä hetkellä numero on x:n suurin numero, ja koska x <= 2 ^31 - 1 = 2147483647, x:n suurin numero on 2. Eli numero<=2, joten yhtälö pätee aina.

Kun kierrosluku > max/10:
Koska analyysi tällä hetkellä on tilanne, kun x>0, tämä tilanne ei päde.

Joten se voidaan yksinkertaistaa muotoon x <= max/10, joten koodissa, kun x>max/10, voit palauttaa 0;

---

Seuraavaksi tilanne, kun x<0 voidaan analysoida samalla tavalla.