Κοινή χρήση τεχνολογίας

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

Δεδομένου ενός ακέραιου x 32-bit υπογεγραμμένο, επιστρέψτε το αποτέλεσμα της αντιστροφής του αριθμητικού μέρους του x.

Εάν ο αντίστροφος ακέραιος υπερβαίνει το εύρος ενός ακέραιου αριθμού 32 bit [−2 ^31, 2 ^31 − 1], επιστρέφεται 0.

Ας υποθέσουμε ότι το περιβάλλον δεν επιτρέπει την αποθήκευση ακεραίων 64-bit (υπογεγραμμένων ή μη).

Παράδειγμα 1:
Είσοδος: x = 123
Έξοδος: 321

Παράδειγμα 2:
Είσοδος: x = -123
Έξοδος: -321

Παράδειγμα 3:
Είσοδος: x = 120
Έξοδος: 21

Παράδειγμα 4:
Είσοδος: x = 0
Έξοδος: 0

ίχνος:

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

Αλγόριθμος 1 (ανεξάρτητα από την αποθήκευση ακεραίων 64-bit): Αναστροφή συμβολοσειράς

#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

Είναι σχετικά απλό να μην εξετάσουμε την κατάσταση ότι οι ακέραιοι αριθμοί 64-bit δεν μπορούν να αποθηκευτούν, επομένως δεν θα υπεισέλθω σε λεπτομέρειες.

Αλγόριθμος 2: Μαθηματική μέθοδος

Ο πλήρης κώδικας έχει ως εξής:

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

αναλύω λέξη
Το πρώτο βήμα είναι να αναστρέψετε το σχήμα:

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

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

Δεδομένου ότι το x είναι ένας ακέραιος αριθμός 32 bit, για να αποφευχθεί η υπερχείλιση, είναι απαραίτητο να προσδιοριστεί εάν το αντίστροφο αποτέλεσμα θα υπερβεί το εύρος ενός ακέραιου αριθμού 32 bit [−2 ^31, 2 ^31−1] πριν από τον υπολογισμό των στροφών για τελευταία φορά.

Δεδομένου ότι η ερώτηση απαιτεί ότι το περιβάλλον δεν μπορεί να αποθηκεύσει ακέραιους αριθμούς 64-bit, δεν μπορεί να είναι απευθείας−2 ^ 31 ≤ rev⋅10+digit ≤2 ^ 31 −1。
Επομένως, πρέπει να υιοθετηθούν ορισμένες μαθηματικές μέθοδοι για να αποτραπεί η εμφάνιση τιμών που υπερβαίνουν τους ακέραιους αριθμούς των 32 bit κατά τη διαδικασία υπολογισμού. Εδώ οι οριακές τιμές μπορούν να αποσυντεθούν. θυμάμαι:

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

Για να το αναλύσετε:
min = (min/10) * 10 - 8;
max = (max/10) * 10 + 7;

Όταν x>0,
στροφές * 10 + ψηφίο <= (μέγ./10) * 10 + 7
=>
(στροφές - μέγ./10)*10 <= 7 - ψηφίο;

Όταν στροφές < max/10:
Δηλαδή, μπορεί να ισχύει όταν ψηφίο <= 17. Επειδή το ψηφίο <= 9, η εξίσωση ισχύει πάντα.

Όταν στροφές = max/10:
ψηφίο <= 7;
Εάν το x μπορεί ακόμα να αποσυναρμολογηθεί αυτή τη στιγμή, σημαίνει ότι ο αριθμός των ψηφίων στο x είναι ο ίδιος με το μέγιστο, και το ψηφίο είναι το υψηλότερο ψηφίο του x Και επειδή x <= 2 ^31 - 1 = 2147483647, το υψηλότερο ψηφίο. του x είναι 2. Δηλαδή ψηφίο<=2, άρα ισχύει πάντα η εξίσωση.

Όταν στροφές > max/10:
Δεδομένου ότι η ανάλυση αυτή τη στιγμή είναι η κατάσταση όταν x>0, αυτή η κατάσταση δεν ισχύει.

Έτσι μπορεί να απλοποιηθεί σε x <= max/10, οπότε στον κώδικα, όταν x>max/10, μπορείτε να επιστρέψετε 0.

---

Στη συνέχεια, η κατάσταση όταν το x<0 μπορεί να αναλυθεί με τον ίδιο τρόπο.