ホームページ ウェブフロントエンド jsチュートリアル インタビュー キット: 配列 - スライディング ウィンドウ。

インタビュー キット: 配列 - スライディング ウィンドウ。

Sep 05, 2024 pm 05:35 PM

重要なのはパターンです!

パターンを学ぶと、すべてが少し簡単に感じ始めます。あなたも私と同じなら、おそらく技術系の面接は好きではないでしょう。私はあなたを責めません。面接は厳しいものになる可能性があります。

配列の問題は、面接で遭遇する最も一般的な問題の 1 つです。これらの問題には、多くの場合、自然配列の操作が関係します。

const arr = [1, 2, 3, 4, 5];
ログイン後にコピー

そして、本質的に文字の配列である文字列の問題:

"mylongstring".split(""); // ['m', 'y', 'l', 'o','n', 'g', 's','t','r','i', 'n', 'g']


ログイン後にコピー

配列の問題を解決するための最も一般的なパターンの 1 つは、スライディング ウィンドウです。

スライディング ウィンドウ パターン

スライディング ウィンドウ パターンには、配列内をスライドするウィンドウのように、同じ方向に移動する 2 つのポインターが含まれます。

いつ使用するか

最小値、最大値、最長値など、特定の条件を満たす サブ配列 または サブ文字列 を検索する必要がある場合は、スライディング ウィンドウ パターンを使用します。最短です。

ルール 1: サブ配列またはサブ文字列を検索する必要があり、データ構造が配列または文字列である場合は、スライディング ウィンドウ パターンの使用を検討してください。

簡単な例

スライディング ウィンドウにポインターの概念を導入する基本的な例を次に示します。

function SlidingWindow(arr) {
    let l = 0;  // Left pointer
    let r = l + 1;  // Right pointer

    while (r < arr.length) {
        console.log("left", arr[l]);
        console.log("right", arr[r]);
        l++;
        r++;
    }
}

SlidingWindow([1, 2, 3, 4, 5, 6, 7, 8]);
ログイン後にコピー

左 (L) と右 (R) ポインターは同時に移動する必要はありませんが、同じ方向に移動する必要があることに注意してください。

Interview Kit: Arrays - Sliding window.

右ポインタが左ポインタよりも低くなることはありません。

実際の面接の問題でこの概念を探ってみましょう。

現実の問題: 繰り返し文字を含まない最長の部分文字列

問題: 文字列 s を指定して、文字を繰り返さない最長の部分文字列の長さを見つけます。

キーワード: サブ-文字列、最長 (最大)

function longestSubstr(str) {
    let longest = 0;
    let left = 0;
    let hash = {};

    for (let right = 0; right < str.length; right++) {
        if (hash[str[right]] !== undefined && hash[str[right]] >= left) {
            left = hash[str[right]] + 1;
        }

        hash[str[right]] = right;
        longest = Math.max(longest, right - left + 1);
    }

    return longest;
}
ログイン後にコピー

これが複雑に見えても心配しないでください。少しずつ説明していきます。

let str = "helloworld";
console.log(longestSubstr(str));  // Output: 5
ログイン後にコピー

この問題の核心は、繰り返し文字を含まない最長の部分文字列を見つけることです。

初期ウィンドウ: サイズ 0

開始時には、左 (L) と右 (R) のポインターは両方とも同じ場所にあります。


let left = 0;

