2 ポインター手法を詳しく分析する

導入。

配列とリストの基本をマスターした後でも、これらのデータ構造に関連する問題を解決するのは困難に感じることがあります。データ構造そのものを理解するだけでなく、その操作や時間と空間の複雑さも併せて理解します。これらの問題に適用されるさまざまなテクニックを把握すると、プロセスがはるかに簡単になります。
配列やリストで発生する可能性のあるさまざまな問題を考慮すると、これは特に当てはまります。このブログ投稿では、そのようなテクニックの 1 つである 2 ポインター テクニックに焦点を当てます。これは、配列やリストの問題に取り組むのに特に効果的です。

2 つのポインタ。

2 ポインター手法はアルゴリズムによるアプローチであり、配列やシーケンスを解決する場合に特に効果的です。これは、このアプローチが文字列やリンク リストにも適用できることを意味します。
これには、データ構造をトラバースするための 2 つの異なるポインターの使用が含まれ、多くの場合、時間の複雑さを軽減した効率的な解決策が得られます。

2 つのポインターの型。

ポインタが互いに向かって移動します。

このアプローチには、データ構造の反対側の端から開始して相互に向かう 2 つのポインターが含まれます。つまり、ポインターは反対方向に移動します。このタイプの 2 ポインター手法は、特定の条件を満たす要素のペアを検索する場合、または両端の要素を比較する場合に特に役立ちます。一般的な使用例には、回文のチェックや特定の合計を持つペアの検索などがあります

アプローチ

1. ポインタの初期化: データ構造の先頭 (左) に 1 つのポインタを配置し、データ構造の末尾 (右) にもう 1 つのポインタを配置します。
2. ポインタを移動する: 指定された条件に基づいて、ポインタを相互に向けて調整します。
3. 条件の確認: 目的の結果が見つかるか、特定の条件が満たされるまで、ポインタを互いに向かって動かし続けます

例:文字列 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

ポインタが同じ方向に移動します。

このアプローチでは、両方のポインターがデータ構造の同じ端から開始され、同じ方向に移動します。この手法は、配列内のウィンドウまたはサブ配列を追跡する必要がある場合によく使用され、特定の条件に基づいてウィンドウを効率的に移動および調整できます。一般的な使用例には、スライディング ウィンドウ手法やソートされた配列のマージなどがあります。

アプローチ

1. 2 つのポインターを初期化する: データ構造の先頭にある両方のポインターから開始します。
2. ポインタを移動する: 特定の条件に基づいて、一方のポインタ (通常は高速なポインタ) を他方のポインタより先に移動します。
3. ポインタを調整する: 必要に応じてポインタの位置を変更し、希望のウィンドウ条件を維持します。

例:2 つの文字列 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)

結論

2 ポインター手法は、アルゴリズムの世界、特に配列、文字列、リンク リストを扱う場合、多用途かつ効率的なツールです。ポインタが互いに向かって移動している場合でも、同じ方向に移動している場合でも、このアプローチにより複雑な問題を単純化し、ソリューションのパフォーマンスを向上させることができます。これらの戦略を理解し、適用することで、コーディングの幅広い課題に取り組む準備が整います。

さまざまな問題を解決し、さまざまなシナリオを試して、これらのテクニックを実践することをお勧めします。時間と経験を積めば、2 ポインタ テクニックが問題解決ツールキットに非常に貴重な追加物であることがわかるでしょう。

以上が2 ポインター手法を詳しく分析するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。