Maîtriser la manipulation de tableaux dans DSA à l'aide de JavaScript : des bases à l'avancée

Maîtriser la manipulation de tableaux en JavaScript pour DSA

Les tableaux sont des structures de données fondamentales en informatique et sont largement utilisés dans divers algorithmes et scénarios de résolution de problèmes. Ce guide complet vous présentera les bases de la manipulation de tableaux en JavaScript, couvrant des sujets allant des niveaux de base aux niveaux avancés. Nous explorerons le parcours, l'insertion, la suppression, la recherche et bien plus encore, ainsi que leurs complexités temporelles et des exemples pratiques.

Table des matières

1. Introduction aux tableaux
2. Traversée de tableau
3. Insertion dans des tableaux
4. Suppression dans les tableaux
5. Recherche dans des tableaux
6. Techniques avancées de manipulation de tableaux
7. Problèmes de pratique
8. Liens des problèmes LeetCode

1. Introduction aux tableaux

Un tableau est une collection d'éléments stockés dans des emplacements mémoire contigus. En JavaScript, les tableaux sont dynamiques et peuvent contenir des éléments de différents types.

Opérations de base sur les tableaux :

// Creating an array
let arr = [1, 2, 3, 4, 5];

// Accessing elements
console.log(arr[0]); // Output: 1

// Modifying elements
arr[2] = 10;
console.log(arr); // Output: [1, 2, 10, 4, 5]

// Getting array length
console.log(arr.length); // Output: 5

Complexité temporelle :

• Accès aux éléments : O(1)
• Modification d'éléments : O(1)
• Obtention de la longueur du tableau : O(1)

2. Traversée du tableau

La traversée signifie visiter chaque élément du tableau une fois. Il existe plusieurs façons de parcourir un tableau en JavaScript.

2.1 Utiliser une boucle for

let arr = [1, 2, 3, 4, 5];
for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
}

Complexité temporelle : O(n), où n est le nombre d'éléments dans le tableau.

2.2 Utilisation de forEach

let arr = [1, 2, 3, 4, 5];
arr.forEach(element => console.log(element));

Complexité temporelle : O(n)

2.3 Utilisation de la boucle for...of

let arr = [1, 2, 3, 4, 5];
for (let element of arr) {
    console.log(element);
}

Complexité temporelle : O(n)

3. Insertion dans des tableaux

L'insertion dans les tableaux peut être effectuée au début, à la fin ou à une position spécifique.

3.1 Insertion à la fin

let arr = [1, 2, 3];
arr.push(4);
console.log(arr); // Output: [1, 2, 3, 4]

Complexité temporelle : O(1) (amorti)

3.2 Insertion au début

let arr = [1, 2, 3];
arr.unshift(0);
console.log(arr); // Output: [0, 1, 2, 3]

Complexité temporelle : O(n), car tous les éléments existants doivent être décalés

3.3 Insertion à un emplacement spécifique

let arr = [1, 2, 4, 5];
arr.splice(2, 0, 3);
console.log(arr); // Output: [1, 2, 3, 4, 5]

Complexité temporelle : O(n), car les éléments après le point d'insertion doivent être décalés

4. Suppression dans les tableaux

Semblable à l'insertion, la suppression peut être effectuée au début, à la fin ou à une position spécifique.

4.1 Suppression depuis la fin

let arr = [1, 2, 3, 4];
arr.pop();
console.log(arr); // Output: [1, 2, 3]

Complexité temporelle : O(1)

4.2 Suppression depuis le début

let arr = [1, 2, 3, 4];
arr.shift();
console.log(arr); // Output: [2, 3, 4]

Complexité temporelle : O(n), car tous les éléments restants doivent être décalés

4.3 Suppression à une position spécifique

let arr = [1, 2, 3, 4, 5];
arr.splice(2, 1);
console.log(arr); // Output: [1, 2, 4, 5]

