Technologieaustausch

Likou 7. Detaillierte Erläuterung zweier Algorithmen zur Ganzzahlumkehr

2024-07-12

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

Geben Sie bei einer gegebenen 32-Bit-Ganzzahl x mit Vorzeichen das Ergebnis der Invertierung des numerischen Teils von x zurück.

Wenn die umgekehrte Ganzzahl den Bereich einer 32-Bit-Ganzzahl mit Vorzeichen [−2 ^31, 2 ^31 − 1] überschreitet, wird 0 zurückgegeben.

Gehen Sie davon aus, dass die Umgebung die Speicherung von 64-Bit-Ganzzahlen (mit oder ohne Vorzeichen) nicht zulässt.

Beispiel 1:
Eingabe: x = 123
Ausgabe: 321

Beispiel 2:
Eingabe: x = -123
Ausgabe: -321

Beispiel 3:
Eingabe: x = 120
Ausgabe: 21

Beispiel 4:
Eingabe: x = 0
Ausgabe: 0

Hinweis:

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

Algorithmus 1 (unabhängig von der Speicherung von 64-Bit-Ganzzahlen): String-Flipping

#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 ist relativ einfach, die Situation, dass 64-Bit-Ganzzahlen nicht gespeichert werden können, nicht zu berücksichtigen, daher werde ich nicht auf Details eingehen.

Algorithmus 2: Mathematische Methode

Der vollständige Code lautet wie folgt:

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

analysieren
Der erste Schritt besteht darin, die Form umzudrehen:

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

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

Da x eine 32-Bit-Ganzzahl ist, muss vor der Berechnung von rev ermittelt werden, ob das umgekehrte Ergebnis den Bereich einer 32-Bit-Ganzzahl mit Vorzeichen [−2 ^31, 2 ^31−1] überschreitet, um einen Überlauf zu vermeiden zum letzten Mal.

Da die Frage erfordert, dass die Umgebung keine 64-Bit-Ganzzahlen speichern kann, kann dies nicht direkt erfolgen−2 ^ 31 ≤ rev⋅10+digit ≤2 ^ 31 −1
Daher müssen einige mathematische Methoden angewendet werden, um zu verhindern, dass während des Berechnungsprozesses Werte angezeigt werden, die 32-Bit-Ganzzahlen überschreiten. Hier können die Grenzwerte zerlegt werden. erinnern:

min =2 ^31 = -2147483648;
max = 2 ^311 = 2147483647;
  • 1
  • 2

Um es aufzuschlüsseln:
min = (min/10) * 10 - 8;
max = (max/10) * 10 + 7;

Wenn x&gt;0,
umdrehung * 10 + ziffer &lt;= (max/10) * 10 + 7
=>
(Umdrehung - max./10)*10 &lt;= 7 - Ziffer;

Wenn Drehzahl &lt; max/10:
Das heißt, es kann wahr sein, wenn die Ziffer &lt;= 17 ist. Da die Ziffer &lt;= 9 ist, gilt die Gleichung immer.

Bei Drehzahl = max/10:
Ziffer &lt;= 7;
Wenn x zu diesem Zeitpunkt noch zerlegt werden kann, bedeutet dies, dass die Anzahl der Ziffern in x mit max übereinstimmt und die Ziffer die höchste Ziffer von x ist. Und weil x &lt;= 2 ^31 - 1 = 2147483647, die höchste Ziffer von x ist 2. Das heißt, Ziffer&lt;=2, also gilt die Gleichung immer.

Bei Drehzahl &gt; max/10:
Da es sich bei der Analyse zu diesem Zeitpunkt um eine Situation mit x &gt; 0 handelt, ist diese Situation nicht gegeben.

Es kann also zu x &lt;= max/10 vereinfacht werden. Wenn im Code x&gt; max/10 ist, können Sie 0 zurückgeben.


Als nächstes kann die Situation, wenn x&lt;0 ist, auf die gleiche Weise analysiert werden.