Algorithmes et structures de données
J'ai l'intention d'utiliser ce référentiel comme un terrain de jeu de pratique (KATA) ainsi que comme un rappel de certains algorithmes communs, simples mais puissants. Où élégant j'utiliserai des transducteurs Clojure, qui sont de grands outils électriques pour traiter les séquences. Bien que ce document puisse sembler exhaustif, j'ai l'intention de l'utiliser comme une liste à laquelle je peux revenir à tout moment où j'ai besoin d'étudier. Je n'ai pas tout mis en œuvre répertorié ici.
Style d'écriture
Le code ici n'est pas façonné dans le style que j'utiliserais pour le codage professionnel. Chaque équipe a une culture et des opinions sur le style de code et il est préférable de s'en tenir à ces directives communes. De plus, le code est écrit principalement pour être lu par d'autres personnes, ou nous tous coderons en assemblage pour des performances maximales si nous devions cibler uniquement un lectorat de la machine. Le code que j'écris dans le cadre d'une équipe est destiné à avoir été écrit par quelqu'un d'autre dans cette équipe.
Le code ici est écrit en programmation littéraire grâce à EMACS et en mode org. Cela signifie que le code écrit en Clojure est dérivé des fichiers texte expliquant le raisonnement derrière. J'espère que cela facilite la lecture.
Python
Se préparer pour un nouveau problème
./dev-resources/new-problem.sh
--problem-path neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups
Voir --help .
Lorsque le script d'initialisation se termine, une commande suggérée pour les tests apparaîtra à la fin:
poetry run ptw -- --
src/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups.py
tests/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups_test.py
Interagir avec la poésie et Pytest
Par exemple, pour regarder les tests pendant le développement:
poetry run ptw
poetry run ptw -- -- --memray
poetry run ptw -- -- --benchmark-only
poetry run ptw -- -- --benchmark-skip
La petite danse autour -- -- pourrait probablement être évitée, mais je préfère être très explicite sur ce qui fonctionne, donc je garde poetry comme argument avant de gauche.
Pour obtenir une mémoire Flamegraph:
poetry run memray run -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4 "
poetry run python -m memray flamegraph memray-neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate.554244.bin
Pour obtenir un CPU FlameGraph (ou d'autres graphiques):
poetry run python -m cProfile -o program.prof -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4, 4 "
poetry run snakeviz program.prof
Pour exécuter des repères et obtenir un résumé graphique:
poetry run pytest --benchmark-only --benchmark-histogram
Liste d'études
Tri des algorithmes
- Implémentez à partir de zéro: tri à bulles, tri, tri rapide, tri de tas.
- Compte tenu d'un tableau d'entiers, trouvez le Kth le plus petit élément à l'aide de l'algorithme Quick Select.
- Implémentez l'algorithme de tri de comptage pour trier un tableau d'entiers avec une gamme connue de valeurs.
- Résolvez le problème "partition à trois voies" en utilisant un tri rapide pour trier efficacement un tableau avec des valeurs en double.
Recherche d'algorithmes
- Implémentation de zéro: recherche binaire (pour un tableau trié), recherche linéaire.
- Étant donné un tableau trié tourné, trouvez l'élément cible à l'aide de la recherche binaire modifiée.
Graphique, arbre et algorithmes de la traversée de celui-ci
- Implémentation de zéro: recherche de largeur (BFS), recherche en profondeur d'abord (DFS), algorithme de Dijkstra, algorithme Bellman-Ford.
- Implémentez différentes représentations: matrice d'adjacence, liste d'adjacence.
- Trouvez le chemin le plus court entre deux nœuds dans un graphique pondéré en utilisant l'algorithme de Dijkstra.
- Implémentez un arbre de recherche binaire et effectuez des opérations de base comme l'insertion, la suppression et la recherche.
- Étant donné un graphique dirigé, vérifiez s'il y a un itinéraire entre deux nœuds.
- Trouvez le nombre de composants connectés dans un graphique non dirigé.
- Implémentez le tri topologique pour un graphique acyclique dirigé (DAG).
- Trouvez l'ancêtre commun le plus bas (LCA) de deux nœuds dans un arbre binaire.
- Compte tenu d'un arbre binaire, vérifiez s'il s'agit d'un arbre de recherche binaire valide (BST).
- Compte tenu d'un graphique, trouvez tous les composants fortement connectés (SCC) à l'aide de l'algorithme de Kosaraju ou de l'algorithme de Tarjan.
- Implémentez l'algorithme Floyd-Warshall pour trouver les chemins les plus courts toutes les paires d'un graphique pondéré.
- Compte tenu d'un arbre N-ARE, effectuez une traversée d'ordre de niveau ou une traversée de profondeur d'abord (par exemple, pré-commande, post-ordre).
Programmation dynamique
- Comprendre le concept de rupture d'un problème en sous-problèmes de chevauchement plus petits et d'utilisation de la mémorisation ou de la tabulation.
- Résolvez le problème classique "Fibonacci" en utilisant à la fois des approches de programmation récursives et dynamiques.
- Étant donné un ensemble d'éléments avec des poids et des valeurs, trouvez la valeur maximale qui peut être obtenue avec un poids maximum donné en utilisant un problème de sac à dos 0-1.
Algorithmes gourmands
- Comprendre les problèmes où faire des choix localement optimaux conduit à une solution globalement optimale.
- Implémentez une solution pour le "problème de sélection d'activités" où vous devez sélectionner le nombre maximum d'activités qui ne se chevauchent pas.
- Étant donné un ensemble de pièces avec différentes dénominations et un montant, trouvez le nombre minimum de pièces nécessaires pour faire ce montant en utilisant une approche gourmand.
Algorithmes de retour en arrière
- Résolvez le problème "N-Queens" pour placer n queens sur un échangeur n × n sans s'attaquer.
- Implémentez un solveur Sudoku pour résoudre un puzzle Sudoku partiellement rempli.
Algorithmes de manipulation de chaînes
- Correspondance des cordes
- Inversion des cordes
- Chèques de palindrome
- Compte tenu de deux cordes, vérifiez si l'une est une permutation de l'autre.
- Implémentez l'algorithme "Rabin-Karp" pour trouver un modèle dans un texte donné.
Algorithmes de manipulation de bits
- Opérations bitwise, trouvant l'élément unique unique dans un tableau.
- Étant donné un tableau où tous les nombres se produisent deux fois, sauf pour un numéro, trouvez le numéro unique unique.
- Implémentez une fonction pour compter le nombre de bits défini sur 1 dans un entier.
Diviser et conquérir les algorithmes
- Recherche binaire, trouvant la somme maximale de sous-réseau.
- Implémentez l'algorithme Karatsuba pour la multiplication rapide de grands entiers.
- Trouvez la paire de points la plus proche parmi un ensemble de points dans l'espace 2D en utilisant l'approche Divide et Conquér.
Algorithmes randomisés
- Merger un tableau au hasard en place.
- Implémentez l'algorithme "SELECT randomisé" pour trouver le Kth le plus petit élément d'un tableau.
Technique de fenêtre coulissante
- Compte tenu d'un tableau d'entiers, trouvez la somme maximale de tout sous-réseau contigu de la taille k.
- Trouvez la sous-chaîne la plus longue avec au plus k caractères distincts dans une chaîne donnée.
Problèmes d'intervalle
- Compte tenu d'une liste d'intervalles, fusionnez les intervalles qui se chevauchent.
- Trouvez le nombre minimum de salles de réunion requises pour planifier une liste d'intervalles.
Essais
- Implémentez une structure de données TRIE pour une recherche et une récupération efficaces de chaînes.
- Compte tenu d'une liste de mots, trouvez le plus long préfixe commun à l'aide d'un Trie.
- Implémentez une fonctionnalité d'observation automatique à l'aide d'un Trie pour un ensemble donné de mots.
- Compte tenu d'une liste de mots, trouvez toutes les paires de mots de telle sorte que la concaténation forme un palindrome.
Hachage
- Implémentation des fonctions de hachage, des techniques de résolution de collision et des cas d'utilisation.
- Implémentez une table de hachage avec résolution de collision (par exemple, chaînage ou adressage ouvert).
- Trouvez le premier caractère non répété dans une chaîne à l'aide d'une carte de hachage.
- Implémentez l'algorithme Rabin-Karp pour la correspondance de chaînes avec plusieurs modèles.
- Trouvez la sous-chaîne la plus longue sans répéter les caractères en utilisant une carte de hachage pour la fréquence des caractères.
Tas
- Implémentation de Min-Heaps et Max-Heaps et de leurs applications (par exemple, files d'attente prioritaires).
- Implémentez un min-heap ou max-heap à partir de zéro.
- Compte tenu d'un tableau d'éléments, trouvez le Kth le plus grand élément à l'aide d'une approche basée sur un tas.
Manipulation de la matrice
- Compte tenu d'une matrice M × N, tournez-la de 90 degrés en place.
- Étant donné une matrice de 0 et 1, trouvez le plus grand carré de 1 (sous-matrice carrée maximale) et renvoyez sa zone.
Arbres rouges ou arbres AVL
- Implémentez les opérations d'insertion et de suppression pour un arbre rouge-noir ou un arbre AVL.
- Effectuez des rotations pour équilibrer un arbre de recherche binaire déséquilibré.
Implémentations de la structure des données
- Tableaux et listes: implémentation de tableaux, listes liées et leurs opérations.
- Stacks et files d'attente: implémentation de structures de données de pile et de file d'attente et leurs applications.
- Cartes de hachage: implémentation de cartes de hachage et compréhension de leur complexité temporelle.
Outils
Les algorithmes et les structures de données sont exposés par une simple API Restful pour un paramètre plus réaliste et pour un test plus robuste:
(Les outils répertoriés ici peuvent être spécifiques à certaines langues)
