デュアルポインタ(デュアルインデックス)アルゴリズムの紹介(c++)

0概要
二重ポインタアルゴリズムはいくつかの配列問題でよく用いられ、二つのポインタを用いて配列を遍歴して問題を解く方法を指す.ここでのポインタは一般化され、c/c++のポインタである可能性があり、二つの整数の下付き記号である可能性もある.ダブルポインタアルゴリズムには2つの形式があり、1つは衝突ポインタと呼ばれ、2つのポインタが両端から中間に近づく.もう1つはスローポインタで、2つのポインタが統一方向に移動し、ウィンドウをスライドさせる方法が一般的なスローポインタ方法です.
1突き当て針
衝突指針に対する考え方は前述したように,以下に具体的な例題を挙げて説明する.この問題はleetcode 345問題です.タイトルは以下の通り.
文字列を入力として関数を作成し、文字列のアクセント文字を反転します.例1:入力:leetcode出力:leotcede
衝突ポインタを使用する考え方は、2つのポインタiを初期化し、jは文字列の先頭の末尾に位置し、iは右に原音のアルファベットを探し、停止を見つけることである.j左に母音のアルファベットを探して、止まっているのを見つけます;次に、i>jまで両者が対話する.具体的なコードでは配列の境界を越える問題に注意すればいい.コードは次のとおりです.

class Solution {
public:
    string reverseVowels(string s) 
    {
        for(int i = 0,j = s.size()-1; i < j;)
        {
            while(i < s.size() && !isVowet(s[i]))
                ++i;
            while(j > 0 && !isVowet(s[j]))
                --j;
            if(i < j)
                std::swap(s[i],s[j]);
            ++i,--j;
        }
        return s;
    }

    bool isVowet(char c)//      
    {
        if(c == 'a' || c == 'o' || c == 'e'
            || c == 'i' || c == 'u')
            return true;
        if(c == 'A' || c == 'O' || c == 'E'
            || c == 'I' || c == 'U')
            return true;
        else
            return false;
    }
};

2スライドウィンドウ
スライドウィンドウは文字列の問題でよく見られますが、2つのポインタを同じ方向に動かし、具体的な条件に従ってポインタをスライドさせます.次に具体的なテーマを結びつけて説明します.leetcode第3題です.タイトルの説明:
文字列を指定すると、重複文字が含まれていない長男の列の長さを見つけてください.入力:“abcabcbb”出力:3解釈:重複文字のない最長子列は“abc”であるため、その長さは3
この問題は二重ポインタアルゴリズムを用いることができる.まず、2つのポインタi=0,j=1を定義し、次に、文字の出現回数を統計するためのbuf[256]を準備する.1文字が表示されていない場合は、jポインタをスライドし、そうでない場合はiポインタをスライドします.スライドするたびに、現在の文字長が最大長かどうかを判定します.コードは次のとおりです.

class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        int i = 0,j = -1;
        int maxLen = 0;
        char buf[256];
        memset(buf,0,sizeof(buf));
        while(i < s.size())
        {
            if(j+1 < s.size() && buf[s[j+1]] == 0)
            {
                ++j;
                buf[s[j]] = 1;
            }
            else
            {
                buf[s[i]] = 0;
                ++i;
            }
            maxLen = max(maxLen,j-i+1);
        }
        return maxLen;
    }
};