ALGO AND DS

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/16

flashcard set

Earn XP

Description and Tags

révisé les pattern des problème et les ds et les algorithmes

17 Terms

1
New cards

Principe du partitionnement en deux passes (Sort Colors)

Technique de tri en place pour trois valeurs distinctes (00, 11, 22) : une premiere boucle échange et accumule tous les 00 au début via un pointeur gauche, puis une seconde boucle échange et accumule tous les 22 à la fin via un pointeur droit, laissant mécaniquement les 11 au centre.

2
New cards

Complexités temporelle et spatiale du tri de couleurs en deux passes

Complexité temporelle de O(n)\mathcal{O}(n) (deux parcours complets du tableau de taille nn) et complexité spatiale de O(1)\mathcal{O}(1) (tri réalisé directement en mémoire sans tableau auxiliaire).

3
New cards

Rôle des pointeurs i0 et i2 dans l'algorithme Sort Colors fourni

i0 sert d'index cible pour placer le prochain élément 00 depuis le début du tableau, tandis que i2 sert d'index cible pour placer le prochain élément 22 depuis la fin du tableau.

4
New cards

Algorithme optimal alternatif réalisant le tri des couleurs en une seule passe

L'algorithme du drapeau hollandais (Dutch National Flag) de Dijkstra, qui utilise trois pointeurs simultanés pour classer les éléments en un seul parcours avec une complexité temporelle de O(n)\mathcal{O}(n) et spatiale de O(1)\mathcal{O}(1).

5
New cards

Comment résoudre le problème Majority Element II (éléments apparaissant \(> \lfloor n/3 \rfloor\) fois) en utilisant l'approche par Bucket Sort après avoir compté les fréquences ? (Donner les 3 grandes étapes)

  1. Compter les occurrences de chaque nombre avec une HashMap.

  2. Créer un tableau de listes (List<Integer>[] bucket = new List[n + 1]) où l'index représente la fréquence.

  3. Parcourir le bucket à partir de l'index (n/3) + 1 jusqu'à la fin pour récupérer les éléments majoritaires.


6
New cards

for (int key : occurence.keySet()){

int value = occurence.get(key);

// ... CODE À TROUVER ...

buket[value].add(key);

}


if (buket[value] == null){

buket[value] = new ArrayList<Integer>();

}

(Note : On vérifie si la liste à cet index de fréquence existe déjà, sinon on l'initialise avant d'ajouter la clé !)

7
New cards

Pour trouver les éléments apparaissant plus de \(n/3\) fois, à quel index i doit commencer la boucle de collecte dans le bucket ? (Compléter le code)

int most = n / 3;

// À compléter :

for (int i = ....... ; i < buket.length; i++)


for (int i = most + 1; i < buket.length; i++)

(Explication : On cherche strictement \(> n/3\), donc on commence obligatoirement à l'entier supérieur, c'est-à-dire most + 1).

8
New cards

Prefix Sum

Prefix Sum est un pattern algorithmique qui consiste à utiliser un tableau auxiliaire dans lequel chaque indice contient la somme des éléments du tableau original, du premier élément jusqu'à l'indice correspondant inclus.

9
New cards
Que contient prefix[i] ?
La somme des éléments de nums[0] à nums[i], inclus.
10
New cards
Comment calculer prefix[i] ?
prefix[i] = prefix[i - 1] + nums[i].
11
New cards
Comment initialiser le tableau Prefix Sum ?
prefix[0] = nums[0], si le tableau n'est pas vide.
12
New cards
Comment calculer la somme de nums[L..R] ?
prefix[R] - prefix[L - 1], si L > 0.
13
New cards
Comment calculer la somme de nums[0..R] ?
La réponse est directement prefix[R].
14
New cards
Quelle est la complexité de construction ?
O(n), car on parcourt le tableau une seule fois.
15
New cards
Quelle est la complexité d'une somme d'intervalle ?
O(1), après la construction du tableau Prefix Sum.
16
New cards
Quel problème suggère souvent Prefix Sum ?
Calculer plusieurs sommes de sous-tableaux ou d'intervalles.
17
New cards
Quel est le principal avantage de Prefix Sum ?
Éviter de recalculer les mêmes sommes pour chaque intervalle.