Graphique, pas souvent testé
définition
Nœuds connectés entre eux sous forme de réseau
le terme
Edge : arête, une paire de nœuds
Algorithme de traversée
Recherche en largeur d'abord DFS
Recherche en profondeur TFS
Lié à l’entretien
Mettre en œuvre d'abord une recherche large et approfondie
Vérifiez si le graphique est un arbre
Compter le nombre d'arêtes dans un graphique
Trouver la distance la plus courte entre deux sommets
Pile monotone La pile monotone est rarement testée
File d'attente à double extrémité Deque, rarement testée
Union Find est rarement testé
Les arbres de segments de ligne sont rarement testés
Tableau d'arbres Arbre indexé binaire, BIT, rarement testé
Arbre de dictionnaire Trie, rarement testé
définition
Également connu sous le nom : arbre de préfixes, une structure de données spéciale de type arborescence
utiliser
Très efficace pour résoudre les problèmes liés aux chaînes
Fournir une recherche rapide
Rechercher un mot dans un dictionnaire
Suggestions automatiques dans les moteurs de recherche
entretien
Comptez le nombre total de mots dans l'arborescence du dictionnaire
Imprimer tous les mots stockés dans l'arborescence du dictionnaire
Trier les éléments d'un tableau à l'aide d'une arborescence de dictionnaire
Former des mots à partir d'un dictionnaire à l'aide d'un arbre de dictionnaire
Construire le dictionnaire T9 : Arborescence du dictionnaire DFS
Table de hachage/Hash Map Table de hachage, souvent testée
définition
Stockez des objets identifiés de manière unique sous la forme de paires clé-valeur
Dictionnaire : une collection de paires clé-valeur
Rechercher la valeur de l'objet à l'aide de la clé clé
HashSet/HashMap en Java, unordered_map en C, dict en Python
Opérations prises en charge : O(1) Insérer / O(1) Rechercher / O(1) Supprimer
Comment fonctionnent les tables de hachage
<br>Principe de fonctionnement : Pour set. La clé obtient un index via la fonction de hachage, puis la valeur est stockée dans le tableau. <br>Pour get, recherchez l'index via les fonctions de clé et de hachage et obtenez la valeur.
Pourquoi la complexité temporelle de diverses opérations sur le hachage ne peut-elle pas être simplement considérée comme étant O(1) ?
La clé peut être une chaîne, un entier ou quelque chose de longueur inconnue. Par conséquent, il est approprié d'utiliser O(L); au sens strict, la complexité temporelle de toute opération est O(keySize) plutôt que O(1)<br>
Comment implémenter la fonction de hachage
Comment résoudre une collision de hachage (Collision)
La collision signifie que deux clés différentes obtiennent deux valeurs identiques après calcul par la fonction de hachage. Il existe deux manières principales de résoudre les conflits :<br>Hashing ouvert. Cela signifie que dans le tableau sur lequel est basée la table de hachage, chaque position est le nœud principal d'une liste chaînée. De cette façon, les tuples <key, value> en conflit sont placés dans la même liste chaînée. <br>Hachage fermé. Cela signifie que lorsqu'un conflit survient, les éléments suivants iront à la position suivante pour trouver un espace vide<br>
Comment agrandir continuellement la table de hachage ?
facteurs de performance
Taille de la table de hachage
Méthode de gestion des collisions
entretien
Rechercher des paires clé-valeur symétriques dans un tableau
La table de hachage sera-t-elle utilisée de manière flexible pour résoudre le problème ?
Maîtrisez-vous les principes de base des tables de hachage ?
Suivez le chemin complet pour plus de commodité
Rechercher si un tableau est un sous-ensemble d'un autre tableau
Vérifie si les tableaux donnés sont disjoints
526. Équilibreur de charge<br>
134. Stratégie de cache LRU<br>657. Insérer Supprimer GetRandom O(1)<br>954. Insérer Supprimer GetRandom O(1) - Doublons autorisés<br>209.
Problèmes de classe Data Stream<br>960. Premier numéro unique dans un flux II<br>138. Somme des sous-tableaux<br>105. Copie d'une liste chaînée avec des pointeurs aléatoires<br>171. 124. séquence continue la plus longue
Trier la recherche
Trouver
table de recherche statique
table de recherche dynamique
Définition de la structure de données : Une structure de données peut être considérée comme une collection de stockage de données et plusieurs opérations (fonctions) définies sur cette collection.
Méthode de test 1 : Renseignez-vous sur les principes de base d'une certaine structure de données et demandez sa mise en œuvre
Exemple : Parler du principe du Hash et implémenter une table de Hash
Méthode de test 2 : utiliser une sorte de structure de données pour terminer les choses
Exemple : fusionner des tableaux ordonnés K
Méthode de test 3 : Implémenter une structure de données pour fournir certaines fonctions spécifiques
Exemple : problème d'élément K de fréquence la plus élevée
complexité temporelle :
Décrire la complexité temporelle de plusieurs interfaces<br>
Par exemple, vous devez concevoir une structure de données Set
Algorithme 1:O(n) lowerBound O(1) ajouter
Méthode de mise en œuvre : utiliser le stockage en tableau, comparer à chaque fois, insérer directement à l'extrémité du tableau
Algorithme 2 : O(logn) lowerBound O(logn) ajouter
Méthode d'implémentation : utiliser le stockage Tree rouge-noir, TreeSet en Java, map en C
Array Array, le plus couramment testé
taper
Tableaux multidimensionnels
sous-tableau
Questions d'entretien
41. 42,43, Sous-tableau maximum<br>44. Sous-tableau minimum<br>138.
Problème d'intervalle de tableau
Questions d'entretien
30. Insertion de plages<br>793. Intersection de plusieurs tableaux<br>156.
problème de tri externe
Définition : L'algorithme de tri externe fait référence à un algorithme permettant de trier les données stockées dans un ou plusieurs fichiers volumineux lorsque la mémoire est insuffisante. <br>
Deux étapes de base :<br>Coupez le gros fichier en plusieurs petits fichiers et utilisez la mémoire pour les trier respectivement<br>Utilisez l'algorithme de fusion K-way (fusion k-way) pour trier plusieurs petits fichiers et fusionner en un seul gros fichier
Questions d'entretien
486. Fusionner les tableaux triés K<br>104. Fusionner les listes triées K.
Opérations sur les bits
Définition : Opérations sur les bits binaires
Questions d'entretien
365. Combien y a-t-il de 1 en binaire<br>
Les tableaux d'arbres sont rarement pris en compte
Également connu sous le nom : Fenwick Tree Nom anglais : Binary Indexed Tree Abréviation : BIT est implémenté sur la base d'un préfixe et d'informations<br>
Bien que le nom soit Tree, il est stocké dans un tableau (Array)<br>BIT est un multi-arbre et la relation parent-enfant représente la relation d'inclusion<br>Utilisez getPrefixSum(k) pour implémenter getRangeSum(x, y )
complexité temporelle
Log(n) Modifier la valeur à n'importe quelle position<br>Log(n) Interroger la somme de n'importe quel intervalle
Caractéristiques
Pour un tableau avec N nombres, les fonctions suivantes sont prises en charge :<br>update(index, val) //Mettre à jour la valeur à une position du tableau dans le temps logN getPrefixSum(k) //Obtenir la valeur dans le temps log(K) La somme des K premiers nombres du tableau
Questions d'entretien
817. Variable de somme d'élément de matrice de plage<br>249. Comptez le nombre de nombres précédents plus petits que lui-même.
Lié à l’entretien
Trouver le deuxième plus petit élément d'un tableau
Trouver le premier entier non répétitif
Réorganiser les valeurs positives et négatives dans un tableau
65. Médiane de deux tableaux triés, problème difficile<br>
6. Fusionner les tableaux triés II<br>64. Fusionner les tableaux triés<br>839. Fusionner deux listes d'intervalles triées<br>486. Fusionner les tableaux triés<br>577. deux tableaux<br>548. Intersection de deux tableaux II<br>793. Intersection de plusieurs tableaux<br>654. Multiplication matricielle clairsemée<br>931. Médiane de K tableaux triés<br>149. temps<br>405. Sous-matrice dont la somme est nulle<br>944. Sous-matrice maximale<br>943. Requête de somme de plage - Immuable<br>665.
Stack Stack, pas souvent testé
définition
LIFO. Par exemple, lors du chargement logistique, les marchandises chargées ultérieurement sont déchargées en premier.
Opérations prises en charge : O(1) Push / O(1) Pop / O(1) Top
application
Utilisé pour la traversée non récursive d'arbres binaires, le calcul d'expressions polonaises inversées, etc.
La principale structure de données de la mise en œuvre non récursive de DFS
Dans la recherche en largeur d'abord (BFS), les nœuds à développer sont enregistrés.
Les files d'attente peuvent être utilisées pour implémenter des files d'attente de messages afin d'effectuer des tâches asynchrones.
Lorsque la vitesse de production et de consommation des messages est incohérente, une file d'attente de messages est nécessaire pour stocker temporairement les messages envoyés mais non reçus.
Implémenter le mode pile
Utiliser une structure de stockage (tableaux couramment utilisés, parfois listes chaînées) pour stocker les éléments
Utiliser un tableau pour implémenter trois piles ?
Implémenter une pile utilisant deux files d'attente ? <br>
la différence
Les tableaux ont de meilleures performances pour l'accès aléatoire. <br>Les listes chaînées ont de meilleures performances pour l'insertion et la suppression d'éléments.
Exercices<br>
lintcode : 495. Implémenter la pile
494. Pile d'implémentation à double file d'attente<br>
224. Utilisez un tableau pour implémenter trois piles<br>
fonctionner
pousser, insérer l'élément en haut
pop renvoie et supprime l'élément supérieur de la pile
isEmptyLa pile est vide et renvoie vrai
top renvoie l'élément supérieur sans le supprimer
Java utilise java.util.Stack, qui s'étend de la classe Vector et prend en charge des opérations telles que push(), pop(), peek(), empty() et search().
C, utilisez simplement la pile dans <stack>. La méthode est similaire à Java, sauf que peek() en C est appelé top(), et lorsque pop(), la valeur de retour est vide.
Python, utilisez la liste directement, utilisez des opérations de découpage comme [-1] pour afficher le haut de la pile, utilisez list.pop() pour faire apparaître le haut de la pile et utilisez list.append() pour pousser le haut de la pile . <br>
Lié à l’entretien
Utiliser la pile pour évaluer les expressions postfix
Trier les éléments de la pile
Déterminer si une expression est équilibrée entre parenthèses
QueueQueue, souvent testé
définition
Structure de données linéaire de stockage séquentiel FIFO premier entré, premier sorti, caisse de supermarché
Opérations prises en charge : O(1) Push / O(1) Pop / O(1) Top
application
Utilisé comme structure de données principale pour l'algorithme BFS
fonctionner
Insérer des éléments à la fin de la file d'attente
dequeue supprime l'élément de tête de la file d'attente
La colonne isEmpty est vide et renvoie vrai
top renvoie le premier élément de la file d'attente
Méthode pour réaliser
Implémenter la file d'attente à l'aide d'une liste chaînée ?
Implémenter une file d'attente avec deux piles ? <br>
Implémenter une file d'attente à l'aide d'un tableau circulaire ?
Exercice : 955. Implémenter une file d'attente par réseau circulaire<br>
entretien
Utiliser la file d'attente pour représenter la pile
Inverser les k premiers éléments de la file d'attente
Utilisez une file d'attente pour générer des nombres binaires de 1 à n
642. Moyenne mobile du flux de données<br>
955. Implémenter la file d'attente par réseau circulaire<br>
Liste chaînée, souvent testée
définition
Chaîne de nœuds : chaque nœud contient des données et des pointeurs vers les nœuds suivants
utiliser
Implémenter le système de fichiers, la table de hachage, la liste de contiguïté
taper
liste chaînée à sens unique
fonctionner
isEmpty, est vide, renvoie vrai
entretien
Détecter les cycles dans les listes chaînées
Renvoie le nième nœud du dernier dans la liste chaînée
Supprimer les doublons de la liste chaînée
ArbreArbre
définition
structure de données hiérarchique
Composé de sommets et d'arêtes
Il n'y a pas de cycles dans l'arborescence comme le montre le graphique
taper
Les arbres de segments de ligne ne sont fondamentalement pas testés, ils sont universels.
Arbre binaire, souvent testé
arbre de recherche binaire
Définition : le sous-arbre gauche est plus petit que le nœud racine et le nœud racine est plus petit que le sous-arbre droit. L'effet est le suivant : le côté gauche est toujours plus petit que le côté droit
arbre binaire équilibré
Arbre équilibré (arbre AVL)
définition:
Il s'agit d'un arbre vide ou la valeur absolue de la différence de hauteur entre ses sous-arbres gauche et droit ne dépasse pas 1, et les sous-arbres gauche et droit sont tous deux des arbres binaires équilibrés.
Mise en œuvre
Arbre rouge-noir, AVL, arbre bouc émissaire, Treap, arbre étalé
tas
Définition : Un tas est un arbre binaire équilibré. Le nœud parent est plus petit que le nœud enfant. Les nœuds enfants excédentaires sont placés autant que possible sur le nœud enfant gauche. Peut être implémenté à l'aide de tableaux<br>
Opérations prises en charge : O(log N) Ajouter / O(log N) Supprimer / O(1) Min ou Max
Tas maximum vs tas minimum
Caractéristiques de la valeur : pour le tas min, le nœud parent est plus petit que le nœud enfant, et il n'y a pas de relation de taille entre les nœuds enfants gauche et droit ; pour le tas de type max, le nœud parent est plus grand que le nœud enfant, et là il n'y a pas de relation de taille entre les nœuds enfants gauche et droit ;
Caractéristiques structurelles : C'est un arbre binaire de hauteur logN
Complexité temporelle : la complexité de suppression et de pop sont toutes logN, recherchez la complexité minimale ou maximale O(1)<br>
Méthode d'insertion : insérez toujours par la gauche, en garantissant un arbre binaire équilibré. Si le nombre inséré est petit, déplacez-le vers le haut et le nœud parent descend. La complexité maximale est donc logN<br>
La méthode de suppression est similaire à
Méthode d'implémentation : Exercice : lintcode 130 heapify<br>
Questions pratiques d'entretien
104. Fusionner K listes triées<br>612. K points les plus proches<br>545. Top K Big Numbers II<br>613 Excellents résultats<br>486. Fusionner K tableaux triés<br>81. chiffres<br>544. Top K grands nombres<br>401 Le kème nombre de petit à grand dans la matrice de tri.
Arbre de segments<br>
Définition : L'arbre de segments de ligne est une structure de données avancée et une structure arborescente, pour être précis, c'est un arbre binaire. Il peut gérer efficacement des problèmes tels que les requêtes de modification d'intervalle. <br>
Remarque : il n'est fondamentalement pas testé, mais si vous pouvez le maîtriser, vous pouvez résoudre de nombreux problèmes en une seule fois. L'arborescence des segments de ligne est implémentée sur la base de la méthode diviser pour régner et peut être utilisée comme une bonne pratique pour la division. et conquérir la méthode.
entretien
Trouver la hauteur d'un arbre binaire
Trouver la kième valeur maximale dans un arbre de recherche binaire
Trouver le nœud situé à la distance k du nœud racine
Trouver les nœuds ancêtres d'un nœud donné dans un arbre binaire
104. Fusionner les listes triées K<br>
3 façons
Méthode 1 : utiliser PriorityQueue
Méthode 2 : algorithme de division pour mieux régner similaire au tri par fusion
Méthode 3 : algorithme de fusion par paire ascendant
La complexité temporelle est O(NlogK)
Combiné avec : l'algorithme de Jiuzhang
Les questions pratiques sont toutes des questions de code lint
Wondershare EdrawMind
