Disséquer la technique à deux pointeurs

Introduction.

Même après avoir maîtrisé les bases des tableaux et des listes, résoudre les problèmes liés à ces structures de données peut parfois sembler insurmontable. Au-delà de la compréhension des structures de données elles-mêmes, ainsi que de leurs opérations et de leurs complexités temporelles et spatiales ; maîtriser diverses techniques qui s'appliquent à ces problèmes peut rendre le processus beaucoup plus facile.
Cela est particulièrement vrai compte tenu de la grande variété de problèmes pouvant survenir avec les tableaux ou les listes. Dans cet article de blog, je me concentrerai sur l'une de ces techniques : la technique à deux pointeurs, qui est particulièrement efficace pour résoudre les problèmes de tableau ou de liste.

Deux pointeurs.

La technique des deux pointeurs est une approche algorithmique, particulièrement efficace pour résoudre des tableaux ou des séquences. Cela signifie que l'approche peut également être appliquée aux chaînes et aux listes chaînées.
Cela implique l'utilisation de deux pointeurs distincts pour parcourir la structure des données, conduisant souvent à une solution efficace avec une complexité temporelle moindre.

Types de deux pointeurs.

Les pointeurs se rapprochent.

Cette approche implique deux pointeurs partant des extrémités opposées de la structure de données et se déplaçant l'un vers l'autre, ce qui signifie que les pointeurs se déplacent dans des directions opposées. Ce type de technique à deux pointeurs est particulièrement utile dans les scénarios dans lesquels vous souhaitez trouver une paire d'éléments qui remplissent certaines conditions ou lorsque vous comparez des éléments des deux côtés. Les cas d'utilisation courants incluent la recherche d'un palindrome ou la recherche de paires avec une somme spécifique

Approche

1. Initialisez les pointeurs : commencez avec un pointeur au début (à gauche) et l'autre à la fin (à droite) de la structure de données.
2. Déplacez les pointeurs : ajustez les pointeurs les uns vers les autres en fonction des conditions données.
3. Vérifier les conditions : continuez à déplacer les pointeurs les uns vers les autres jusqu'à ce que le résultat souhaité soit trouvé ou qu'une condition spécifique soit remplie

Exemple :Étant donné une chaîne s, inversez l'ordre des caractères dans chaque mot dans une phrase tout en préservant les espaces et l'ordre initial des mots.

def reverseWords(s: str) -> str:
    words = s.split()  # Split the input string into words

    for i in range(len(words)):
        left = 0  # Initialize the left pointer
        right = len(words[i]) - 1  # Initialize the right pointer
        split_word = list(words[i])  # Convert the word into a list of characters

        while left < right:  # Continue until the pointers meet in the middle
            # Swap the characters at the left and right pointers
            temp = split_word[left]
            split_word[left] = split_word[right]
            split_word[right] = temp

            left += 1  # Move the left pointer to the right
            right -= 1  # Move the right pointer to the left

        words[i] = "".join(split_word)  # Rejoin the characters into a word

    return " ".join(words)  # Join the reversed words into a final string

Pointeurs se déplaçant dans la même direction.

Dans cette approche, les deux pointeurs partent de la même extrémité de la structure de données et se déplacent dans la même direction. Cette technique est souvent utilisée lorsque vous devez suivre une fenêtre ou un sous-tableau au sein d'un tableau, vous permettant de déplacer et d'ajuster efficacement la fenêtre en fonction de certaines conditions. Les cas d'utilisation courants incluent la technique de la fenêtre coulissante et la fusion de tableaux triés.

Approche

1. Initialiser deux pointeurs : commencez par les deux pointeurs au début de la structure de données.
2. Déplacez les pointeurs : déplacez un pointeur (généralement le plus rapide) devant l'autre en fonction de conditions spécifiques.
3. Ajustez les pointeurs : modifiez les positions des pointeurs si nécessaire pour maintenir les conditions de fenêtre souhaitées.

Exemple :Vous recevez deux chaînes mot1 et mot2. Fusionnez les chaînes en ajoutant des lettres dans un ordre alterné, en commençant par mot1. Si une chaîne est plus longue que l'autre, ajoutez les lettres supplémentaires à la fin de la chaîne fusionnée.

def mergeAlternately(word1: str, word2: str) -> str:
    # Initialize an empty list to store the merged characters
    word_list = []

    # Initialize two pointers, starting at the beginning of each word
    pointer_1 = 0
    pointer_2 = 0

    # Loop until one of the pointers reaches the end of its respective word
    while pointer_1 < len(word1) and pointer_2 < len(word2):
        # Append the character from word1 at pointer_1 to the list
        word_list.append(word1[pointer_1])
        # Append the character from word2 at pointer_2 to the list
        word_list.append(word2[pointer_2])

        # Move both pointers forward by one position
        pointer_1 += 1
        pointer_2 += 1

    # If there are remaining characters in word1, add them to the list
    if pointer_1 < len(word1):
        word_list.append(word1[pointer_1:])

    # If there are remaining characters in word2, add them to the list
    if pointer_2 < len(word2):
        word_list.append(word2[pointer_2:])

    # Join the list of characters into a single string and return it
    return "".join(word_list)

Conclusion

La technique des deux pointeurs est un outil polyvalent et efficace dans le monde des algorithmes, notamment lorsqu'il s'agit de tableaux, de chaînes et de listes chaînées. Que les pointeurs se rapprochent ou dans la même direction, cette approche peut simplifier des problèmes complexes et améliorer les performances de vos solutions. En comprenant et en appliquant ces stratégies, vous serez mieux équipé pour relever un large éventail de défis de codage.

Je vous encourage à pratiquer ces techniques en résolvant divers problèmes et en expérimentant différents scénarios. Avec le temps et l'expérience, vous découvrirez que la technique des deux points est un ajout inestimable à votre boîte à outils de résolution de problèmes.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!