. Différentes façons d'ajouter des parenthèses

241. Différentes façons d'ajouter des parenthèses

Difficulté :Moyen

Sujets : Mathématiques, Chaînes, Programmation Dynamique, Récursion, Mémorisation

Étant donné une expression de chaîne de nombres et d'opérateurs, renvoie tous les résultats possibles du calcul de toutes les différentes manières possibles de regrouper les nombres et les opérateurs. Vous pouvez renvoyer la réponse dans n'importe quel ordre.

Les cas de test sont générés de telle sorte que les valeurs de sortie tiennent dans un entier de 32 bits et que le nombre de résultats différents ne dépasse pas 10⁴.

Exemple 1 :

• Entrée : expression = "2-1-1"
• Sortie : [0,2]
• Explication :

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

Exemple 2 :

• Entrée : expression = "2*3-4*5"
• Sortie : [-34,-14,-10,-10,10]
• Explication :

  (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

Contraintes :

• 1 <= expression.length <= 20
• L'expression se compose de chiffres et de l'opérateur '+', '-' et '*'.
• Toutes les valeurs entières de l'expression d'entrée sont comprises dans la plage [0, 99].
• Les valeurs entières dans l'expression d'entrée n'ont pas de préfixe « - » ou « + » indiquant le signe.

Solution :

Nous pouvons utiliser la récursion combinée à la mémoisation pour stocker les résultats précédemment calculés pour les sous-expressions, car cela évite les calculs redondants et optimise la solution.

Approche:

1. Récursion :

   • Pour chaque opérateur de la chaîne (+, -, *), nous divisons l'expression au niveau de cet opérateur.
   • Calculez récursivement les parties gauche et droite de l'expression.
   • Combinez les résultats des deux parties à l'aide de l'opérateur.

2. Mémoisation :

   • Stockez les résultats des sous-expressions dans un tableau associatif pour éviter de recalculer plusieurs fois la même sous-expression.

3. Cas de base :

   • Si l'expression contient uniquement un nombre (c'est-à-dire aucun opérateur), renvoyez ce nombre comme résultat.

Exemple de procédure pas à pas :

Pour la saisie "2*3-4*5" :

• Diviser à * -> 2 et 3-4*5
  • Calculez récursivement 3-4*5 et 2, puis combinez.
• Partager à - -> 2*3 et 4*5
  • Calculez chacun de manière récursive et combinez-le.
• De même pour les autres fractionnements.

Implémentons cette solution en PHP : 241. Différentes façons d'ajouter des parenthèses

<?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]
?>

Explication:

1. Mémoisation : Le tableau $memo stocke les résultats calculés pour chaque expression afin d'éviter les calculs redondants.
2. Cas de base : lorsque l'expression est numérique, elle est convertie en entier et ajoutée aux résultats.
3. Partage récursif : pour chaque opérateur de l'expression, divisez-le en parties gauche et droite, calculez de manière récursive les résultats pour les deux parties, puis combinez-les en fonction de l'opérateur.
4. Exemple d'utilisation : La fonction diffWaysToCompute est testée avec des exemples d'expressions pour vérifier la solution.

Cette approche garantit que vous calculez efficacement tous les résultats possibles en tirant parti de la mémorisation pour éviter les calculs redondants.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!