for (let right = 0; right < str.length; right++) {  // RIGHT POINTER
ログイン後にコピー
h e l l o w o r l d 
^
^
L
R
ログイン後にコピー
そして空のハッシュ (オブジェクト) があります:


let hash = {};
ログイン後にコピー
オブジェクトの何が素晴らしいのですか?これらは一意の

キーを保存しており、これがまさにこの問題を解決するために必要なものです。ハッシュを使用して、訪問したすべてのキャラクターを追跡し、現在のキャラクターを以前に見たことがあるかどうかを確認します (重複を検出するため)。

文字列を見ると、world が文字を繰り返さない最長の部分文字列であることが視覚的にわかります。


h e l l o w o r l d 
          ^        ^   
          L        R
ログイン後にコピー
これの長さは 5 です。それでは、どうやってそこに到達するのでしょうか?

段階的に見てみましょう:

初期状態

hash = {}

h e l l o w o r l d 
^
^
L
R
ログイン後にコピー
反復 1:

各反復で、R ポインタの下の文字をハッシュ マップに追加し、インクリメントします。


hash[str[right]] = right;
longest = Math.max(longest, right - left + 1);
ログイン後にコピー
ログイン後にコピー
現在、ウィンドウ内に繰り返される文字 (h と e) はありません:


hash = {h: 0}
h e l l o w o r l d 
^ ^
L R
ログイン後にコピー
反復 2:

hash = {h: 0, e: 1}
h e l l o w o r l d 
^   ^
L   R
ログイン後にコピー
今、新しいウィンドウができました:hel。

反復 3:

hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
^     ^
L     R
ログイン後にコピー
ここが興味深いところです。ハッシュにはすでに l があり、R は文字列内の別の l を指しています。ここで if ステートメントが登場します。


if (hash[str[right]] !== undefined)
ログイン後にコピー
ハッシュに R が指している文字が含まれている場合は、重複が見つかりました。前のウィンドウ (hel) はこれまでで最長です。

それでは、次に何をしましょうか?すでに左側の部分文字列を処理しているため、L ポインタを上に移動してウィンドウを左側から縮小します。しかし、L をどこまで移動すればよいでしょうか?


left = hash[str[right]] + 1;
ログイン後にコピー
L を複製の直後に移動します。


hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
      ^
      ^
      L
      R
ログイン後にコピー
引き続き重複をハッシュに追加するため、L のインデックスは 3 になります。


hash[str[right]] = right;
longest = Math.max(longest, right - left + 1);
ログイン後にコピー
ログイン後にコピー
新しい状態: 反復 4

hash = {h: 0, e: 1, l: 3}
h e l l o w o r l d 
      ^ ^
      L R
ログイン後にコピー
反復 4 ~ 6

hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
      ^     ^
      L     R
ログイン後にコピー
R が別の重複 (o) を指す場合、L を最初の o の直後に移動します。


hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
          ^ ^
          L R
ログイン後にコピー
別の重複 l:

が見つかるまで続行します。

hash = {h: 0, e: 1, l: 3, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^     ^
          L     R
ログイン後にコピー
しかし、それが現在のウィンドウの外側にあることに注意してください。 w から始まる

ルール 3: 処理されたサブ x を無視する

現在のウィンドウの外側にあるものはすべて無関係です。すでに処理されています。これを管理するためのキーコードは次のとおりです:


if (hash[str[right]] !== undefined && hash[str[right]] >= left)
ログイン後にコピー
この条件により、現在のウィンドウ内の文字のみが考慮され、ノイズが除去されます。


hash[str[right]] >= left
ログイン後にコピー
左ポインターより大きいか等しいものに焦点を当てます

最終反復:

hash = {h: 0, e: 1, l: 8, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^       ^
          L       R
ログイン後にコピー
詳しく説明しましたが、問題をより小さなパターンやルールに分割することが、問題を習得する最も簡単な方法です。

In Summary:

  • Rule 1: Keywords in the problem (e.g., maximum, minimum) are clues. This problem is about finding the longest sub-string without repeating characters.
  • Rule 2: If you need to find unique or non-repeating elements, think hash maps.
  • Rule 3: Focus on the current window—anything outside of it is irrelevant.

Bonus Tips:

  • Break down the problem and make it verbose using a small subset.
  • When maximizing the current window, think about how to make it as long as possible. Conversely, when minimizing, think about how to make it as small as possible.

To wrap things up, here's a little challenge for you to try out! I’ll post my solution in the comments—it’s a great way to practice.

Problem 2: Sum Greater Than or Equal to Target

Given an array, find the smallest subarray with a sum equal to or greater than the target(my solution will be the first comment).

/**
 * 
 * @param {Array<number>} arr 
 * @param {number} target 
 * @returns {number} - length of the smallest subarray
 */
function greaterThanOrEqualSum(arr, target){
   let minimum = Infinity;
   let left = 0;
   let sum = 0;

   // Your sliding window logic here!
}

ログイン後にコピー

Remember, like anything in programming, repetition is key! Sliding window problems pop up all the time, so don’t hesitate to Google more examples and keep practicing.

I’m keeping this one short, but stay tuned—the next article will dive into the two-pointer pattern and recursion (prepping for tree problems). It’s going to be a bit more challenging!

If you want more exclusive content, you can follow me on Twitter or Ko-fi I'll be posting some extra stuff there!

Resources:

Tech interview Handbook

leet code arrays 101

以上がインタビュー キット: 配列 - スライディング ウィンドウ。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

Python vs. JavaScript:学習曲線と使いやすさ Python vs. JavaScript:学習曲線と使いやすさ Apr 16, 2025 am 12:12 AM

Pythonは、スムーズな学習曲線と簡潔な構文を備えた初心者により適しています。 JavaScriptは、急な学習曲線と柔軟な構文を備えたフロントエンド開発に適しています。 1。Python構文は直感的で、データサイエンスやバックエンド開発に適しています。 2。JavaScriptは柔軟で、フロントエンドおよびサーバー側のプログラミングで広く使用されています。

C/CからJavaScriptへ:すべてがどのように機能するか C/CからJavaScriptへ:すべてがどのように機能するか Apr 14, 2025 am 12:05 AM

C/CからJavaScriptへのシフトには、動的なタイピング、ゴミ収集、非同期プログラミングへの適応が必要です。 1)C/Cは、手動メモリ管理を必要とする静的に型付けられた言語であり、JavaScriptは動的に型付けされ、ごみ収集が自動的に処理されます。 2)C/Cはマシンコードにコンパイルする必要がありますが、JavaScriptは解釈言語です。 3)JavaScriptは、閉鎖、プロトタイプチェーン、約束などの概念を導入します。これにより、柔軟性と非同期プログラミング機能が向上します。