Complexité temporelle : O(n), car les éléments après le point de suppression doivent être décalés

5. Recherche dans des tableaux

La recherche est une opération courante effectuée sur les tableaux. Examinons quelques techniques de recherche.

5.1 Recherche linéaire

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

let arr = [1, 3, 5, 7, 9];
console.log(linearSearch(arr, 5)); // Output: 2
console.log(linearSearch(arr, 6)); // Output: -1

Complexité temporelle : O(n)

5.2 Recherche binaire (pour les tableaux triés)

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

let arr = [1, 3, 5, 7, 9];
console.log(binarySearch(arr, 5)); // Output: 2
console.log(binarySearch(arr, 6)); // Output: -1

Complexité temporelle : O(log n)

6. Techniques avancées de manipulation de tableaux

Explorons maintenant quelques techniques plus avancées de manipulation de tableaux.

6.1 Technique à deux pointeurs

La technique à deux pointeurs est souvent utilisée pour résoudre efficacement les problèmes de tableau. Voici un exemple d'utilisation de deux pointeurs pour inverser un tableau sur place :

function reverseArray(arr) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
}

let arr = [1, 2, 3, 4, 5];
reverseArray(arr);
console.log(arr); // Output: [5, 4, 3, 2, 1]

Complexité temporelle : O(n)

6.2 Technique de la fenêtre coulissante

La technique de la fenêtre coulissante est utile pour résoudre les problèmes de sous-réseaux. Voici un exemple pour trouver le sous-tableau de somme maximale de taille k :

