1. Conversion des Nombres Romains en Entiers

Les chiffres romains sont représentés par sept symboles distincts : I, V, X, L, C, D et M. Chaque symbole possède une valeur numérique associée :

• I : 1
• V : 5
• X : 10
• L : 50
• C : 100
• D : 500
• M : 1000

Généralement, les chiffres sont lus de gauche à droite et leurs valeurs s'additionnent. Par exemple, II représente 2 (1 + 1), et XII représente 12 (10 + 1 + 1). Cependant, il existe des exceptions où un petit chiffre est placé avant un grand chiffre, indiquant une soustraction. Ces cas spécifiques sont les suivants :

• I placé avant V (IV) donne 4, ou avant X (IX) donne 9.
• X placé avant L (XL) donne 40, ou avant C (XC) donne 90.
• C placé avant D (CD) donne 400, ou avant M (CM) donne 900.

L'objectif est de convertir une chaîne de caractères représentant un nombre romain en son équivalent entier. Une approche consiste à parcourir la chaîne de gauche à droite, en gérant les cas de soustraction lorsqu'un symbole de plus petite valeur précède un symbole de plus grande valeur.

class ConvertisseurRomain:
    def convertir(self, chaine_romaine: str) -> int:
        symboles_valeurs = {
            'I': 1, 'V': 5, 'X': 10, 'L': 50,
            'C': 100, 'D': 500, 'M': 1000
        }
        total_decimal = 0
        longueur_chaine = len(chaine_romaine)

        # Parcourir la chaîne jusqu'à l'avant-dernier caractère
        for i in range(longueur_chaine - 1):
            valeur_actuelle = symboles_valeurs[chaine_romaine[i]]
            valeur_suivante = symboles_valeurs[chaine_romaine[i+1]]

            if valeur_actuelle < valeur_suivante:
                total_decimal -= valeur_actuelle
            else:
                total_decimal += valeur_actuelle

        # Ajouter la valeur du dernier caractère, qui n'a pas été traité dans la boucle
        total_decimal += symboles_valeurs[chaine_romaine[longueur_chaine-1]]
        return total_decimal

# Exemple d'utilisation
# c = ConvertisseurRomain()
# print(c.convertir("LVIII"))  # Output: 58
# print(c.convertir("MCMXCIV")) # Output: 1994

2. Détection de Cycle dans une Liste Chaînée

