トーク・ウィズ・ユーシリーズ #2-Python チュートリアル-php.cn

イントロ

今日は、さまざまなアルゴリズムの問題に取り組むために使用される概念についての概要を開始します。特定の概念を理解すると、潜在的な解決策についてどの角度から考え始めるべきかが直感的にわかるかもしれません。

世の中にはさまざまな概念がありますが、それほど多くはありません。今日はスライディングウィンドウのコンセプトに注目していきます。

引き違い窓

Talk with You Series #2

スライディングウィンドウの概念は、一見しただけよりも少し複雑です。実際の例でそれを説明します。現時点では、概念的なアイデアとして、移動する必要があるウィンドウがあるということを覚えておいてください。早速例から始めてみましょう。

整数の配列とサブ配列の事前定義されたサイズがあると仮定します。値の合計が他のサブ配列の中で最大となるサブ配列 (別名ウィンドウ) を見つけるように求められます。

array = [1, 2, 3]
window_size = 2

# conceptually
subarray_1 = [1, 2] --> sum 3
subarray_2 = [2, 3] --> sum 5

maximum_sum = 5

ログイン後にコピー

そうですね、非常に簡単に見えます:
(1) サイズ 2 の引き違い窓
(2) 2 つのサブ配列
(3) それぞれの
の合計を数えます (4) それらの間の最大値を見つけます

実装してみましょう。

def foo(array: List[int], size: int) -> int:
    maximum = float("-inf")

    for idx in range(size, len(array)+1):
        left, right = idx-size, idx
        window = array[left:right]
        maximum = max(maximum, sum(window))

    return maximum

ログイン後にコピー

そうですね、スライディングウィンドウの概念を効果的に使用したようです。実際には、正確にはそうではありません。解の時間計算量を理解することで、その「証明」が得られるかもしれません。

計算量は O(l)*O(w) になります。ここで、l は配列内のウィンドウの量、w はウィンドウ内の要素の量です。言い換えれば、l 個のウィンドウを走査する必要があり、l 番目のウィンドウごとに w 要素の合計を計算する必要があります。

ここで疑わしいのは何ですか?質問に答えるための反復を概念的に描いてみましょう。

array = [1, 2, 3, 4]
window_size = 3

iterations
1 2 3 4 5
|___|
  |___|
    |___|

ログイン後にコピー

答えは、配列をスライドさせているにもかかわらず、各反復で、前の反復ですでに計算された k-1 個の要素を「再計算」する必要があるということです。

基本的に、この洞察は次のような質問をすることを示唆しています。

「前のステップの計算を利用する方法はありますか?」

答えは「はい」です。ウィンドウ要素の後の最初と次を加算および減算することで、ウィンドウの要素の合計を取得できます。このアイデアをコードに取り入れてみましょう。

def foo(array: List[int] = None, size: int = 0) -> int
    window_start, max_, window_sum_ = 0, float("-inf"), 0
    for window_end in range(len(array)):
        if window_end > size - 1:
            window_sum_ -= array[window_start]
            window_start += 1
        window_sum_ += array[window_end]
        max_ = max(max_, window_sum_)
    return max_

assert foo(array=[1, 2, 3, 4], size=3) == 9

ログイン後にコピー

ここで、size の長さの部分配列を構築した時点で、ウィンドウの合計から最初の要素の減算を開始したことがわかります。これにより、前のステップの計算を再利用できるようになります。

さて、スライディングウィンドウの概念を効率的に利用し、時間計算量をチェックする証明が得られ、時間計算量が O(l*w) から O(l) に減少したと言えます。ここで、l はウィンドウの数です。スライドします。

私が強調したい主要なアイデアであるスライディングウィンドウの概念は、単に特定のサイズのウィンドウで反復可能をスライスするというものではありません。

いくつかの問題を紹介します。ここでは、スライディングウィンドウの概念に関係する可能性がある問題を検出する方法と、ウィンドウ自体を使用して正確に何を行うかを学びます。

問題の概要

ここでは単に概念について話しているので、「ウィンドウ内の何かを数える方法」については省略します。

問題 1

配列が与えられた場合、その配列内のサイズ K のすべての連続する部分配列の平均を求めます。

引き違い窓 ? - 連続部分配列が最初のキーワードです。これは、連続部分配列を表すウィンドウを処理する必要があることを意味します。
引き違い窓のサイズを知っていますか? - はい、K、ウィンドウのサイズがわかりました。これは K の長さでなければなりません。
スライディングウィンドウ内で正確に何を管理/確認する必要があるのでしょうか? - 平均を求めます...

よし、次のようにアプローチを定義しましょう。サイズ K のウィンドウで入力配列を反復処理します。各反復カウントでウィンドウの平均を計算します...

問題 2

正の数の配列と正の数 K を指定して、サイズ K の連続する部分配列の最大合計を求めます。

引き違い窓 ? - 連続部分配列、最初のキーワードです。これは、連続部分配列を表すウィンドウを処理する必要があることを意味します。
引き違い窓のサイズを知っていますか? - はい、K、ウィンドウのサイズがわかりました。これは K の長さでなければなりません。
スライディングウィンドウ内で正確に何を管理/確認する必要があるのでしょうか? - ..合計...

次に: サイズ K のウィンドウを使用して入力配列を走査します。反復ごとにウィンドウの合計がカウントされます...

問題 3

正の数の配列と正の数 S を指定して、合計が S 以上である最小の連続部分配列の長さを見つけます。

引き違い窓 ? - 連続部分配列、最初のキーワードです。これは、連続部分配列を表すウィンドウを処理する必要があることを意味します。
引き違い窓のサイズを知っていますか? - 実際にはいいえ、それを理解する必要があります。
スライディングウィンドウ内で正確に何を管理/確認する必要があるのでしょうか? - ... 合計は S に対して >= です ...

ここで、アプローチを次のように定義します。「まず、入力配列を反復処理し、条件を満たす最初のウィンドウを構築します (合計が S に対して >= である)。完了したら、ウィンドウを移動し、ウィンドウを管理します」始まりと終わり..."

問題 4

文字列が指定された場合、その中で K 個以下の異なる文字を含む最長の部分文字列の長さを見つけます。

引き違い窓 ? - 最長の部分文字列、最初のキーワード。部分文字列を表すウィンドウを処理する必要があることを意味します。
引き違い窓のサイズを知っていますか? - いいえ、それを理解する必要があります。
スライディングウィンドウ内で正確に何を管理/確認する必要があるのでしょうか? - ... 個別の文字の量 ...

ここでのアプローチはもう少し複雑なので、ここでは省略します。

問題 5

各整数が果樹を表す整数の配列が与えられた場合、2 つのバスケットが与えられ、目標は各バスケットに最大数の果物を入れることです。唯一の制限は、各バスケットに 1 種類のフルーツのみを入れることです。
どのツリーからでも開始できますが、一度開始したツリーをスキップすることはできません。各木から 1 つの果物を収穫できなくなるまで収穫します。つまり、3 番目の果物の種類から収穫する必要があるときに停止します。
両方のバスケット内の果物の最大数を返す関数を作成します。

それほど明白ではないようです。まず条件を単純化してみましょう。