Page d'accueil>Lié à la programmation>C/C++
Télécharger

Problèmes de structure des données et d’algorithmes

Statut actuel Statistiques
Total des problèmes C++ 188
Problèmes totaux avec Python 15
Série quotidienne actuelle 11
Dernière séquence 20/06/2019 - 21/06/2019
Série actuelle 23/06/2019 - 03/07/2019

Remarque : Une partie du code ici est ancienne et a été écrite lorsque j'apprenais le C++. Il est possible que le code ne soit pas sûr ou qu'il fasse de fausses hypothèses. Veuillez utiliser avec prudence. Les demandes de tirage sont toujours les bienvenues.

Problèmes de liste liée

Problème Solution
Recherchez le nième nœud de la liste chaînée à partir du dernier. nthToLastNode.cpp, nth_to_last_node.py
Ajoutez des nombres où chaque chiffre du nombre est représenté par un nœud d'une liste chaînée. Donnez la sortie sous forme de liste chaînée. add_two_numbers_lists.cpp, add_two_numbers_list.py
Échangez les nœuds d'une liste chaînée sans échanger de données. swapNodesWithoutSwappingData.cpp, swap_nodes_without_swapping_data.py
Inverser une liste chaînée, de manière itérative et récursive reverseLinkedListIterAndRecurse.cpp, reverse_linkedlist.py
Étant donné une liste chaînée, inversez les nœuds alternatifs et ajoutez-les à la fin. reverseAlternateNodes.cpp
Seulement étant donné un pointeur de nœud, supprimez le nœud de la liste chaînée. supprimerNode.cpp
Supprimez toute la liste de liens. supprimerLinkedlist.cpp
Imprimez le nœud central de la liste liée sans itérer deux fois. printMiddleNode.cpp
Déterminez si une liste chaînée est un pallindrome. listePallindrome.cpp
Insérez des données dans une liste chaînée triée. insertInASortedLinkedList.cpp
Déterminez le point d’intersection (fusion) de deux listes chaînées données. findIntersectionPointOfLists.cpp, intersection_of_lists.py
Clonez une liste chaînée qui a next et un pointeur aléatoire, Space Complexity - O(1). cloneListWithRandomPtr.cpp, clone_list_with_random_ptr.py
Étant donné une liste chaînée triée avec des doublons, supprimez les doublons en une seule itération. supprimerDuplicatesFromSortedList.cpp
À l'aide de l'algorithme de recherche de cycle de Floyd, détectez si une liste chaînée contient un cycle, si elle contient un cycle, supprimez la boucle floyedCycleDetection.cpp
Trier une liste chaînée à l'aide du tri par fusion merge_sort.cpp
Étant donné une liste à chaînage unique L 0 -> L 1 -> … -> L n-1 -> L n . Réorganisez les nœuds dans la liste (en place) pour que la nouvelle liste formée soit : L 0 -> L n -> L 1 -> L n-1 -> L 2 -> L n-2 .... réorganiser_list.cpp

Inclure

Include contient une implémentation d'en-tête unique de structures de données et de certains algorithmes.

Structure/algorithme de données Mise en œuvre
Macros et algorithmes génériques comme le swap, la génération de nombres aléatoires générique.h
Implémentation de la pile générique pile.h
Implémentation de file d'attente générique file d'attente.h
Implémentation de liste générique liste.h
Implémentation de l'arbre de recherche binaire binaireSearchTree.h
Implémentation du tri rapide tri rapide.h
Implémentation du tri par fusion mergeSort.h
Implémentation du tri par sélection sélectionSort.h
Implémentation du tri à bulles bubbleSort.h
Implémentation de double liste liée au noyau Linux double_linked_list.h
Implémentation de graphiques génériques (liste de contiguïté) graphique.h
Implémentation du tri en tas tas_sort.h
Ma propre implémentation de bibliothèque de chaînes pstring.h pstring.cpp

Problèmes de manipulation de bits

Problème Solution
Déterminez si un nombre est une puissance de 2. power_of_2.cpp
Ajoutez deux nombres binaires représentés sous forme de chaîne. addBin.cpp
Déterminez la prochaine puissance de 2 pour un nombre donné. next_power_of_2.cpp
À l'aide de la manipulation de bits, déterminez si un nombre est un multiple de 3. multiple_of_3.cpp
Déterminez l'Endianess de la machine, imprimez un numéro en Endianess inversé. reverseEndianness.cpp
Trouvez la parité d'un nombre donné. find_parity.cpp
Implémentez la multiplication rapide d'un nombre à 7 en utilisant la manipulation de bits. multiplier_by_7.cpp
Inverser les bits d'un entier non signé (deux méthodes : Inverser bit par bit et diviser pour régner). reverseBitsOfAnInteger.cpp
Petite fonction pour déterminer la position du bit le plus à droite dans un entier donné. right_most_set_bit.cpp
Étant donné un vecteur de nombres, un seul nombre apparaît un nombre impair de fois, trouvez le nombre. find_odd_one_out.cpp
Étant donné deux entiers, déterminez si leur somme serait un débordement d'entier. entierOverflow.cpp
Combien d’opérations de retournement de bits nécessiteraient pour convertir le nombre A en B. countNumberOfBitFlips.cpp
Étant donné un nombre x et deux positions (à partir du côté droit) dans la représentation binaire de x, écrivez une fonction qui échange n bits droits à deux positions données et renvoie le résultat. Il est également entendu que les deux ensembles de bits ne se chevauchent pas. swapSetOfBits.cpp
Additionnez deux nombres sans utiliser d'opérateurs arithmétiques addition_sans_operators.cpp
Louise et Richard jouent à un jeu. Ils ont un pion placé sur N. Louise obtient le premier tour et les tours alternent par la suite. Dans le jeu, ils effectuent les opérations suivantes :
  • Si N n'est pas une puissance de 2, réduisez le compteur de la plus grande puissance de 2 inférieure à N.
  • Si N est une puissance de 2, réduisez le compteur de la moitié de N.
