導入。

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

2 つのポインタ。

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

2 つのポインターの型。

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

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

を持つペアの検索などがあります。

アプローチ

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

例:文字列 s を指定すると、空白と最初の語順を維持したまま、文内の各単語の文字の順序が逆になります。

def reverseWords(s: str) -> str: Words = s.split() # 入力文字列を単語に分割します range(len(word)) 内の i の場合: left = 0 # 左ポインタを初期化します right = len(words[i]) - 1 # 右ポインタを初期化します split_word = list(words[i]) # 単語を文字のリストに変換します while left 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 ポインタが同じ方向に移動します。

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

アプローチ

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

例:2 つの文字列 word1 と word2 が与えられています。 word1 から始めて交互に文字を追加して、文字列を結合します。文字列が他の文字列より長い場合は、マージされた文字列の末尾に追加の文字を追加します。

def mergeAlternately(word1: str, word2: str) -> str: # マージされた文字を格納するために空のリストを初期化します 単語リスト = [] # 各単語の先頭から開始して 2 つのポインターを初期化します ポインタ_1 = 0 ポインタ_2 = 0 # ポインタの 1 つがそれぞれの単語の終わりに到達するまでループします pointer_1 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 結論

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

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