Berbagi teknologi

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

Diberikan bilangan bulat bertanda 32-bit x, kembalikan hasil inversi bagian numerik dari x.

Jika bilangan bulat terbalik melebihi rentang bilangan bulat bertanda 32-bit [−2 ^31, 2 ^31 − 1], 0 dikembalikan.

Asumsikan bahwa lingkungan tidak mengizinkan penyimpanan bilangan bulat 64-bit (bertanda tangan atau tidak bertanda tangan).

Contoh 1:
Masukan: x = 123
Keluaran: 321

Contoh 2:
Masukan: x = -123
Keluaran: -321

Contoh 3:
Masukan: x = 120
Keluaran: 21

Contoh 4:
Masukan: x = 0
Keluaran: 0

petunjuk:

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

Algoritma 1 (terlepas dari penyimpanan bilangan bulat 64-bit): Pembalikan 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

Relatif mudah untuk tidak mempertimbangkan situasi di mana bilangan bulat 64-bit tidak dapat disimpan, jadi saya tidak akan menjelaskan secara detail.

Algoritma 2: Metode matematika

Kode lengkapnya adalah sebagai berikut:

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

menguraikan
Langkah pertama adalah membalik bentuknya:

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

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

Karena x adalah bilangan bulat 32-bit, untuk menghindari luapan, perlu ditentukan apakah hasil yang dibalik akan melebihi rentang bilangan bulat bertanda 32-bit [−2 ^31, 2 ^31−1] sebelum menghitung rev untuk terakhir kalinya.

Karena pertanyaannya mengharuskan lingkungan tidak dapat menyimpan bilangan bulat 64-bit, maka tidak bisa secara langsung−2 ^ 31 ≤ rev⋅10+digit ≤2 ^ 31 −1。
Oleh karena itu, beberapa metode matematika perlu diterapkan untuk mencegah munculnya nilai yang melebihi bilangan bulat 32-bit selama proses perhitungan. Di sini nilai batas dapat diuraikan. Ingat:

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

Untuk memecahnya:
menit = (menit/10) * 10 - 8;
maks = (maks/10) * 10 + 7;

Ketika x>0,
rev * 10 + digit <= (maks/10) * 10 + 7
=>
(rev - maks/10)*10 <= 7 - angka;

Saat putaran < maks/10:
Artinya, bisa jadi benar jika angka <= 17. Karena angka <= 9, persamaannya selalu berlaku.

Ketika putaran = maks/10:
angka <= 7;
Jika x masih dapat dibongkar saat ini, berarti jumlah digit pada x sama dengan max, dan digit tersebut merupakan digit tertinggi dari x. Dan karena x <= 2 ^31 - 1 = 2147483647 maka digit tertingginya. dari x adalah 2. Artinya, angka<=2, sehingga persamaannya selalu berlaku.

Ketika putaran > maks/10:
Karena analisis saat ini adalah situasi ketika x>0, maka situasi ini tidak berlaku.

Jadi bisa disederhanakan menjadi x <= max/10, jadi di kodenya, ketika x>max/10, Anda bisa mengembalikan 0;

---

Selanjutnya, situasi ketika x<0 dapat dianalisis dengan cara yang sama.