L'Atelier Monstre

Fusion de deux tableaux triés (LeetCode 88) L'objectif est de fusionner deux tableaux d'entiers triés, nums1 et nums2, en un seul tableau trié au sein de nums1. Pour optimiser l'espace, nous utilisons une approche à trois pointeurs partant de la fin des tableaux, ce qui évite d'utiliser une structure de données intermédiaire. class Solution { ...

Cet article explore les méthodes de tri par fusion pour orgnaiser une liste chaînée en ordre croissant. L'objectif est d'atteindre une complxeité temporelle de O(n log n) avec une complexité spatiale auxiliaire constante (O(1)), ce qui implique de réorganiser les pointeurs des nœuds existants plutôt que de créer de nouveaux nœuds lors de la fus ...

Cet article présente une récapitulation technique des solutions pour les problèmes de l'AtCoder Beginner Contest 420, avec des explications et des exemples de code réécrits en C++. Problème A Un problème simple qui peut être résolu directement. La solution calcule la valeur modulo 12 après ajustement. #include <iostream> using namespace s ...

La bibliothèque standard du C++ ne fournit pas de fonction native équivalente au split de Java ou Python pour fractionner une chaîne de caractères (std::string). Cette opération est pourtant incontournable, en particulier lors du traitement des flux d'entrée ou de l'analyse syntaxique. Voici trois approches techniques pour pallier cette absence ...

Représentations Mémoire des Graphes Liste d'Adjacence Cette structure est optimale pour les graphes creux. Elle utilise un vecteur de listes pour stocker les voisins de chaque sommet. #include <iostream> #include <vector> #include <list> #include <algorithm> class GrapheAdjacence { private: int nbSommets; std:: ...

Somme Maximale d'un Sous-tableau La résolution de ce problème repose sur une approche gloutonne (greedy). L'idée centrale est que si la somme cumulée d'un sous-tableau devient négative, elle ne peut que diminuer la somme des éléments suivants. Par conséquent, dès que la somme courante tombe en dessous de zéro, nous réinitialisons le compteur po ...

Maison Voleur Ce problème est analogue à une version non continue de la somme maximale d'une sous-séquence. En séparant le dernier élément, les parties précédentes forment un sous-problème. La solution utilise la programmation dynamique pour calculer le maximum sans voler deux maisons adjacentes. class Solution { public: int rob(vector&l ...