La valeur résultante est le nouveau N qui est à nouveau utilisé pour les opérations ultérieures. Le jeu se termine lorsque le compteur tombe à 1, c'est-à-dire N == 1, et la dernière personne à effectuer un mouvement valide gagne.
  • Étant donné N, votre tâche est de trouver le gagnant du jeu. S'ils mettent le compteur à 1, Richard gagne, car c'est le tour de Louise et elle ne peut pas bouger.
  • Format d'entrée : -La première ligne contient un entier T, le nombre de cas de test. Les lignes T suivent. Chaque ligne contient N, le nombre initial défini dans le compteur.
 counter_game.cpp
Déterminez si deux entiers sont de signes opposés. check_opposite_signs.cpp
Échangez deux bits aux positions p et q d'un entier donné. swapBits.cpp
Vérifiez si un nombre est une puissance de 4. check_if_power_of_4.cpp

Résoudre les problèmes d'entretien de codage

Problème Solution
Problème 1-1 : Édition 6 : Écrire un algorithme pour déterminer si une chaîne a des caractères uniques ou non. Pouvons-nous le faire sans utiliser de structures de données supplémentaires ? 1-1-hasUniqueChars.cpp, 1-1-hasUniqueChars.py
Problème 1-2 : Édition 5 : Inversez une chaîne lorsque vous transmettez une chaîne C terminée par un caractère nul. 1-2-edi5-reverseString.cpp
Problème 1-2 : Édition 6 : Étant donné deux chaînes, déterminez si l'une est une permutation de l'autre. 1-2-perm-strings.cpp, 1-2-perm-strings.py
Problème 1-3 : Édition 5 : Écrivez un algorithme pour supprimer les caractères en double d'une chaîne. 1-3-edi5-removeDuplicates.cpp
Problème 1-3 : Édition 6 : URLify : Remplacez tous les espaces d'une chaîne par '%20'. De préférence sur place 1-3-URLify.cpp
Problème 1-4 : Edition 6 : Étant donné une chaîne, écrivez une fonction pour vérifier s'il s'agit d'une permutation d'un pallindrome. 1-4-pallindrome-permutations.cpp
Problème 1-5 : Édition 6 : Il existe trois modifications possibles qui peuvent être effectuées sur une chaîne : Insérer un caractère, Supprimer un caractère, Remplacer un caractère. Étant donné deux chaînes, déterminez si elles sont à une ou à 0 édition. 1-5-one-edit-away.cpp
Problème 1-6 : implémenter une méthode pour effectuer une compression de chaîne de base. L'exemple de chaîne aabcccccaaa doit être compressé en a2b1c5a3 , cependant si la chaîne compressée est plus grande que la chaîne d'origine, renvoie la chaîne d'origine 1-6-string-compression.cpp
Problème 1-7 : faites pivoter la matrice dans le sens des aiguilles d'une montre (et dans le sens inverse des aiguilles d'une montre) de 90 degrés. 1-7-rotation-matrice.cpp
Problème 1-8 : Écrivez un algorithme tel que si un élément de la matrice MxN est 0, toute sa ligne et sa colonne sont définies sur 0. 1-8-zero-matrix.cpp
Problème 1-9 : Étant donné deux chaînes s1 et s2, déterminez que s2 est la rotation de s1 en utilisant un seul appel à une fonction qui vérifie si une chaîne est la rotation d'une autre. Rotation de 1 à 9 cordes.cpp
Problème 2-1 : supprimez les doublons d'une liste chaînée non triée . Que se passe-t-il si aucun tampon temporaire n'est autorisé. 2-1-supprimer-dups.cpp
Problème 2-2 : Déterminer le k ème nœud à partir du dernier d'une liste à chaînage unique. (Approches itératives et récursives) 2-2-kthToLast.cpp
Problème 2-3 : implémenter un algorithme pour supprimer un nœud au milieu d'une liste à chaînage unique 2-3-delete-middle-node.cpp
Problème 2-4 : Partitionner une liste chaînée autour d'une valeur x, tous les nœuds inférieurs à x précèdent tous les nœuds supérieurs à x 2-4-partition.cpp
Problème 2-5 : Vous avez deux nombres représentés par une liste chaînée où chaque nœud contient un seul chiffre. Les chiffres sont stockés dans l'ordre inversé, de sorte que les chiffres de 1 soient en tête de liste. Écrivez une fonction qui additionne les deux nombres et renvoie la somme sous forme de liste chaînée. Exemple :
  • Entrée : ( 7 --> 1 --> 6 ) + ( 5 --> 9 --> 2 ) soit 617 + 295
  • Sortie : ( 2 --> 1 --> 9 ) soit 912.
  • SUIVI : Supposons que les listes soient stockées dans l'ordre suivant, répétez le problème ci-dessus.
  • Entrée : ( 6 --> 1 --> 7 ) + ( 2 --> 9 --> 5 ) soit 617 + 295
  • Sortie : ( 9 --> 1 --> 2 ) soit 912.
  • Implémentez-le de manière récursive et itérative.
 2-5-ajouter-des-listes.cpp
