Introduction

Cet article détaille des solutions initiales et des implémentations locales pour des problèmes de LeetCode. Les approches peuvent ne pas être optimales, et les discussions pour améliorer les solutions sont encouragées.

1er avril : 2810. Clavier défectueux

Considérons les caractères un par un. Si le caractère est 'i', nous changeons la direction d'insertion. Sinon, nous ajoutons le caractère au début ou à la fin de la liste selon la direction courante. Une variable booléenne indique si l'insertion est en avant ou en arrière.

def create_final_text(s):
    direction_forward = True
    result_chars = []
    for symbol in s:
        if symbol == "i":
            direction_forward = not direction_forward
        elif direction_forward:
            result_chars.append(symbol)
        else:
            result_chars.insert(0, symbol)
    if not direction_forward:
        result_chars.reverse()
    return ''.join(result_chars)

2 avril : 894. Tous les arbres binaires complets possibles

Les arbres binaires complets ont un nombre impair de nœuds. Nous utilisons une mémoïsation pour stocker les arbres pour chaque nombre de nœuds. Pour un nombre donné, nous récursivement construisons des arbres en divisant les nœuds entre les sous-arbres gauche et droit.

class NodeBT:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def generate_full_binary_trees(n):
    if n < 3 or n % 2 == 0:
        return []
    memo = {}
    memo[1] = [NodeBT(0)]
    def build_trees(count):
        if count in memo:
            return memo[count]
        forest = []
        for left_count in range(1, count - 1, 2):
            left_trees = build_trees(left_count)
            right_trees = build_trees(count - 1 - left_count)
            for l_tree in left_trees:
                root = NodeBT(0)
                root.left = l_tree
                for r_tree in right_trees:
                    root.right = r_tree
                    forest.append(root)
        memo[count] = forest
        return forest
    return build_trees(n)

3 avril : 1379. Trouver le nœud correspondant dans un arbre cloné

Utilisation d'une recherche en profondeur (DFS) pour parcourir simultanément les arbres original et cloné. Lorsque le nœud cible est trouvé dans l'arbre original, nous retournons le nœud correspondant dans l'arbre cloné.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def locate_target_node(original, cloned, target):
    def dfs_search(orig_node, clone_node):
        if orig_node is None:
            return None
        if orig_node == target:
            return clone_node
        left_res = dfs_search(orig_node.left, clone_node.left)
        right_res = dfs_search(orig_node.right, clone_node.right)
        return left_res if left_res else right_res
    return dfs_search(original, cloned)

4 avril : 2192. Tous les ancêtres d'un nœud dans un graphe orienté acyclique

Si x est un ancêtre de y, alors les ancêtres de x sont aussi des ancêtres de y. Nous utilisons un ensemble pour les nœuds dont tous les ancêtres ont été traités, un compteur pour le nombre d'ancêtres non traités, et une liste pour stocker les ancêtres. Une approche de tri topologique est appliquée.

def compute_ancestors(num_nodes, edges):
    processed_nodes = set(range(num_nodes))
    ancestors = [set() for _ in range(num_nodes)]
    children_adj = [[] for _ in range(num_nodes)]
    pending_ancestors = [0] * num_nodes
    for src, dst in edges:
        if dst in processed_nodes:
            processed_nodes.discard(dst)
        children_adj[src].append(dst)
        pending_ancestors[dst] += 1
    while processed_nodes:
        next_nodes = set()
        for node in processed_nodes:
            for child in children_adj[node]:
                ancestors[child].add(node)
                ancestors[child].update(ancestors[node])
                pending_ancestors[child] -= 1
                if pending_ancestors[child] == 0:
                    next_nodes.add(child)
        processed_nodes = next_nodes
    return [sorted(list(a)) for a in ancestors]

5 avril : 1026. Différence maximale entre un nœud et ses ancêtres

Depuis la racine, nous parcourons les nœuds en gardant une trace des valeurs minimales et maximales rencontrées dans le chemin courant. Pour chaque nœud, nous calculons la différence absolue avec ces valeurs extrêmes et mettons à jour la différence maxiamle globale.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_difference_ancestor(root):
    global_max_diff = 0
    def traverse_tree(node, current_min, current_max):
        nonlocal global_max_diff
        if node is None:
            return
        global_max_diff = max(global_max_diff, abs(current_min - node.val))
        global_max_diff = max(global_max_diff, abs(current_max - node.val))
        updated_min = min(current_min, node.val)
        updated_max = max(current_max, node.val)
        traverse_tree(node.left, updated_min, updated_max)
        traverse_tree(node.right, updated_min, updated_max)
    traverse_tree(root, root.val, root.val)
    return global_max_diff

6 avril : 1483. Le K-ième ancêtre d'un nœud dans un arbre

Utilisation de la technique de binary lifting avec une table de programmation dynamique. Pour chaque nœud, nous stockons ses ancêtres à des puissances de deux. La relation récursive permet de remonter rapidement dans l'arbre.

class KthAncestorFinder:
    def __init__(self, node_count, parent_array):
        self.ancestor_table = [[] for _ in range(node_count)]
        for i in range(node_count):
            self.ancestor_table[i].append(parent_array[i])
        level = 1
        while True:
            all_zero = True
            for i in range(node_count):
                mid_ancestor = self.ancestor_table[i][level - 1]
                if mid_ancestor != -1:
                    far_ancestor = self.ancestor_table[mid_ancestor][level - 1]
                else:
                    far_ancestor = -1
                self.ancestor_table[i].append(far_ancestor)
                if far_ancestor != -1:
                    all_zero = False
            if all_zero:
                break
            level += 1

    def query_kth_ancestor(self, node, k):
        current_node = node
        bit_index = 0
        while k > 0 and current_node != -1:
            if bit_index >= len(self.ancestor_table[current_node]):
                return -1
            if k & 1:
                current_node = self.ancestor_table[current_node][bit_index]
            k >>= 1
            bit_index += 1
        return current_node

7 avril : 1600. Ordre de succession au trône

Cela peut être modélisé comme un arbre n-aire. L'ordre de succession suit un parcours préfixe (racine-gauche-droite). Nous utilisons un ensemble pour les personnes décédées et une map pour les enfants de chaque personne. Le parcours récursif génère la liste ordonnée.

class SuccessionSystem:
    def __init__(self, king_name):
        from collections import defaultdict
        self.deceased_set = set()
        self.root_king = king_name
        self.children_dict = defaultdict(list)

    def register_birth(self, parent, child):
        self.children_dict[parent].append(child)

    def mark_death(self, person):
        self.deceased_set.add(person)

    def generate_order(self):
        succession_list = []
        def preorder_traversal(name):
            if name not in self.deceased_set:
                succession_list.append(name)
            for child_name in self.children_dict.get(name, []):
                preorder_traversal(child_name)
        preorder_traversal(self.root_king)
        return succession_list