Heim > Artikel > Backend-Entwicklung > . 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 überschreitet4.
Beispiel 1:
((2-1)-1) = 0 (2-(1-1)) = 2
Beispiel 2:
(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:
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.
Rekursion:
Auswendiglernen:
Basisfall:
Für die Eingabe „2*3-4*5“:
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] ?>
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:
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!