L'Atelier Monstre

Inverser les mots dans une chaîne L’idée est d’abord de nettoyer les espaces superflus, puis d’inverser toute la chaîne et enfin d’inverser chaque mot individuellement. public class InversionMots { public String inverserMots(String phrase) { char[] tab = phrase.toCharArray(); int lent = 0; // Nettoyage des espace ...

Maximisation de la somme des hauteurs de tours distinctes Le problème consiste à attribuer une hauteur à chaque tour de manière à ce que toutes les hauteurs soient strictement distinctes, tout en respectant une limite maximale pour chaque tour, et en maximisant la somme totale des hauteurs. Approche algorithmique L'approche gloutonne optimale r ...

Ce problème demande de déterminer le nombre minimal d’échanges de caractères nécessaires pour transformer une chaîne s1 en une autre chaîne s2, sous la contrainte que les deux chaînes sont des anagrammes. Chaque échange consiste à permuterexactement deux caractères d’une position. Méthode de Résolution par Recherche en Largeur (BFS) La approche ...

Le problème Word Ladder consiste à transformer un mot de départ en un mot d'arrivée en changeant une seule lettre à la fois, chaque étape intermédiaire devant figurer dans un dictionnaire donné. Il s'agit d'un problème classique de théorie des graphes qui peut être modélisé comme la recherche du plus court chemin dans un graphe non pondéré. Wor ...

Approche par marquage avec ensembles de bits Une solution élégante consiste à utiliser trois tableaux de masques de bits pour suivre les présences respectivement dans les lignes, les colonnes et les sous-grilles. Cette technique évite les réinitialisations répétées et offre une complexité temporelle en O(1) avec un espace constant. class Soluti ...

Étant donné une grille de taille m × n, chaque cellule contenant soit une case vide (0) soit un obstacle (1), il s'agit de calculer le nombre de chemins distincts permettant de rejoindre le coin inférieur droit depuis le coin supérieur gauche, en se déplaçant uniquement vers la droite ou vers le bas. Approche par programmation dynamique On note ...

La station-service Vous disposez de n stations-service sur un circuit circulaire. À la station i, le réservoir peut recevoir gas[i] litres de carburant, et le coût pour se rendre de la station i à la station i+1 est de cost[i] litres. Vous commencez avec un réservoir vide au départ d'une des stations. L'objectif est de trouver l'index de la ...

Analyse du Problème de Parenthèses Valides Ce défi algorithmique consiste à analyser une chaîne de caractères composée exclusivement de parenthèses ouvrantes ( et fermantes ). L'objectif est d'identifier la longueur maximale d'une sous-chaîne continue qui respecte la syntaxe correcte des parenthèses. Visualisation de la Logique Pour comprendre ...

Vous incarnez un cambrioleur expérimenté qui planifie une série de vols dans des maisons situées le long d'une rue. Chaque maison recèle une certaine quantité d'argent. La seule restriction est que les systèmes de sécurité des maisons adjacentes sont interconnectés, déclenchant une alerte de police si deux maisons contiguës sont cambriolées la ...

Élagage d'un arbre binaire de recherche L'objectif est de modifier un arbre binaire de recherche (ABR) pour que toutes les valeurs de ses nœuds se situent dans un intervalle donné [minVal, maxVal]. La structure relative des nœuds conservés doit rester intacte. Grâce aux propriétés fondamentales des ABR, nous pouvons optimiser cette opération en ...