剖析二指针技术-Python教程-PHP中文网

剖析二指针技术

王林

发布： 2024-08-11 12:32:15

原创

465 人浏览过

Dissecting the two pointer technique

介绍。

即使掌握了数组和列表的基础知识，解决与这些数据结构相关的问题有时也会让人感到不知所措。除了了解数据结构本身 - 以及它们的操作以及时间和空间复杂性；掌握适用于这些问题的各种技术可以使这个过程变得更加容易。
考虑到数组或列表可能出现的各种问题尤其如此。在这篇博文中，我将重点讨论这样一种技术：两指针技术，它对于解决数组或列表问题特别有效。

两个指针。

两指针技术是一种算法方法，对于求解数组或序列特别有效。这意味着该方法也可以应用于字符串和链表。
它涉及使用两个不同的指针来遍历数据结构，通常会以较低的时间复杂度提供有效的解决方案。

两个指针的类型。

指针相互靠近。

这种方法涉及两个指针，从数据结构的相对两端开始并向彼此移动，这意味着指针向相反的方向移动。这种类型的双指针技术在您想要查找一对满足某些条件的元素或比较两端元素的情况下特别有用。常见用例包括检查回文或查找具有特定总和的对

方法

初始化指针：从数据结构的开头（左）开始，另一个指针位于数据结构的末尾（右）。
移动指针：根据给定的条件调整指针彼此相对的方向。
检查条件：继续将指针相互靠近，直到找到所需结果或满足特定条件

示例：给定一个字符串 s，反转句子中每个单词的字符顺序，同时仍然保留空格和初始单词顺序。

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

登录后复制

指针朝同一方向移动。

在这种方法中，两个指针从数据结构的同一端开始，并向相同的方向移动。当您需要跟踪窗口或阵列内的子阵列时，通常会使用此技术，使您可以根据特定条件有效地移动和调整窗口。常见用例包括滑动窗口技术和合并排序数组。

方法

初始化两个指针：从数据结构开头的两个指针开始。
移动指针：根据特定条件将一个指针（通常是速度较快的指针）移到另一个指针之前。
调整指针：根据需要修改指针的位置，以保持所需的窗口条件。

示例：给定两个字符串 word1 和 word2。通过以交替顺序添加字母来合并字符串，从 word1 开始。如果一个字符串比另一个字符串长，请将附加字母附加到合并字符串的末尾。

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)

登录后复制