アルゴリズム:Sliding Window

先週末、やっとLeetCodeの試合に参加する暇がありました.そして、試合ですべてのテーマを完成したのは初めてです.ペナルティーを加えて試合時間を超えたが、以前に比べてかなり進歩した.今回のテーマは比較的簡単で、前の2つは暴力解法で、3つ目は動態計画の簡単な応用で、最後の1つは比較的に面白くて、私は最初はタイムアウトして、それからスライドウィンドウの思想で最適化することができることを発見しました.スライドウィンドウであるSliding Windowは、実はスライドウィンドウがアルゴリズムであるかどうかは分かりません.本ではこのアルゴリズムの紹介を見たことがありませんが、スライドウィンドウの考えはとても素晴らしいので、多くの問題で使えます.次に、今回の最後の問題を例にスライドウィンドウを紹介します.
スライドウィンドウ
スライドウィンドウは、配列上で区間を維持し、配列を巡るまで先頭と末尾を調整します.スライドウィンドウを適用する問題は、配列内の区間を見つけることが要求されることが多い.配列内のすべての区間を遍歴すると、時間複雑度はO(n 2)であり、スライドウィンドウの時間複雑度はO(n)である.
Smallest Rotation with Highest Score
に質問
この配列の各要素を左に移動(境界を越えた要素を最も右に補う)して新しい配列を得ることができ、長さnの配列は合計nの異なる配列を得ることができる配列を与える.次に各配列に点数をつけ、1つの配列の各要素の値が下付き文字より大きくなければ1点を得て、最高点の配列を求めます.
構想
最初は簡単に考えて、各配列の点数を求めて最高点の配列を取ったが、タイムアウトした.配列スコアを求めるときは配列の各要素を遍歴し、各要素に対応して得点可能な配列に1点、すなわち各要素の操作時間の複雑さはO(n)である.実際、各要素が対応して得点可能な配列は連続しており、区間は先頭のみを記録していると見なすことができる.すなわち、最初の配列の得点は前の配列より1多く、最後の配列の得点は後の配列より1多い.これにより,各配列の点数と前の配列の点数との関係を得ることができ,一度遍歴すれば最高点の配列を得ることができる.
コード#コード#

class Solution {
public:
    int bestRotation(vector& A) {
        vector v(A.size()+1, 0);  //        
        for (int i = 0; i < A.size(); ++i) {
            if (A[i] <= i) {  //       
                ++v[0];  //   0     
                --v[i + 1 - A[i]];  //        ，        ，    
                ++v[i + 1];  //      ，     ，      ，    
            } else {  //      
                ++v[i + 1];  //            ，       ，      ，    
                --v[i + 1 + A.size() - A[i]];  //        ，        ，    
            }
        }
        int K = 0;
        int ans = v[0];  //      
        int max = ans;
        for (int i = 1; i < A.size(); ++i) {
            ans += v[i];  //                
            if (ans > max) {
                K = i;
                max = ans;
            }
        }
        return K;
    }
};

感想
今回の試合が終わった後、LeetCodeのテーマは簡単だと思います.時には巧みな考えが必要ですが、全体的には複雑ではありません.アルゴリズムと学習の考えを熟知するのに適しています.これからはCodeForceの問題のような複雑な問題を探して、プログラミングコンテストの能力を高めるつもりです.今学期はACMの准备に力を入れて、自分のプログラミングの限界がどこにあるかを见て、これからの勉强と仕事に役立つことを望んでいます.