JavaScriptとWeb:コア機能とユースケース JavaScriptとWeb:コア機能とユースケース Apr 18, 2025 am 12:19 AM

Web開発におけるJavaScriptの主な用途には、クライアントの相互作用、フォーム検証、非同期通信が含まれます。 1)DOM操作による動的なコンテンツの更新とユーザーインタラクション。 2)ユーザーエクスペリエンスを改善するためにデータを提出する前に、クライアントの検証が実行されます。 3)サーバーとのリフレッシュレス通信は、AJAXテクノロジーを通じて達成されます。

JavaScript in Action:実際の例とプロジェクト JavaScript in Action:実際の例とプロジェクト Apr 19, 2025 am 12:13 AM

現実世界でのJavaScriptのアプリケーションには、フロントエンドとバックエンドの開発が含まれます。 1)DOM操作とイベント処理を含むTODOリストアプリケーションを構築して、フロントエンドアプリケーションを表示します。 2)node.jsを介してRestfulapiを構築し、バックエンドアプリケーションをデモンストレーションします。

JavaScriptエンジンの理解:実装の詳細 JavaScriptエンジンの理解:実装の詳細 Apr 17, 2025 am 12:05 AM

JavaScriptエンジンが内部的にどのように機能するかを理解することは、開発者にとってより効率的なコードの作成とパフォーマンスのボトルネックと最適化戦略の理解に役立つためです。 1)エンジンのワークフローには、3つの段階が含まれます。解析、コンパイル、実行。 2)実行プロセス中、エンジンはインラインキャッシュや非表示クラスなどの動的最適化を実行します。 3)ベストプラクティスには、グローバル変数の避け、ループの最適化、constとletsの使用、閉鎖の過度の使用の回避が含まれます。

Python vs. JavaScript:コミュニティ、ライブラリ、リソース Python vs. JavaScript:コミュニティ、ライブラリ、リソース Apr 15, 2025 am 12:16 AM

PythonとJavaScriptには、コミュニティ、ライブラリ、リソースの観点から、独自の利点と短所があります。 1)Pythonコミュニティはフレンドリーで初心者に適していますが、フロントエンドの開発リソースはJavaScriptほど豊富ではありません。 2)Pythonはデータサイエンスおよび機械学習ライブラリで強力ですが、JavaScriptはフロントエンド開発ライブラリとフレームワークで優れています。 3)どちらも豊富な学習リソースを持っていますが、Pythonは公式文書から始めるのに適していますが、JavaScriptはMDNWebDocsにより優れています。選択は、プロジェクトのニーズと個人的な関心に基づいている必要があります。

Python vs. JavaScript:開発環境とツール Python vs. JavaScript:開発環境とツール Apr 26, 2025 am 12:09 AM

開発環境におけるPythonとJavaScriptの両方の選択が重要です。 1)Pythonの開発環境には、Pycharm、Jupyternotebook、Anacondaが含まれます。これらは、データサイエンスと迅速なプロトタイピングに適しています。 2)JavaScriptの開発環境には、フロントエンドおよびバックエンド開発に適したnode.js、vscode、およびwebpackが含まれます。プロジェクトのニーズに応じて適切なツールを選択すると、開発効率とプロジェクトの成功率が向上する可能性があります。

JavaScript通訳者とコンパイラにおけるC/Cの役割 JavaScript通訳者とコンパイラにおけるC/Cの役割 Apr 20, 2025 am 12:01 AM

CとCは、主に通訳者とJITコンパイラを実装するために使用されるJavaScriptエンジンで重要な役割を果たします。 1)cは、JavaScriptソースコードを解析し、抽象的な構文ツリーを生成するために使用されます。 2)Cは、Bytecodeの生成と実行を担当します。 3)Cは、JITコンパイラを実装し、実行時にホットスポットコードを最適化およびコンパイルし、JavaScriptの実行効率を大幅に改善します。

See all articles