デュアルポインタとスライディングウィンドウアルゴリズムテンプレート

[[428819]]

ダブルポインタのアルゴリズム原理は、2 つのポインタを介して 1 つの for ループで 2 つの for ループの作業を完了することです。時間計算量は から最適化されます。

ダブルポインターアルゴリズムのテンプレートは比較的単純であり、突破口は主に問題の単調性を見つけてそれを利用することにあります。

高速ポインターと低速ポインター

高速ポインタと低速ポインタはリンクリストの操作手法であり、「ウサギとカメの競争」という面白い名前も付けられています。

• 要素を削除します:

クラスソリューション{
公共：
 int要素を削除(ベクトル< int >& 数値, int値) {
スローインデックス = 0;
 ( int fastIndex = 0; fastIndex < nums.size ( ) ); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
 slowIndexを返します。
    }
 };

• リングの入口位置: 高速ポインターと低速ポインターを使用します。高速ポインターは 2 ステップ進み、低速ポインターは 1 ステップ進みます。ループがある場合、2 つのポインタは遅かれ早かれ出会います。ループがない場合、高速ポインタは末尾に到達してループを終了します。ループがある場合は、遅いポインターが再び開始し、速いポインターが交差点になります。同じ速度の 2 つのポインターの交差点が入り口である必要があります。

クラスソリューション{
公共：
    リストノード *detectCycle(リストノード *head) {
        ListNode* 遅い = ヘッド;
        ListNode* fast = ヘッド;
        while (fast && fast-> next ){
            fast = fast-> next- > next ;
            slow = slow-> next ;
            if (fast == slow) break;
        } 
         
        if (fast && fast-> next ){
            遅い = 頭;
            while(遅い!=速い){
                slow = slow-> next ;
                fast = fast-> next ;
            }
ゆっくりと戻る;
        }
 nullptrを返します。
    }
 };

• リンク リストの中間ノード: 高速ポインターと低速ポインターを適用します。高速ポインターは 2 ステップ実行し、低速ポインターは 1 ステップ実行します。高速ポインタが端に到達すると、低速ポインタはちょうど半分まで移動した状態になり、戻り点は中間のノードになります。
• リンク リストの N 番目から最後のノードを削除します。最初に高速ポインターが n ステップ移動し、次に高速ポインターと低速ポインターが同時に移動し、高速ポインターが最後に到達すると、低速ポインターは n 番目から最後の位置にあります。

バックポインタ

典型的な逆ポインター問題には、N 和級数とバイナリ検索のバリエーションがあります。

N和シリーズの典型的な問題は、3つの数字の合計である。

 def threeSum(数値):
    nums.sort()
    # [-4, -1, -1, 0, 1, 2]
    res_list = []
    # ヘッドループ検索
i が範囲(len(nums))内にある場合:
     # 条件nums[i] > nums[i - 1]をチェックする必要がある
        i == 0またはnums[i] > nums[i - 1] の場合:
            # 左端
            1 = i + 1 です
            # 右端
            r = 長さ(数値) - 1
            while l < r: # 検索中
                3つの合計 = nums[i] + nums[l] + nums[r]
                three_sum == 0の場合:
                    res_list.append([nums[i], nums[l], nums[r]])
                    l += 1 # 1ビット右にシフト
                    r -= 1 # 1ビット左にシフト
                    l < rかつnums[l] == nums[l - 1]の場合:
                        # 左から右へ、同じ値をスキップします
                        1 += 1
                    r > lかつnums[r] == nums[r + 1] の場合:
                        # 右から左へ、同じ値をスキップします
                        r -= 1
                three_sum > 0の場合:
                    # 0より大きい場合、右側の値が大きいので左に移動します
                    r -= 1
それ以外：
                    # ゼロ未満、左側の値が小さいので右に移動
                    1 += 1
 res_listを返す

4 つのバイナリ検索バリアントでは、Wang Zheng のアルゴリズム コラムによれば、low = 0、high = len(list) - 1 がハードコードされています。ループ条件は low <= high です。左に高く移動 = 中 - 1、右に低く移動 = 中 + 1

 def binary_search(数値、ターゲット):
 '' '標準バイナリ アルゴリズム テンプレート' ''  
    低い = 0
    high = len(nums) - 1 # 注 1 low と high は、検索するリストの部分を追跡するために使用されます。
    low <= high: # 注2 要素が1つに減っていない限り、チェックを続ける
        中 = (低 + 高) // 2
        リスト[mid] == ターゲットの場合:
戻る途中
        elif リスト[mid] > ターゲット:
            high = mid - 1 # 注3: 推測した数値が高すぎる
        elif list[mid] < ターゲット:
            low = mid + 1 # 注4: 推測した数字が小さすぎる
