Leetcode Problem 7: Umgedrehter Integer

3/7/2024

Summary

Eine Lösung für LeetCodes „Reverse Integer“-Problem mithilfe von String-Konvertierung und Array-Manipulation, um Ziffern effizient umzukehren – inklusive Behandlung negativer Zahlen und Einhaltung der 32-Bit-Ganzzahnbeschränkung.

Einführung

Heute habe ich mein erstes Problem mittlerer Schwierigkeit auf LeetCode gelöst: Reverse Integer.
In diesem Artikel erkläre ich das Problem und meinen Lösungsansatz.
Wichtig: Das ist nur eine Möglichkeit, das Problem zu lösen und sicher nicht die perfekte.

Das Problem erklärt

Als Eingabe wird eine Ganzzahl x, wie x=123 oder x=-122, gegeben.
Die Ausgabe soll dann die gegebene Eingabe in umgekehrter Reihenfolge wieder ausgeben. Wenn die Ausgabe den vorzeichenbehafteten 32-Bit-Bereich [-2³¹ bis (2³¹)-1] überschreitet, sollte die Ausgabe 0 sein.
Beispiele:
Eingabe: x=123 => Ausgabe: x=321
Eingabe: -123 => Ausgabe: -321
Eingabe: x=120 => Ausgabe: x=21

Die Lösung

Die Grundidee

Die erste Idee, die mir in den Sinn kam, war, die Eingabe-Ganzzahl in ein Array umzuwandeln. Dies würde es mir ermöglichen, das Vorzeichen "-" zu extrahieren, falls die Zahl negativ ist, es in einer separaten Variable zu speichern und es aus dem Array zu entfernen. Auf diese Weise müsste ich nur mit einem Array von Ganzzahlen arbeiten.
Danach müsste ich das Array umkehren und es zurück in eine Ganzzahl konvertieren.
Schließlich müsste ich prüfen, ob die Ganzzahl in den 32-Bit-Bereich fällt. Falls die Eingabe negativ war, muss ich das Ergebnis wieder in eine negative Ganzzahl umwandeln.

1) Vorzeichen der Eingabe extrahieren

Mein initialer Ansatz zur Lösung dieses Problems beinhaltet also, die Eingabe in ein Array von Strings umzuwandeln und zu prüfen, ob die Zahl negativ ist.
Der Zustand des Vorzeichens sollte als boolesche Variable namens "positive" gespeichert werden. Im Code implementiert sieht das so aus:
var reverse = functions(x){
  let xArray = x.toString().split("");
  let positive = true;

  if(xArray[0] === "-"){
    positive = false;
    xArray.shift();
  }
}

2) Array umkehren und in Ganzzahl konvertieren

Nach dem Extrahieren des Minuszeichens, falls vorhanden, gehen wir zum nächsten Schritt über. Jetzt müssen wir das Array umkehren und es zurück in eine Ganzzahl konvertieren. Dies wird erreicht, indem wir das Array mit der eingebauten .reverse()-Funktion in JavaScript umkehren. Danach iterieren wir über das Array, das die Werte noch als Strings enthält, um sie in ein Array von Ganzzahlen zu konvertieren. Sobald wir diesen Schritt abgeschlossen haben, müssen wir das Array von Ganzzahlen zurück in eine einzelne Ganzzahl konvertieren und diese in einer Variable speichern.
//...
    xArray.reverse()
    let reversedXArray = []
    
    for(let i=0; i<xArray.length; i++){
        reversedXArray.push(parseInt(xArray[i], 10))
    }
    
    let number = parseInt(reversedXArray.join(''));
//...

3) Zahl in negativ umwandeln, falls Eingabe negativ war

Im dritten Schritt kehren wir zur Variable zurück, in der wir früher gespeichert haben, ob die Eingabe positiv oder negativ war. Falls die Eingabe ursprünglich negativ war, muss ich das Ergebnis mit -1 multiplizieren: 
//...
    if (!positive) {
        number *= -1;
    }
//...

4) Prüfung auf Ganzzahl im 32-Bit-Bereich

Ein letzter Schritt bleibt noch. Wenn man die Problembeschreibung sorgfältig liest, wird man bemerken, dass die finale Ausgabe 0 sein sollte, falls die Ganzzahl nicht in den 32-Bit-Bereich passt. Um dies im Code zu implementieren, schrieb ich eine kleine Hilfsfunktion, die true zurückgibt, wenn die Zahl in den 32-Bit-Bereich passt, und false, wenn nicht. Am Ende der Funktion prüfen wir, ob sie in den Bereich passt. Falls nicht, geben wir 0, andernfalls geben wir die Zahl zurück. 
function isInteger32Bit(num) {
    return num >= -(2**31) && num <= (2**31 - 1);
}

//...

    if(isInteger32Bit(number)===false){
        return 0
    }

    return number
};

5) Finaler Code 

function isInteger32Bit(num) {
    return num >= -(2**31) && num <= (2**31 - 1);
}
var reverse = function(x) {
    
    let xArray = x.toString().split("");
    let positive = true;
    
    if(xArray[0] === "-"){
        positive = false;
        xArray.shift();
    }
    
    xArray.reverse()
    let reversedXArray = []
    
    for(let i=0; i<xArray.length; i++){
        reversedXArray.push(parseInt(xArray[i], 10))
    }
    
    let number = parseInt(reversedXArray.join(''));
    
    if (!positive) {
        number *= -1;
    }
    
    if(isInteger32Bit(number)===false){
        return 0
    }

    return number
};
Schließlich kann ich die Lösung einreichen und prüfen, ob der Code korrekt ist.
Bingo! Laut LeetCode lag meine Laufzeit bei 76 ms, schneller als 39,46 % der JavaScript-Einreichungen.
Der Speicherverbrauch lag bei 52,5 MB und war damit besser als 62,26 %.
Kein Rekord, aber für den Anfang absolut solide.

Abschließende Worte

Ich hoffe, dir hat der Artikel gefallen.
Wenn du eine elegantere Lösung hast, dann schick sie mir gerne.
Dein Mario 💚