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
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);
}
};
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;
}
analysieren
Der erste Schritt besteht darin, die Form umzudrehen:
// 弹出 x 的末尾数字 digit
digit = x % 10
x /= 10
// 将数字 digit 推入 rev 末尾
rev = rev * 10 + digit
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 ^31−1 = 2147483647;
Um es aufzuschlüsseln:
min = (min/10) * 10 - 8;
max = (max/10) * 10 + 7;
Wenn x>0,
umdrehung * 10 + ziffer <= (max/10) * 10 + 7
=>
(Umdrehung - max./10)*10 <= 7 - Ziffer;
Wenn Drehzahl < max/10:
Das heißt, es kann wahr sein, wenn die Ziffer <= 17 ist. Da die Ziffer <= 9 ist, gilt die Gleichung immer.
Bei Drehzahl = max/10:
Ziffer <= 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 <= 2 ^31 - 1 = 2147483647, die höchste Ziffer von x ist 2. Das heißt, Ziffer<=2, also gilt die Gleichung immer.
Bei Drehzahl > max/10:
Da es sich bei der Analyse zu diesem Zeitpunkt um eine Situation mit x > 0 handelt, ist diese Situation nicht gegeben.
Es kann also zu x <= max/10 vereinfacht werden. Wenn im Code x> max/10 ist, können Sie 0 zurückgeben.
Als nächstes kann die Situation, wenn x<0 ist, auf die gleiche Weise analysiert werden.