戻る途中
 
 
 def bsearch_low(数値、ターゲット):
 '' '固定値に等しい最初の値を見つける' ''  
    低い = 0
    高さ = 長さ(数値) - 1
    # <= はここに必要です
    低 <= 高の場合:
        # 注意: ((high - low) >> 1) を使用する場合は、二重拡張が必要です。
        中 = 低 + ((高 - 低) >> 1)
        nums[mid] < targetの場合:
            低 = 中 + 1
        elif nums[mid] > ターゲット:
            高 = 中 - 1
それ以外：
            mid == 0またはnums[mid-1] != target の場合:
戻る途中
それ以外：
                高 = 中 -1 
 
 -1を返す
 
 def bsearch_high(数値,ターゲット):
 '' '固定値に等しい最後のものを見つける' ''  
    低い = 0
    高さ = 長さ(数値) -1
    低 <= 高の場合:
        中 = 低 + ((高 - 低) >> 1 )
        nums[mid] > targetの場合:
            高さ = 中 - 1
        elif nums[mid] < ターゲット:
            低 = 中 +1
それ以外：
            mid == (len(nums) -1)またはnums[mid] != nums[mid+1] の場合:
戻る途中
それ以外：
                低 = 中 +1
 -1を返す
 
 '' '
指定された値以上の最初の要素を検索します
* たとえば、3、4、6、7、19というシーケンスで、5より大きい最初の要素である6を見つけて、 2を返します。
 * 最初の値が指定された値より大きい場合、前の値は指定された値より小さいことを意味します。
 '' '
 def bsearch_low_not_less(数値、ターゲット):
    低い = 0
    高さ = 長さ(数値) -1
    （低<=高）の場合：
        中 = 低 + ((高-低) >> 1)
        nums[mid] >= targetの場合:
            mid == 0またはnums[mid - 1] < target の場合:
戻る途中
それ以外：
                # 左に移動
                高 = 中 - 1
それ以外：
            # 右に移動
            低 = 中 +1
 -1を返す
 
 '' '
指定された値より小さい最初の要素を見つける
* たとえば、3、4、6、7、19というシーケンスで、5より小さい最初の要素である4を見つけて、1を返します。
 * 最初の値が指定された値より大きい場合、前の値は指定された値より小さいことを意味します。
 '' '
 def bsearch_high_not_greater(数値、ターゲット):
 '' '以下の最後の値を検索' ' '  
    低い = 0
    高さ = 長さ(数値) -1
    低 <= 高の場合:
        中 = 低 + (( 高 - 低 ) >> 1)
        nums[mid] <= targetの場合:
            (mid == len(nums) -1)または(nums[mid + 1] > target) の場合:
戻る途中
それ以外：
                低 = 中 +1
それ以外：
            高さ = 中間 -1
 -1を返す

スライディングウィンドウ

原文: https://mp.weixin.qq.com/s/ioKXTMZufDECBUwRRp3zaA

スライディング ウィンドウ アルゴリズムは、ダブル ポインター テクニックの最高レベルであり、主に 2 つの文字列を一致させる問題に使用されます。

スライディング ウィンドウの問題解決テンプレートを習得すると、一連の文字列一致問題を簡単に解決できます。

次のテンプレート コードは labuladong からのものであり、LeetCode の問題 76「最小ウィンドウ サブ文字列」を解決して、最小のカバー サブ文字列を見つけます。

 /* スライディングウィンドウアルゴリズムフレームワーク */
文字列minWindow(文字列s, 文字列t) {
     // 2 つの unordered_maps。1 つはパターン文字列内の文字数を記録し、もう 1 つのウィンドウはウィンドウ内の文字を記録します。
    unordered_map< char , int > 必要、ウィンドウ;
    // 初期化が必要
( char c : t )が必要です[c]++; 
 
整数 左= 0、右= 0;
    // 条件を満たした unordered_map の数
整数有効 = 0;
    //最小カバー部分文字列の開始インデックスと長さを記録する
int開始 = 0、長さ = INT_MAX;
    while (右< s.size ()) {
        // c はウィンドウに移動する文字です
char c = s[右];
        // ウィンドウを右に移動する
右++;
        // ウィンドウ内のデータに対して一連の更新を実行します
        if (need. count (c)) {
            ウィンドウ[c]++;
            if (window[c] == need[c])
                有効++;
        } 
 
        // 左のウィンドウを縮小するかどうかを決定します
        while (有効 == need.size ()) {
            // ここで最小被覆部分文字列を更新します
            （右-左< 長さ）の場合{
                開始 =左;
                len =右-左;
            }
            // dはウィンドウ外に移動する文字です
char d = s[左];
            // ウィンドウを左に移動する
左++;
            // ウィンドウ内のデータに対して一連の更新を実行します
            必要数( d)の場合
                if (window[d] == need[d])
                    有効- ;  
                ウィンドウ[d] --;  
            }
        }
    }
    // 最小の被覆部分文字列を返す
len == INT_MAXを返しますか?
 "" : s.substr(開始, 長さ);
 }

Pythonでは、unnodeed mapはcollections.defaultdictとcollections.Counterを使用して実装できます。