Énoncé du problème :

Étant donné un tableau entier nums, renvoie une réponse de tableau telle que la réponse[i] est égale au produit de tous les éléments de nums sauf nums[i].

Le produit de tout préfixe ou suffixe de nombres est garanti pour tenir dans un entier de 32 bits.

Vous devez écrire un algorithme qui s'exécute en un temps O(n) et sans utiliser l'opération de division.

Exemple 1:

• Entrée : nombres = [1,2,3,4]
• Sortie : [24,12,8,6]

Exemple 2 :

• Entrée : nombres = [-1,1,0,-3,3]
• Sortie : [0,0,9,0,0]

Contraintes:

• 2
• -30
• Le produit de tout préfixe ou suffixe de nombres est garanti pour tenir dans un entier de 32 bits.

Suivi:

Pouvez-vous résoudre le problème de la complexité spatiale supplémentaire O(1) ? (Le tableau de sortie ne compte pas comme espace supplémentaire pour l'analyse de la complexité de l'espace.)

Processus de réflexion initial :

Pour résoudre ce problème, nous devons calculer le produit de tous les éléments sauf l'élément actuel sans utiliser l'opération de division. Cela peut être fait en utilisant deux passes sur le tableau :

1. Calculez les produits de préfixe pour chaque élément.
2. Calculez les produits de suffixe pour chaque élément et multipliez par les produits de préfixe.

Solution basique:

Nous pouvons utiliser deux tableaux pour stocker les produits de préfixe et de suffixe, puis les multiplier pour obtenir le résultat final.

Code:

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    const prefixProducts = new Array(n).fill(1);
    const suffixProducts = new Array(n).fill(1);
    const result = new Array(n).fill(1);

    // Compute prefix products
    for (let i = 1; i = 0; i--) {
        suffixProducts[i] = suffixProducts[i   1] * nums[i   1];
    }

    // Compute the result by multiplying prefix and suffix products
    for (let i = 0; i 




  
  
  Analyse de la complexité temporelle :

• Complexité temporelle : O(n), où n est la longueur du tableau. Nous parcourons le tableau trois fois.
• Complexité spatiale : O(n), pour stocker les produits de préfixe et de suffixe.

Limites:

La solution de base fonctionne bien mais utilise un espace supplémentaire pour stocker les produits de préfixe et de suffixe.

Solution optimisée :

Nous pouvons optimiser la solution pour utiliser l'espace supplémentaire O(1) en utilisant d'abord le tableau de sortie pour stocker les produits de préfixe, puis le modifier sur place pour inclure les produits de suffixe.

Code:

function productExceptSelfOptimized(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(1);

    // Compute prefix products in the result array
    for (let i = 1; i = 0; i--) {
        result[i] = result[i] * suffixProduct;
        suffixProduct *= nums[i];
    }

    return result;
}

Analyse de la complexité temporelle :

• Complexité temporelle : O(n), où n est la longueur du tableau. Nous parcourons le tableau deux fois.
• Complexité de l'espace : O(1), car nous utilisons le tableau de sortie pour stocker les résultats intermédiaires et n'utilisons aucun espace supplémentaire.

Améliorations par rapport à la solution de base :

• La solution optimisée réduit la complexité de l'espace à O(1) en utilisant le tableau de sortie pour les résultats intermédiaires.

Cas extrêmes et tests :

Cas extrêmes :

1. Le tableau contient zéro(s).
2. Le tableau contient des nombres négatifs.
3. La longueur du tableau est la limite minimale (2) ou maximale (10^5).

Cas de tests :

console.log(productExceptSelf([1,2,3,4])); // [24,12,8,6]
console.log(productExceptSelf([-1,1,0,-3,3])); // [0,0,9,0,0]
console.log(productExceptSelf([2,2,2,2])); // [8,8,8,8]
console.log(productExceptSelf([0,0])); // [0,0]
console.log(productExceptSelf([5])); // This should not be a valid input as the minimum length is 2
console.log(productExceptSelf([1,2])); // [2, 1]

console.log(productExceptSelfOptimized([1,2,3,4])); // [24,12,8,6]
console.log(productExceptSelfOptimized([-1,1,0,-3,3])); // [0,0,9,0,0]
console.log(productExceptSelfOptimized([2,2,2,2])); // [8,8,8,8]
console.log(productExceptSelfOptimized([0,0])); // [0,0]
console.log(productExceptSelfOptimized([5])); // This should not be a valid input as the minimum length is 2
console.log(productExceptSelfOptimized([1,2])); // [2, 1]

Stratégies générales de résolution de problèmes :

1. Comprendre le problème : Lisez attentivement l'énoncé du problème pour comprendre les exigences et les contraintes.
2. Identifier les opérations clés : Déterminez les opérations clés nécessaires, telles que les produits de préfixe et de suffixe informatique.
3. Optimiser pour la lisibilité : Utilisez une logique claire et concise pour garantir que le code est facile à suivre.
4. Testez de manière approfondie : Testez la solution avec divers cas, y compris les cas extrêmes, pour garantir son exactitude.

Identifier des problèmes similaires :

1. Tableau de somme de préfixes :

   • Problèmes pour lesquels vous devez calculer les sommes de préfixes pour les requêtes par plage.
   • Exemple : requête de somme de plage.

2. Algorithmes sur place :

   • Problèmes où les opérations doivent être effectuées sur place avec un espace supplémentaire limité.
   • Exemple : faites pivoter un tableau vers la droite de k étapes.

3. Manipulation du tableau :

   • Problèmes pour lesquels vous devez modifier les tableaux en fonction de conditions spécifiques.
   • Exemple : déplacer les zéros à la fin d'un tableau.

Conclusion:

• Le problème du calcul du produit d'un tableau sauf soi peut être résolu efficacement en utilisant à la fois une approche de base avec un espace supplémentaire et une approche optimisée sur place.
• Comprendre le problème et le décomposer en parties gérables est crucial.
• L'utilisation d'une logique claire et l'optimisation de la lisibilité garantissent que la solution est facile à suivre.
• Les tests avec différents cas extrêmes garantissent la robustesse.
• Reconnaître les tendances des problèmes peut aider à appliquer des solutions similaires à d'autres défis.

En pratiquant de tels problèmes et stratégies, vous pouvez améliorer vos compétences en résolution de problèmes et être mieux préparé à relever divers défis de codage.