function maxSumSubarray(arr, k) {
    let maxSum = 0;
    let windowSum = 0;

    // Calculate sum of first window
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;

    // Slide the window
    for (let i = k; i < arr.length; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

let arr = [1, 4, 2, 10, 23, 3, 1, 0, 20];
console.log(maxSumSubarray(arr, 4)); // Output: 39

Complexité temporelle : O(n)

6.3 L'algorithme de Kadane

L'algorithme de Kadane est utilisé pour trouver la somme maximale des sous-tableaux dans un tableau. C'est un exemple de programmation dynamique :

function kadane(arr) {
    let maxSoFar = arr[0];
    let maxEndingHere = arr[0];

    for (let i = 1; i < arr.length; i++) {
        maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;
}

let arr = [-2, -3, 4, -1, -2, 1, 5, -3];
console.log(kadane(arr)); // Output: 7

Complexité temporelle : O(n)

6.4 Algorithme du drapeau national néerlandais

Cet algorithme est utilisé pour trier un tableau contenant uniquement des 0, des 1 et des 2 :

function dutchNationalFlag(arr) {
    let low = 0, mid = 0, high = arr.length - 1;

    while (mid <= high) {
        if (arr[mid] === 0) {
            [arr[low], arr[mid]] = [arr[mid], arr[low]];
            low++;
            mid++;
        } else if (arr[mid] === 1) {
            mid++;
        } else {
            [arr[mid], arr[high]] = [arr[high], arr[mid]];
            high--;
        }
    }
}

let arr = [2, 0, 1, 2, 1, 0];
dutchNationalFlag(arr);
console.log(arr); // Output: [0, 0, 1, 1, 2, 2]

Complexité temporelle : O(n)

7. Problèmes de pratique

Voici 50 problèmes pratiques allant du niveau facile au niveau avancé. Certains d'entre eux proviennent de LeetCode, tandis que d'autres sont des scénarios courants de manipulation de tableaux :

1. Somme tous les éléments d'un tableau
2. Trouver l'élément maximum dans un tableau
3. Inverser un tableau sur place
4. Supprimer les doublons d'un tableau trié
5. Faire pivoter un tableau de k étapes
6. Trouver le deuxième plus grand élément d'un tableau
7. Fusionner deux tableaux triés
8. Trouvez le nombre manquant dans un tableau de 1 à n
9. Déplacez tous les zéros à la fin du tableau
10. Trouver l'intersection de deux tableaux
11. Trouver l'union de deux tableaux
12. Vérifier si un tableau est un sous-ensemble d'un autre tableau
13. Trouver l'indice d'équilibre dans un tableau
14. Réorganiser les nombres positifs et négatifs dans un tableau
15. Trouver l'élément majoritaire dans un tableau
16. Trouver l'élément de pointe dans un tableau
17. Implémenter un réseau circulaire
18. Trouver le plus petit nombre positif manquant dans un tableau
19. Problème de piégeage de l'eau de pluie
20. Implémenter une pile à l'aide d'un tableau
21. Implémenter une file d'attente à l'aide d'un tableau
22. Trouver la sous-séquence croissante la plus longue
23. Implémenter la recherche binaire dans un tableau trié avec rotation
24. Trouver la somme maximale d'un sous-tableau de taille k
25. Implémenter l'algorithme de Kadane
26. Trouver le nombre minimum de quais requis pour une gare
27. Trouvez le sous-tableau le plus long avec un nombre égal de 0 et de 1
28. Implémenter l'algorithme du drapeau national néerlandais
29. Trouver le plus petit sous-tableau dont la somme est supérieure à une valeur donnée
30. Mettre en œuvre l'algorithme de vote majoritaire Boyer-Moore
31. Trouver le sous-tableau de produits maximum
32. Implémenter l'algorithme Jump Game
33. Trouver l'élément supérieur suivant pour chaque élément d'un tableau
34. Implémenter l'algorithme Sliding Window Maximum
35. Trouver la sous-chaîne la plus longue sans répéter de caractères
36. Implémenter l'algorithme de fusion des intervalles
37. Trouver le nombre minimum de sauts pour atteindre la fin d'un tableau
38. Mettre en œuvre l'algorithme d'achat et de vente d'actions pour maximiser les profits
39. Trouver la sous-chaîne palindromique la plus longue
40. Implémenter l'algorithme de sous-séquence commune la plus longue
41. Trouver le sous-tableau continu non trié le plus court
42. Implémenter l'algorithme du conteneur avec le plus d'eau
43. Trouver la séquence consécutive la plus longue dans un tableau
44. Implémenter l'algorithme du produit maximum de trois nombres
45. Trouver le Kième plus grand élément d'un tableau
46. Implémenter l'algorithme Rechercher tous les doublons dans un tableau
47. Trouver la somme du sous-tableau de taille minimale
48. Implémenter l'algorithme Product of Array Except Self
49. Trouver l'écart maximum dans un tableau trié
50. Implémenter l'algorithme médiane de deux tableaux triés

8. Liens vers les problèmes LeetCode

Voici 20 problèmes LeetCode pour tester vos compétences en manipulation de tableaux :

1. Deux sommes
2. Meilleur moment pour acheter et vendre des actions
3. Contient des doublons
4. Produit du tableau sauf soi
5. Sous-tableau maximum
6. Fusionner les intervalles
7. 3Somme
8. Récipient contenant le plus d'eau
9. Faire pivoter le tableau
10. Recherche dans un tableau trié avec rotation
11. Trouver le minimum dans un tableau trié avec rotation
12. Prochaine permutation
13. La somme du sous-tableau est égale à K
14. Matrice spirale
15. Jeu de saut
16. Séquence consécutive la plus longue
17. Trouver tous les doublons dans un tableau
18. Kième plus grand élément d'un tableau
19. Pièger l'eau de pluie
20. Médiane de deux tableaux triés

En résolvant ces problèmes et en comprenant les concepts sous-jacents, vous améliorerez considérablement vos compétences en manipulation de tableaux en JavaScript pour les structures de données et les algorithmes.

N'oubliez pas que la clé pour maîtriser ces techniques est une pratique cohérente et une compréhension des complexités temporelles et spatiales de vos solutions.

Bon 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!