Problème 2-6 : Déterminer si la liste chaînée est un palindrome (2 approches itératives et une récursive 2-6-palindrome.cpp
Problème 2-7 : Déterminez si deux listes chaînées se croisent, si oui, renvoyez le nœud qui se croise. L'intersection est définie en fonction d'une référence et non de valeurs 2-7-intersection.cpp
Problème 2-8 : Détecter si la liste chaînée a une boucle, trouver le nœud de départ de la boucle et supprimer la boucle 2-8-loop-detection.cpp

Problèmes de programmation dynamique

Problème Solution
N ème terme de Fibonacci utilisant différentes techniques de mémorisation fibonacci.cpp
Problème de sous-séquence commune le plus long lcs.cpp, longest_common_subsequence.py
Wiki du problème de sous-séquence contiguë à valeur maximale max_subsequence.cpp
Numéro catalan - Comptez le nombre d'arbres de recherche binaires possibles avec n clés numéro_catalan.cpp
Calculez le nombre de chemins uniques depuis l'origine de la source (0, 0) jusqu'à la destination (m-1, n-1) dans la grille amxn. Vous ne pouvez vous déplacer que vers le bas ou vers la droite. chemins_uniques.cpp
0-1 Problème de sac à dos : Imaginez que vous êtes un voleur et que vous voulez voler des choses avec une pièce pleine de choses. Vous disposez d'un sac à dos qui peut supporter une capacité maximale de poids W et vous souhaitez le remplir de manière à ce que sa valeur soit maximale. En tant que voleur intelligent, vous connaissez le poids et la valeur de chaque objet présent dans la pièce. Comment rempliriez-vous votre sac à dos, de telle sorte que vous obteniez la valeur maximale possible, de telle sorte que vous ne puissiez remplir que jusqu'à la capacité W. 0_1_knapsack_problem.cpp

Problèmes d'arbre

Problème Solution
Parcours itératif de l'ordre de niveau de l'arbre à l'aide de la file d'attente levelOrderTraversalIterative.cpp, level_order_tree_traversal_iterative.py
Voyage d'ordre de niveau récursif de l'arbre levelOrderTraversalRecursive.cpp, level_order_tree_traversal_recursive.py
Traversée en zigzag de l'arbre zigZagTraversal.cpp, zig_zag_traversal.py
Prédécesseur et successeur d'un nœud donné dans l'arbre de recherche binaire prédécesseurSuccesseur.cpp
Étant donné les valeurs de deux nœuds dans un arbre de recherche binaire, recherchez l'ancêtre commun le plus bas (LCA). Supposons que les deux valeurs existent dans l’arborescence. le plus bas-common-ancestor.cpp, le plus bas_common_ancestor.py
Étant donné un arbre binaire (contrairement à l'arbre de recherche binaire), recherchez l'ancêtre commun le plus bas (LCA). arbre-binaire-ancêtre-commun le plus bas.cpp
Étant donné un arbre binaire, imprimez tous ses chemins racine-feuille, un par ligne. printAllRootToLeafPath.cpp
Déterminez si un arbre est un arbre somme. Un SumTree est un arbre binaire où la valeur d'un nœud est égale à la somme des nœuds présents dans son sous-arbre gauche et son sous-arbre droit. Un arbre vide est SumTree et la somme d'un arbre vide peut être considérée comme égale à 0. Un nœud feuille est également considéré comme SumTree. sommeTree.cpp
Convertissez un arbre en sumTree, de telle sorte que chaque nœud soit la somme des sous-arbres gauche et droit de l'arbre d'origine. convert_to_sum_tree.cpp, convert_to_sum_tree.py
Convertissez un tableau trié en arbre de recherche binaire équilibré. triéArrayToBST.cpp
Étant donné un arbre binaire, générez la somme de chaque colonne verticale. somme verticale.cpp
Étant donné un arbre binaire et une clé, le nœud avec la clé existe dans l'arbre. Trouvez tous les ancêtres du nœud avec la clé, ancêtre voici les nœuds qui sont en chemin direct du nœud à la racine. node_ancestors_in_root_path.cpp
Étant donné un arbre binaire et une clé, renvoie le niveau du nœud avec la clé. La racine est au niveau 1, et si le nœud avec la clé n'existe pas dans l'arborescence, renvoie 0 niveau_de_node.cpp
Étant donné un arbre binaire, trouvez tous les chemins de la racine aux nœuds, dont la somme est k. k_sum_paths.cpp
Étant donné un arbre binaire, imprimez ses nœuds niveau par niveau dans l'ordre inverse. c'est-à-dire que tous les nœuds présents au dernier niveau doivent être imprimés en premier, suivis des nœuds de l'avant-dernier niveau et ainsi de suite. Tous les nœuds de n'importe quel niveau doivent être imprimés de gauche à droite. reverseLevelOrderTraversal.cpp
Inversez un arbre binaire, de manière récursive et itérative. inverser_a_tree.cpp
Étant donné un arbre de recherche binaire, recherchez-y le plafond et le plancher d'une clé donnée. Si la clé donnée se trouve dans le BST, alors le plancher et le plafond sont égaux à cette clé, sinon le plafond est égal à la clé supérieure suivante (le cas échéant) dans le BST et le plancher est égal à la clé supérieure précédente (le cas échéant) dans le BST. étage_ceil_bst.cpp
Trouver le kième plus petit élément dans un arbre de recherche binaire kth_smallest.cpp
Validez si un arbre binaire donné est un arbre de recherche binaire. valider_bst.cpp
Étant donné un arbre de recherche binaire et un nombre cible, renvoie true s'il existe deux éléments dans le BST tels que leur somme est égale à la cible donnée. find_target_k.cpp
Étant donné un arbre de recherche binaire non vide et une valeur cible, recherchez la valeur dans le BST la plus proche de la cible. A noter également que la valeur cible est une virgule flottante. Il n’y aura qu’une seule valeur unique la plus proche de la cible. close_bst_value.cpp, close_bst_value.py
Étant donné un arbre binaire, traversant la précommande, construisez une sortie de chaîne contenant les valeurs de nœud et des parenthèses. Le nœud nul doit être représenté par une paire de parenthèses vides "()". Et vous devez omettre toutes les paires de parenthèses vides qui n'affectent pas la relation de mappage un-à-un entre la chaîne et l'arbre binaire d'origine. Exemples dans le fichier de code string_from_tree.cpp

Problèmes de chaîne

Problème Solution
Implémentation de l'algorithme Robin-Karp pour la recherche de chaînes robinKarpStringMatching.cpp
Trouver la prochaine permutation d'une chaîne donnée, c'est-à-dire. réorganiser la chaîne donnée de manière à ce qu'elle soit la prochaine chaîne lexicographiquement plus grande que la chaîne donnée next_permutation.cpp
Implémentation de l'algorithme Z pour la correspondance de modèles z.cpp
Cas de test pour une bibliothèque de chaînes auto-créée pstring_test.cpp
Obtenez la longueur du dernier mot d'une chaîne. longueur_du_dernier_mot.cpp
Trouvez la différence entre deux chaînes. La chaîne t est générée en mélangeant aléatoirement les chaînes, puis en ajoutant une lettre supplémentaire à une position aléatoire. Déterminer le caractère qui est différent en t find_difference.cpp

Problèmes courants de structure de données et de logique

Problème Solution
Imprimer le contenu de la matrice dans un ordre en spirale matrice_spirale_print.cpp
Étant donné une matrice M x N, faites-la pivoter de R rotations dans le sens inverse des aiguilles d'une montre et affichez la matrice résultante. rotation_matrix.cpp
Faire pivoter un tableau de r éléments (gauche ou droite) tableau_rotation.cpp
Étant donné un tableau d'entiers répétitifs/non répétitifs, déterminez le premier entier non répétitif de ce tableau first_non_repeating_int.cpp
Dans Quantumland, il y a n villes numérotées de 1 à n. Ici, c i désigne la ième ville. Il y a n−1 routes dans Quantumland. Ici, c i et c i+1 ont une route bidirectionnelle entre eux pour chaque i < n. Il y a une rumeur selon laquelle Flatland va attaquer Quantumland, et la reine veut garder sa terre en sécurité. La route entre c i et c i+1 est sûre s'il y a un garde en c i ou c i+1 . La reine a déjà placé quelques gardes dans certaines villes, mais elle n'est pas sûre qu'ils soient suffisants pour assurer la sécurité des routes. Elle souhaite connaître le nombre minimum de nouveaux gardiens qu'elle doit embaucher. Voir les commentaires dans la solution pour les détails d'entrée/sortie. save_quantamland.cpp
On vous donne un entier N. Trouvez les chiffres de ce nombre qui divisent exactement N (division qui laisse 0 comme reste) et affichez leur décompte. Pour N=24, il y a 2 chiffres (2 & 4). Ces deux chiffres divisent exactement 24. Notre réponse est donc 2. Voir plus de détails dans le commentaire d'en-tête du fichier de solution. findDigits.cpp
Chiffrez puis décrypte un texte à l'aide de Caeser Cipher. caeser_cipher.cpp
Chiffrer puis décrypter un texte grâce au chiffre de Vigenère. vigenere_cipher.cpp
Générez efficacement des nombres binaires entre 1 et N. n_binary.cpp
Implémenter la fonction de puissance power_function.cpp

Problèmes mathématiques

Problème Solution
Imprime toutes les permutations d'une chaîne. Exemple : Les permutations de ABC sont ABC, ACB, BCA, BAC, CAB, CBA string_permutations.cpp
Algorithme euclidien pour trouver le plus grand diviseur commun de deux nombres. (Itératif et récursif) pgcd.cpp
Implémentez pow(x,y) en utilisant l’approche diviser pour régner. Essayez de l'implémenter dans O(logn) pow.cpp
Calculer la factorielle d'un grand nombre, disons 100 (elle aura 158 chiffres) factoriel_of_large_num.cpp
Générez tous les mots possibles à partir d'un numéro saisi sur un clavier mobile traditionnel phone_digits.cpp
Étant donné une représentation sous forme de chaîne d'un nombre, supprimez n caractères de la chaîne de telle sorte que la représentation numérique soit la plus basse possible. nombre_possible_le plus bas.cpp
Détectez si un numéro est un nombre heureux. Un nombre est un nombre heureux si une séquence d'opérations où le nombre est remplacé par la somme du carré de ses chiffres conduit finalement à 1. Un nombre n'est pas un nombre heureux si nous sommes dans une boucle infinie lorsque les opérations ci-dessus sont effectuées. happy_number.cpp

Problèmes de pile

Problème Solution
Nous avons une série de n cotations quotidiennes pour une action. Nous devons calculer la durée du cours de l'action pour les n jours. Le span du ième jour est défini comme le nombre maximum de jours consécutifs pendant lesquels le prix de l'action était inférieur ou égal au ième jour. Pour les cotations boursières, {100, 60, 70, 65, 80, 85}, la durée sera de {1, 1, 2, 1, 4, 5}. Le Span pour le jour 1 est toujours de 1, maintenant pour le jour 2, le stock est à 60, et il n'y a aucun jour avant où le stock était inférieur à 60. Le Span reste donc 1. Pour le jour 3, le stock est évalué à 70, donc son Span reste à 1. est 2, comme la veille, il était 60, et ainsi de suite. stock_span_problem.cpp
Étant donné une expression infixe, convertissez-la en expression postfixe, exemple (A+B)*C --> AB+C* infix_to_postfix.cpp
Étant donné une chaîne contenant uniquement les caractères '(', ')', '{', '}', '[' et ']', déterminez si la chaîne d'entrée est valide. Les crochets doivent se fermer dans le bon ordre, "( )" et "()[]{}" sont tous valides mais "(]" et "([)]" ne le sont pas. valid_parenthesis.cpp

Problèmes de tri et de recherche

Problème Solution
Étant donné un vecteur trié, renvoie le premier index de l'occurrence d'une valeur dans le vecteur, si le nombre n'existe pas, renvoie -1 first_occurrence_binary_search.cpp
Recherchez le premier élément répétitif dans un tableau d'entiers. Étant donné un tableau d’entiers, recherchez le premier élément répétitif. Nous devons trouver l’élément qui apparaît plus d’une fois et dont l’indice de première occurrence est le plus petit. firstRepeatingElement.cpp
Étant donné une liste d'entiers non triés, A={a 1 ,a 2 ,…,a N }, trouver la paire d'éléments qui ont la plus petite différence absolue entre eux ? S’il y a plusieurs paires, trouvez-les toutes. numéros_plus proches.cpp
Étant donné un tableau trié, déterminez l'index du point fixe dans ce tableau. Si le tableau n'a pas de virgule fixe, renvoie -1. Un tableau a un point fixe lorsque l'index de l'élément est le même que l'index, c'est-à-dire i == arr[i], complexité temporelle attendue O(logn) pointfixe.cpp
Trouvez l'élément maximum dans un tableau qui augmente d'abord puis diminue. Entrée : arr[] = {8, 10, 20, 80, 100, 200, 400, 500, 3, 2, 1}, sortie : 500. Le tableau peut également être strictement croissant ou décroissant. La complexité ExpectedTime est O (logn). findMaximum.cpp
Étant donné un tableau d’entiers positifs et/ou négatifs, trouvez une paire dans le tableau dont la somme est la plus proche de 0. findClosestPairToZero.cpp
Numeros, l'Artiste, avait deux listes A et B, de telle sorte que B était une permutation de A. Numeros était très fier de ces listes. Malheureusement, en les transportant d'une exposition à l'autre, certains numéros ont été oubliés dans A. Saurez-vous retrouver les numéros manquants ? Remarques :
  • Si un numéro apparaît plusieurs fois dans les listes, vous devez vous assurer que la fréquence de ce numéro dans les deux listes est la même. Si ce n’est pas le cas, il s’agit également d’un numéro manquant.
  • Vous devez imprimer tous les nombres manquants par ordre croissant.
  • Imprimez chaque numéro manquant une fois, même s'il manque plusieurs fois.
  • La différence entre le nombre maximum et minimum dans B est inférieure ou égale à 100.
.
  • Il y aura quatre lignes de saisie : n - la taille de la première liste, suivie de n entiers séparés par des espaces qui composent la première liste. m - la taille de la deuxième liste. Ceci est suivi de m entiers séparés par des espaces qui constituent la deuxième liste. Affichez les nombres manquants par ordre croissant.
 numéros manquants.cpp
Trouvez la paire la plus proche parmi deux tableaux triés. Étant donné deux tableaux triés et un nombre x, trouvez la paire dont la somme est la plus proche de x et la paire contient un élément de chaque tableau. On nous donne deux tableaux ar1[0…m-1] et ar2[0..n-1] et un nombre x, nous devons trouver la paire ar1[i] + ar2[j] telle que la valeur absolue de (ar1 [i] + ar2[j] – x) est minimum. closePairSorted.cpp
Étant donné un tableau A de n éléments, trouvez trois indices i, j et k tels que A[i]^2 + A[j]^2 = A[K]^2. Complexité temporelle O(n2) et complexité spatiale O(1) squareSum.cpp
Étant donné un tableau non trié arr[0..n-1] de taille n, recherchez la longueur minimale du sous-tableau arr[s..e] de telle sorte que le tri de ce sous-tableau trie l'ensemble du tableau. minLengthUnsortedArray.cpp
Trouvez le nombre manquant dans la progression arithmétique NuméroManquant2.cpp
Trouver les éléments communs dans 3 vecteurs triés commonIn3Arrays.cpp
Trouver toutes les paires avec une somme donnée dans un tableau/vecteur non trié find_pairs_with_sum.cpp
Étant donné un tableau, recherchez-y l'élément de pointe. Un élément de pointe est un élément supérieur à ses voisins. Peak_element.cpp
Étant donné un tableau trié d’entiers non négatifs distincts, recherchez-y le plus petit élément manquant. smallest_missing.cpp
Déplacer tous les zéros du vecteur jusqu'à la fin move_zeros.cpp

Problèmes de graphique

Problème Solution
Profondeur du premier parcours d'un graphique dfsDemo.cpp
Largeur du premier parcours d'un graphique bfsDemo.cpp
calculez la distance la plus courte entre la position de départ (nœud S) et tous les autres nœuds du graphique à l'aide de l'algorithme de Dijkstra. dijkstra-shortest-reach.cpp
Calculer le poids total du Minimum Spanning Tree d'un graphique donné (somme des poids des arêtes qui forme MST) à l'aide de l'algorithme de Prim primsMST.cpp
Imprimez l'arbre couvrant minimum (MST) d'un graphique donné à l'aide de l'algorithme de Kruskal. kruskalMST.cpp
Créez un programme pour générer un codage de Huffman pour chaque caractère sous forme de tableau. huffman_encoding.cpp
Recherchez un mot donné dans un tableau 2D contenant des lettres. Le mot peut être construit en traversant séquentiellement des cellules horizontales ou verticales adjacentes. Dans une séquence pour former un mot, une lettre située à la même position ne peut pas être utilisée plus d'une fois. (Vérifiez le haut du fichier pour des exemples.) grille_mot_search.cpp
Étant donné un écran 2D, l'emplacement du pixel et la nouvelle valeur de la couleur à remplir, remplacez la couleur du pixel et tous les pixels adjacents (haut, bas, gauche, droite) de même couleur par une nouvelle couleur. Cela revient à remplir par inondation (rappelez-vous le symbole du seau) une région dans MS-PAINT. Flood_fill.cpp

Problèmes gourmands

Problème Solution
Étant donné deux tableaux d'entiers, A et B, chacun contenant N entiers. Vous êtes libre de permuter l'ordre des éléments dans les tableaux. Existe-t-il une permutation A', B' possible de A et B, telle que A' i + B' i ≥ K pour tout i, où A' i désigne le i ème élément du tableau A' et B' i désigne i ème élément du tableau B'. deux_arrays.cpp
John prend les commandes. La ième commande est passée par le ième client à ce moment-là et son traitement prend plus de temps. Quel est l’ordre dans lequel les clients recevront leurs commandes ? (voir plus de détails dans les commentaires des solutions) commandes_order.cpp

Problèmes de retour en arrière

Problème Solution
Vous recevez une chaîne de chiffres (par exemple "1234", "567", etc.), fournissez toutes les combinaisons de lettres possibles que nous pourrions générer à partir de cette chaîne de chiffres, en fonction du mappage que nous voyons sur le clavier du téléphone/mobile. Si vous avez tapé des SMS sur des téléphones à l’ancienne, vous le saurez. Par exemple, "1" est mappé sur "abc", 2 est mappé sur "def". Vous pouvez vous référer à l'image..
  • Exemple : "34" donnera le résultat : {"dg","dh","di","eg","eh","ei","fg","fh","fi"}
Notez que l'ordre n'a pas d'importance dans le jeu de résultats.		 dialpad_combinations.cpp
Implémentez le maching de modèles génériques avec la prise en charge de « ? » &' '.
  • '?' Correspond à n’importe quel caractère.
    • ' ' Correspond à n'importe quelle séquence de caractères.
    . Consultez les exemples dans le fichier pour plus de détails.    		 wild_card_matching.cpp
    À partir d'un tableau 2D et d'une liste de mots d'un dictionnaire, trouvez tous les mots possibles à partir de la liste. (Vérifiez l'exemple dans la solution) word_search.cpp

    Problèmes de code Leet

    Problème Solution
    Étant donné un tableau d'entiers triés sans doublons, renvoie le résumé de ses plages. Par exemple, étant donné [0,1,2,4,5,7], retournez ["0->2","4->5","7"]. résumé_ranges.cpp
    Étant donné une matrice 2D, avec les propriétés suivantes
    • Les entiers de chaque ligne sont triés par ordre croissant de gauche à droite.
    • Les entiers de chaque colonne sont triés par ordre croissant de haut en bas.
    		 search2DII.cpp
    Étant donné un tableau d'entiers non triés, recherchez le premier entier positif manquant. Exemple : [1,2,0] devrait renvoyer 3 et [3,4,-1,1] devrait renvoyer 2. La complexité temporelle attendue O(n) et la solution devraient utiliser un espace constant firstMissingPositiveNum.cpp
    Étant donné un tableau d’entiers non triés, trouvez la longueur de la séquence d’éléments consécutifs la plus longue. Par exemple : Étant donné [100, 4, 200, 1, 3, 2]. La séquence d'éléments consécutifs la plus longue est [1, 2, 3, 4]. Renvoie sa longueur : 4. L'algorithme doit s'exécuter en complexité O(n). le plus longConsecutiveSeq.cpp
    Étant donné deux tableaux d'entiers triés nums1 et nums2, fusionnez nums2 dans nums1 en un seul tableau trié. Vous pouvez supposer que nums1 dispose de suffisamment d'espace (taille supérieure ou égale à m + n) pour contenir des éléments supplémentaires de nums2. Le nombre d'éléments initialisés dans nums1 et nums2 sont respectivement m et n. mergeArrays.cpp
    Étant donné un tableau d’entiers non négatifs, vous êtes initialement positionné au premier index du tableau. Chaque élément du tableau représente votre longueur de saut maximale à cette position. Déterminez si vous pouvez atteindre le dernier index. Par exemple:
    • A = [2,3,1,1,4], renvoie vrai.
    • A = [3,2,1,0,4], renvoie faux.
    		 jumpGame.cpp
    Étant donné un entier positif, renvoie le titre de la colonne correspondant tel qu'il apparaît dans une feuille Excel. Par exemple 1 -> A, 2 -> B,...26 -> Z, 27 -> AA, 28 -> AB, ...705 -> AAC excelColSheetTitle.cpp
    Étant donné un tableau nums, écrivez une fonction pour déplacer tous les 0 à la fin tout en conservant l'ordre relatif des éléments non nuls. Par exemple, étant donné nums = [0, 1, 0, 3, 12], après avoir appelé votre fonction, nums devrait être [1, 3, 12, 0, 0]. moveZeroes.cpp
    Étant donné un tableau d’entiers, recherchez si le tableau contient des doublons. La fonction doit renvoyer vrai si une valeur apparaît au moins deux fois dans le tableau, et elle doit renvoyer faux si chaque élément est distinct. contientDuplicate.cpp
    Étant donné une liste, faites pivoter la liste vers la droite de k places, où k est non négatif. Par exemple:
    • Étant donné 1->2->3->4->5->NULL et k = 2, renvoie 4->5->1->2->3->NULL
    		 rotationListe.cpp
    Étant donné deux mots mot1 et mot2, trouvez le nombre minimum d'étapes requises pour convertir mot1 en mot2. (chaque opération compte pour 1 étape.). Vous avez les 3 opérations suivantes autorisées sur un mot :
    • Insérer un caractère
    • Supprimer un personnage.
    • Remplacer un personnage
    .    		 editDistance.cpp
    Étant donné un arbre binaire, remplissez chaque pointeur suivant pour pointer vers son prochain nœud droit. S'il n'y a pas de nœud suivant à droite, le pointeur suivant doit être défini sur NULL. Initialement, tous les pointeurs suivants sont définis sur NULL. Vous ne pouvez utiliser qu'un espace supplémentaire constant. Vous pouvez supposer qu'il s'agit d'un arbre binaire parfait (c'est-à-dire que toutes les feuilles sont au même niveau et que chaque parent a deux enfants). connectNextPointers.cpp
    Étant donné n paires de parenthèses, écrivez une fonction pour générer toutes les combinaisons de parenthèses bien formées. Par exemple, étant donné n = 3, un ensemble de solutions est "((()))", "(()())", "(())()", "()(())", "( )()()" generate_parenthesis.cpp
    Étant donné un tableau contenant n nombres distincts pris parmi 0, 1, 2, ..., n, recherchez celui qui manque dans le tableau. Par exemple, Étant donné nums = [0, 1, 3] renvoie 2. numéro_manquant.cpp
    Supposons qu'un tableau trié pivote à un pivot inconnu de vous au préalable. (c'est-à-dire que 0 1 2 4 5 6 7 pourrait devenir 4 5 6 7 0 1 2). Trouvez l'élément minimum. Vous pouvez supposer qu’aucun doublon n’existe dans le tableau. find_min_rotated.cpp
    Étant donné un tableau S de n entiers, trouver trois entiers dans S tels que la somme soit la plus proche d'un nombre donné, cible. Renvoie la somme des trois entiers. Vous pouvez supposer que chaque entrée aurait exactement une solution. threeSumClosest.cpp
    Étant donné n entiers non négatifs a 1 , a 2 , ..., an , où chacun représente un point à la coordonnée (i, a i ). n lignes verticales sont tracées de telle sorte que les deux extrémités de la ligne i soient à (i, a i ) et (i, 0). Trouvez deux lignes qui, avec l'axe des x, forment un récipient, de telle sorte que le récipient contienne le plus d'eau. Remarque : Vous ne pouvez pas incliner le conteneur. maxArea.cpp
    Étant donné un arbre binaire contenant uniquement des chiffres de 0 à 9, chaque chemin racine-feuille pourrait représenter un nombre. Un exemple est le chemin racine-feuille 1->2->3 qui représente le nombre 123. Trouvez la somme totale de tous les nombres racine-feuille. Exemple dans les commentaires de la solution sumRootToLeafNumbers.cpp
    Supposons que vous ayez un tableau dont le ième élément est le prix d’une action donnée au jour i. Si vous n'étiez autorisé à effectuer qu'une seule transaction (c'est-à-dire acheter une et vendre une action), concevez un algorithme pour trouver le profit maximum. maxProfitStock.cpp
    Étant donné la grille amxn remplie de nombres non négatifs, trouvez un chemin du haut à gauche vers le bas à droite qui minimise la somme de tous les nombres le long de son chemin. Remarque : Vous ne pouvez vous déplacer que vers le bas ou vers la droite à tout moment. minPath.cpp
    Comptez le nombre de nombres premiers inférieurs à un nombre non négatif, n. countPrimes.cpp
    Trouvez toutes les combinaisons possibles de k nombres dont la somme donne un nombre n, étant donné que seuls les nombres de 1 à 9 peuvent être utilisés et que chaque combinaison doit être un ensemble unique de nombres. Assurez-vous que les nombres de l’ensemble sont triés par ordre croissant. Exemple : pour k = 3, n = 9 le résultat serait [[1,2,6], [1,3,5], [2,3,4]], de même pour k = 3, n = 7, résultat serait [[1,2,4]]. combinaisonSum3.cpp
    Étant donné un nombre entier non négatif, ajoutez à plusieurs reprises tous ses chiffres jusqu'à ce que le résultat n'ait qu'un seul chiffre. Par exemple : étant donné num = 38, le processus est le suivant : 3 + 8 = 11, 1 + 1 = 2. Puisque 2 n'a qu'un seul chiffre, renvoyez-le. Suivi : Pourriez-vous le faire sans aucune boucle/récursion dans le runtime O(1) ? addDigits.cpp
    Étant donné une matrice avec des valeurs de cellule 0 ou 1. Trouvez la longueur du chemin le plus court de (a1, b1) à (a2, b2), de telle sorte que le chemin ne puisse être construit qu'à travers des cellules qui ont la valeur 1 et que vous ne puissiez voyager que dans 4 directions possibles, c'est-à-dire gauche, droite, haut et bas. chemin_le_maze_le plus court.cpp
    La distance de Hamming entre deux entiers est le nombre de positions auxquelles les bits correspondants sont différents. Étant donné deux entiers x et y, calculez la distance de Hamming. hamming_distance.cpp
    Étant donné deux arbres binaires, imaginez que lorsque vous placez l'un d'eux pour couvrir l'autre, certains nœuds des deux arbres se chevauchent tandis que les autres ne le sont pas. Vous devez les fusionner dans une nouvelle arborescence binaire. La règle de fusion est que si deux nœuds se chevauchent, additionnez les valeurs des nœuds comme la nouvelle valeur du nœud fusionné. Sinon, le nœud NOT null sera utilisé comme nœud du nouvel arbre. merge_trees.cpp
    Écrivez une fonction qui prend une chaîne en entrée et inverse uniquement les voyelles d'une chaîne. reverse_voyels.cpp
    Étant donné une chaîne, triez-la par ordre décroissant en fonction de la fréquence des caractères. Par exemple :
    • Entrée : cccbbbbaa Sortie : bbbcccaa
    		 sortCharByFrequency.cpp
    Produit du tableau sauf soi. Étant donné un tableau de n entiers où n > 1, nums, renvoie une sortie de tableau telle que sortie[i] est égale au produit de tous les éléments de nums sauf nums[i]. produit_sauf_self.cpp
    Étant donné un tableau trié, supprimez les doublons sur place et renvoyez la nouvelle longueur. Peu importe ce qu'il y a dans le tableau au-delà de la taille unique des éléments. Complexité spatiale O(1) et temporelle O(n) attendue. supprimer_duplicates.cpp
    Comptez le nombre d'îles dans une grille. Étant donné une grille représentant 1 comme corps terrestre et 0 comme plan d'eau, déterminez le nombre d'îles (plus de détails dans les commentaires du problème) count_islands.cpp
    Trouvez la médiane à partir d’un flux de données. Concevez une structure de données qui prend en charge addNum pour ajouter un nombre au flux et findMedian pour renvoyer la médiane des nombres actuels vus jusqu'à présent. De plus, si le nombre de nombres est pair, renvoie la moyenne de deux éléments du milieu, sinon la médiane. médian_stream.cpp
    Supprimez le nombre minimum de parenthèses invalides afin de rendre la chaîne d'entrée valide. Renvoie tous les résultats possibles. Remarque: la chaîne d'entrée peut contenir des lettres autres que les parenthèses (et) retire_invalid_parenthesis.cpp
    Étant donné un tableau et une valeur, supprimez toutes les instances de cette valeur en place et renvoyez la nouvelle longueur. N'allouez pas d'espace supplémentaire pour un autre tableau, vous devez le faire en modifiant le tableau d'entrée en place avec O (1) de la mémoire supplémentaire. L'ordre des éléments peut être modifié. Peu importe ce que vous laissez au-delà de la nouvelle longueur. retire_element.cpp
    Trouvez l'intersection de deux tableaux / vecteurs, étant donné que deux vecteurs trouvent le résultat de leur interaction. Le résultat ne doit contenir que des caractères uniques et peut être dans n'importe quel ordre intersection_of_array.cpp
    Étant donné un motif et une chaîne STR, trouvez si Str suit le même motif. Voici un match complet, de sorte qu'il existe une bijection entre une lettre de modèle et un mot non vide dans Str. exemple:
    Pattern = "Abba", str = "chien chat chat chien" devrait revenir vrai.
    Pattern = "Abba", str = "chat chat Cat Fish" devrait retourner faux.
    Pattern = "aaaa", str = "chien chat chat chien" devrait retourner faux.
    Pattern = "Abba", str = "chien chien chien chien" devrait retourner faux. word_pattern.cpp
    Vous bénéficiez d'un vecteur de nombres, où chaque numéro représente
    Prix ​​d'un stock le jour. Si vous êtes autorisé à terminer uniquement
    Une transaction par jour (c'est-à-dire acheter un et vendre un stock), conception
    Un algorithme pour trouver le profit maximum. best_time_to_buy_sell.cpp
    Compte tenu d'une phrase, inversez l'ordre des caractères de chaque mot d'une phrase tout en préservant l'espace blanc et l'ordre des mots initiaux.
    Exemple:
    Entrée: elle aime le chocolat
    Sortie: EHS Sevol Etalocohc reverse_words.cpp
    Développer
    Informations supplémentaires
    Applications connexes
    Recommandé pour vous
    Actualités connexes Tout