Chroniques de codage dactylographié : produit d'un tableau sauf soi

Énoncé du problème :

Étant donné un tableau entier nums, renvoie un tableau réponse tel que réponse[i] est égal 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 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 <= nums.length <= 10^5
• -30 <= nums[i] <= 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é spatiale.)

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 suffixes pour chaque élément et multipliez par les produits préfixes.

Solution de base :

Nous pouvons utiliser deux tableaux pour stocker les produits préfixe et 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 < n; i++) {
        prefixProducts[i] = prefixProducts[i - 1] * nums[i - 1];
    }

    // Compute suffix products
    for (let i = n - 2; 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 < n; i++) {
        result[i] = prefixProducts[i] * suffixProducts[i];
    }

    return result;
}

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 préfixe et 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 le tableau de sortie pour stocker d'abord 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 < n; i++) {
        result[i] = result[i - 1] * nums[i - 1];
    }

    // Compute suffix products and multiply with the prefix products
    let suffixProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] = result[i] * suffixProduct;
        suffixProduct *= nums[i];
    }

    return result;
}




<h3>
  
  
  Analyse de la complexité temporelle :
</h3>

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

<h3>
  
  
  Améliorations par rapport à la solution de base :
</h3>

<ul>
<li>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.</li>
</ul>

<h2>
  
  
  Cas extrêmes et tests :
</h2>

<h3>
  
  
  Cas extrêmes :
</h3>

<ol>
<li>Le tableau contient zéro(s).</li>
<li>Le tableau contient des nombres négatifs.</li>
<li>La longueur du tableau est la limite minimale (2) ou maximale (10^5).</li>
</ol>

<h3>
  
  
  Cas de tests :
</h3>



<pre class="brush:php;toolbar:false">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 minutieusement : 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 de 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 pas.

3. Manipulation des tableaux :

   • 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 self 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 pour la lisibilité garantissent que la solution est facile à suivre.
• Les tests avec différents cas extrêmes garantissent la robustesse.
• Reconnaître les schémas 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.

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!