Pour déterminer si une liste chaînée contient un cycle (c'est-à-dire si un nœud peut être atteint une seconde fois en suivant les pointeurs suivant), on utilise une technique basée sur deux pointeurs, souvent appelée l'algorithme du "Lièvre et de la Tortue" (Floyd's Cycle-Finding Algorithm).

L'idée est d'utiliser deux pointeurs qui traversent la liste à des vitesses différentes :

• Un pointeur lent (la "tortue") avance d'un nœud à la fois.
• Un pointeur rapide (le "lièvre") avance de deux nœuds à la fois.

Si la liste ne contient pas de cycle, le pointeur rapide atteindra éventuellement la fin de la liste (None). Si un cycle est présent, le pointeur rapide finira par rattraper le pointeur lent à l'intérieur du cycle. Si les deux pointuers se rencontrent, cela confirme l'existence d'un cycle.

class NoeudListe:
    def __init__(self, val=0, suivant=None):
        self.valeur = val
        self.suivant = suivant

class DetecteurCycleListe:
    def a_un_cycle(self, tete: NoeudListe) -> bool:
        if not tete or not tete.suivant:
            return False # Une liste vide ou à un seul nœud ne peut pas avoir de cycle

        pointeur_lent = tete
        pointeur_rapide = tete

        while pointeur_rapide and pointeur_rapide.suivant:
            pointeur_lent = pointeur_lent.suivant          # Avance d'un pas
            pointeur_rapide = pointeur_rapide.suivant.suivant  # Avance de deux pas

            if pointeur_lent == pointeur_rapide:
                return True  # Les pointeurs se sont rencontrés, il y a un cycle

        return False # Le pointeur rapide a atteint la fin de la liste, pas de cycle

# Exemple d'utilisation (nécessiterait la construction d'une liste chaînée avec/sans cycle)
# tete = NoeudListe(3, NoeudListe(2, NoeudListe(0, NoeudListe(-4))))
# tete.suivant.suivant.suivant.suivant = tete.suivant # Crée un cycle où -4 pointe vers 2
#
# d = DetecteurCycleListe()
# print(d.a_un_cycle(tete)) # Output: True

3. Point d'Intersection de Deux Listes Chaînées

Trouver le premier nœud commun à deux listes chaînées distinctes est un problème classique. Une approche efficace utilise une table de hachage (ou un ensemble) pour mémoriser les nœuds de l'une des listes.

La stratégie est la suivante :

1. Parcourir la première liste chaînée (liste_A) et stocker chaque nœud dans un ensemble. Cela nous permet de vérifier rapidement si un nœud a déjà été rencontré.
2. Parcourir la seconde liste chaînée (liste_B). Pour chaque nœud de liste_B, vérifier s'il est présent dans l'ensemble des nœuds de liste_A.
3. Le premier nœud de liste_B qui est trouvé dans l'ensemble est le point d'intersection.
4. Si la fin de liste_B est atteinte sans qu'aucun nœud commun ne soit trouvé, alors les deux listes ne se croisent pas.

class NoeudListe: # Définition réutilisée ou à inclure si non présente
    def __init__(self, val=0, suivant=None):
        self.valeur = val
        self.suivant = suivant

class RechercheIntersection:
    def trouver_intersection(self, tete_A: NoeudListe, tete_B: NoeudListe) -> NoeudListe:
        nœuds_visites_A = set()

        pointeur_A = tete_A
        while pointeur_A:
            nœuds_visites_A.add(pointeur_A)
            pointeur_A = pointeur_A.suivant

        pointeur_B = tete_B
        while pointeur_B:
            if pointeur_B in nœuds_visites_A:
                return pointeur_B # Premier nœud commun trouvé
            pointeur_B = pointeur_B.suivant

        return None # Aucune intersection trouvée

# Exemple d'utilisation (nécessiterait la construction de deux listes chaînées qui se croisent)
# commun = NoeudListe(8, NoeudListe(4))
# liste1 = NoeudListe(4, NoeudListe(1, commun))
# liste2 = NoeudListe(5, NoeudListe(6, NoeudListe(1, commun)))
#
# ri = RechercheIntersection()
# intersection_node = ri.trouver_intersection(liste1, liste2)
# if intersection_node:
#     print(f"Les listes se croisent au nœud avec la valeur: {intersection_node.valeur}") # Output: 8
# else:
#     print("Pas d'intersection.")

4. Vérification d'un Nombre Heureux

Un "nombre heureux" est un entier positif qui, lorsqu'il est soumis à un processus itératif, aboutit finalement à 1. Le processus consiste à remplacer le nombre par la somme des carrés de ses chiffres. Si ce processus ne mène jamais à 1 mais entre dans une boucle infinie, le nombre n'est pas heureux.

Pour détecter si un nombre est heureux, nous devons identifier si le processus de sommation des carrés des chiffres :

1. Atteint 1 (le nombre est heureux).
2. Entre dans une boucle qui ne contient pas 1 (le nombre n'est pas heureux).

Une façon de détecter une boucle est d'utiliser un ensemble pour stocker tous les nombres générés au cours du processus. Si un nombre est généré à nouveau et qu'il est déjà présent dans l'ensemble, cela signifie qu'une boucle est détectée et que le nombre n'est pas heureux.

class DetecteurNombreHeureux:
    def _somme_carres_chiffres(self, num: int) -> int:
        somme = 0
        while num > 0:
            chiffre = num % 10  # Obtenir le dernier chiffre
            somme += chiffre * chiffre
            num //= 10          # Supprimer le dernier chiffre (division entière)
        return somme

    def est_heureux(self, n: int) -> bool:
        historique_calculs = set() # Pour détecter les cycles
        nombre_actuel = n

        # Continuer tant que le nombre n'est pas 1 et qu'il n'est pas déjà apparu dans l'historique
        while nombre_actuel != 1 and nombre_actuel not in historique_calculs:
            historique_calculs.add(nombre_actuel)
            nombre_actuel = self._somme_carres_chiffres(nombre_actuel)

        return nombre_actuel == 1 # Retourne vrai si 1 est atteint, faux si une boucle est détectée
                                # (c'est-à-dire si nombre_actuel est dans historique_calculs)

# Exemple d'utilisation
# dnh = DetecteurNombreHeureux()
# print(dnh.est_heureux(19)) # Output: True
# print(dnh.est_heureux(2))  # Output: False

5. Vérification de Chaînes Isomorphes

Deux chaînes de caractères, chaine_s et chaine_t, sont dites isomorphes si les caractères de chaine_s peuvent être remplacés pour obtenir chaine_t. Cette transformatoin doit respecter les règles suivantes :

1. Chaque occurrence d'un caractère de chaine_s doit être mappée au même caractère de chaine_t.
2. Des caractères distincts de chaine_s ne peuvent pas être mappés au même caractère de chaine_t. (Exemple: "ab" et "aa" ne sont pas isomorphes car 'b' ne peut pas mapper à 'a' si 'a' de "ab" mappe déjà à 'a' de "aa").
3. L'ordre des caractères doit être préservé.
4. Un caractère peut être mappé à lui-même.

Pour vérifier l'isomorphisme, nous pouvons utiliser deux tables de hachage (dictionnaires). Une pour mapper les caractères de chaine_s vers chaine_t, et l'autre pour mapper les caractères de chaine_t vers chaine_s. Cela permet de garantir que les règles de correspondance univoque (bijective) sont respectées dans les deux directions.

class VerificateurIsomorphe:
    def sont_isomorphes(self, chaine_s: str, chaine_t: str) -> bool:
        if len(chaine_s) != len(chaine_t):
            return False # Les chaînes doivent avoir la même longueur

        # Dictionnaire pour mapper les caractères de s vers t
        map_s_vers_t = {}
        # Dictionnaire pour mapper les caractères de t vers s (pour assurer l'unicité inverse)
        map_t_vers_s = {}

        for i in range(len(chaine_s)):
            char_s = chaine_s[i]
            char_t = chaine_t[i]

            # Vérifier la cohérence du mappage s -> t
            if char_s in map_s_vers_t:
                if map_s_vers_t[char_s] != char_t:
                    return False # Mappage incohérent: char_s était déjà mappé à autre chose
            else:
                map_s_vers_t[char_s] = char_t # Créer un nouveau mappage

            # Vérifier la cohérence du mappage t -> s (pour la condition: différents chars de s ne peuvent pas mapper au même char de t)
            if char_t in map_t_vers_s:
                if map_t_vers_s[char_t] != char_s:
                    return False # Mappage incohérent: char_t était déjà la cible d'un autre char_s
            else:
                map_t_vers_s[char_t] = char_s # Créer un nouveau mappage inverse
        
        return True # Toutes les conditions d'isomorphisme sont respectées

# Exemple d'utilisation
# vi = VerificateurIsomorphe()
# print(vi.sont_isomorphes("egg", "add"))    # Output: True
# print(vi.sont_isomorphes("foo", "bar"))    # Output: False
# print(vi.sont_isomorphes("paper", "title")) # Output: True
# print(vi.sont_isomorphes("badc", "baba"))   # Output: False (c doit mapper à c, mais b mappe à b deux fois)