. Verschiedene Möglichkeiten, Klammern hinzuzufügen

241. Verschiedene Möglichkeiten, Klammern hinzuzufügen

Schwierigkeit:Mittel

Themen: Mathematik, String, dynamische Programmierung, Rekursion, Memoisierung

Geben Sie bei einem gegebenen Zeichenfolgenausdruck aus Zahlen und Operatoren alle möglichen Ergebnisse aus der Berechnung aller verschiedenen Möglichkeiten zum Gruppieren von Zahlen und Operatoren zurück. Sie können die Antwort in beliebiger Reihenfolge zurücksenden.

Die Testfälle werden so generiert, dass die Ausgabewerte in eine 32-Bit-Ganzzahl passen und die Anzahl der unterschiedlichen Ergebnisse 10 nicht überschreitet⁴.

Beispiel 1:

• Eingabe: Ausdruck = "2-1-1"
• Ausgabe: [0,2]
• Erklärung:

  ((2-1)-1) = 0
  (2-(1-1)) = 2

Beispiel 2:

• Eingabe: Ausdruck = "2*3-4*5"
• Ausgabe: [-34,-14,-10,-10,10]
• Erklärung:

  (2*(3-(4*5))) = -34
  ((2*3)-(4*5)) = -14
  ((2*(3-4))*5) = -10
  (2*((3-4)*5)) = -10
  (((2*3)-4)*5) = 10

Einschränkungen:

• 1 <= expression.length <= 20
• Der Ausdruck besteht aus Ziffern und den Operatoren „+“, „-“ und „*“.
• Alle ganzzahligen Werte im Eingabeausdruck liegen im Bereich [0, 99].
• Die ganzzahligen Werte im Eingabeausdruck haben kein führendes „-“ oder „+“, das das Vorzeichen angibt.

Lösung:

Wir können Rekursion in Kombination mit Memoisierung verwenden, um zuvor berechnete Ergebnisse für Unterausdrücke zu speichern, da dies redundante Berechnungen vermeidet und die Lösung optimiert.

Ansatz:

1. Rekursion:

   • Für jeden Operator in der Zeichenfolge (+, -, *) teilen wir den Ausdruck an diesem Operator auf.
   • Rekursiv den linken und rechten Teil des Ausdrucks berechnen.
   • Kombinieren Sie die Ergebnisse beider Teile mit dem Operator.

2. Auswendiglernen:

   • Speichern Sie die Ergebnisse von Unterausdrücken in einem assoziativen Array, um zu vermeiden, dass derselbe Unterausdruck mehrmals neu berechnet wird.

3. Basisfall:

   • Wenn der Ausdruck nur eine Zahl enthält (d. h. keine Operatoren), geben Sie diese Zahl als Ergebnis zurück.

Beispielhafte Vorgehensweise:

Für die Eingabe „2*3-4*5“:

• Teilen bei * -> 2 und 3-4*5
  • Rekursiv 3-4*5 und 2 berechnen und dann kombinieren.
• Aufteilung bei - -> 2*3 und 4*5
  • Rekursiv berechnen und kombinieren.
• Ähnliches gilt für andere Teilungen.

Lassen Sie uns diese Lösung in PHP implementieren: 241. Verschiedene Möglichkeiten, Klammern hinzuzufügen

<?php
class Solution {

    /**
     * @var array
     */
    private $memo = [];

    /**
     * @param String $expression
     * @return Integer[]
     */
    public function diffWaysToCompute($expression) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $expression
     * @return array|mixed
     */
    private function compute($expression) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage
$solution = new Solution();
$expression1 = "2-1-1";
$expression2 = "2*3-4*5";
print_r($solution->diffWaysToCompute($expression1)); // Output: [0, 2]
print_r($solution->diffWaysToCompute($expression2)); // Output: [-34, -14, -10, -10, 10]
?>

Erläuterung:

1. Memoisierung: Das $memo-Array speichert die berechneten Ergebnisse für jeden Ausdruck, um redundante Berechnungen zu vermeiden.
2. Basisfall: Wenn der Ausdruck numerisch ist, wird er in eine Ganzzahl umgewandelt und zu den Ergebnissen hinzugefügt.
3. Rekursive Aufteilung: Teilen Sie jeden Operator im Ausdruck in einen linken und einen rechten Teil auf, berechnen Sie die Ergebnisse für beide Teile rekursiv und kombinieren Sie sie dann basierend auf dem Operator.
4. Beispielverwendung: Die diffWaysToCompute-Funktion wird mit Beispielausdrücken getestet, um die Lösung zu überprüfen.

Dieser Ansatz stellt sicher, dass Sie alle möglichen Ergebnisse effizient berechnen, indem Sie die Memoisierung nutzen, um redundante Berechnungen zu vermeiden.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt von. Verschiedene Möglichkeiten, Klammern hinzuzufügen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!