インタビュー キット: 配列 - スライディング ウィンドウ。
重要なのはパターンです!
パターンを学ぶと、すべてが少し簡単に感じ始めます。あなたも私と同じなら、おそらく技術系の面接は好きではないでしょう。私はあなたを責めません。面接は厳しいものになる可能性があります。
配列の問題は、面接で遭遇する最も一般的な問題の 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) ポインターは同時に移動する必要はありませんが、同じ方向に移動する必要があることに注意してください。
右ポインタが左ポインタよりも低くなることはありません。
実際の面接の問題でこの概念を探ってみましょう。
現実の問題: 繰り返し文字を含まない最長の部分文字列
問題: 文字列 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
段階的に見てみましょう:
初期状態
hash = {} h e l l o w o r l d ^ ^ L R
各反復で、R ポインタの下の文字をハッシュ マップに追加し、インクリメントします。
hash[str[right]] = right; longest = Math.max(longest, right - left + 1);
hash = {h: 0} h e l l o w o r l d ^ ^ L R
hash = {h: 0, e: 1} h e l l o w o r l d ^ ^ L R
反復 3:
hash = {h: 0, e: 1, l: 2} h e l l o w o r l d ^ ^ L R
if (hash[str[right]] !== undefined)
それでは、次に何をしましょうか?すでに左側の部分文字列を処理しているため、L ポインタを上に移動してウィンドウを左側から縮小します。しかし、L をどこまで移動すればよいでしょうか?
left = hash[str[right]] + 1;
hash = {h: 0, e: 1, l: 2} h e l l o w o r l d ^ ^ L R
hash[str[right]] = right; longest = Math.max(longest, right - left + 1);
hash = {h: 0, e: 1, l: 3} h e l l o w o r l d ^ ^ L R
hash = {h: 0, e: 1, l: 3, o: 4, w: 5} h e l l o w o r l d ^ ^ L R
hash = {h: 0, e: 1, l: 3, o: 4, w: 5} h e l l o w o r l d ^ ^ L R
が見つかるまで続行します。
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
ルール 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 サイトの他の関連記事を参照してください。

ホットAIツール

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

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

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

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

人気の記事

ホットツール

メモ帳++7.3.1
使いやすく無料のコードエディター

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

ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境

ドリームウィーバー CS6
ビジュアル Web 開発ツール

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

ホットトピック











フロントエンドのサーマルペーパーチケット印刷のためのよくある質問とソリューションフロントエンド開発におけるチケット印刷は、一般的な要件です。しかし、多くの開発者が実装しています...

JavaScriptは現代のWeb開発の基礎であり、その主な機能には、イベント駆動型のプログラミング、動的コンテンツ生成、非同期プログラミングが含まれます。 1)イベント駆動型プログラミングにより、Webページはユーザー操作に応じて動的に変更できます。 2)動的コンテンツ生成により、条件に応じてページコンテンツを調整できます。 3)非同期プログラミングにより、ユーザーインターフェイスがブロックされないようにします。 JavaScriptは、Webインタラクション、シングルページアプリケーション、サーバー側の開発で広く使用されており、ユーザーエクスペリエンスとクロスプラットフォーム開発の柔軟性を大幅に改善しています。

スキルや業界のニーズに応じて、PythonおよびJavaScript開発者には絶対的な給与はありません。 1. Pythonは、データサイエンスと機械学習でさらに支払われる場合があります。 2。JavaScriptは、フロントエンドとフルスタックの開発に大きな需要があり、その給与もかなりです。 3。影響要因には、経験、地理的位置、会社の規模、特定のスキルが含まれます。

この記事の視差スクロールと要素のアニメーション効果の実現に関する議論では、Shiseidoの公式ウェブサイト(https://www.shisido.co.co.jp/sb/wonderland/)と同様の達成方法について説明します。

JavaScriptを学ぶことは難しくありませんが、挑戦的です。 1)変数、データ型、関数などの基本概念を理解します。2)非同期プログラミングをマスターし、イベントループを通じて実装します。 3)DOM操作を使用し、非同期リクエストを処理することを約束します。 4)一般的な間違いを避け、デバッグテクニックを使用します。 5)パフォーマンスを最適化し、ベストプラクティスに従ってください。

JavaScriptの最新トレンドには、TypeScriptの台頭、最新のフレームワークとライブラリの人気、WebAssemblyの適用が含まれます。将来の見通しは、より強力なタイプシステム、サーバー側のJavaScriptの開発、人工知能と機械学習の拡大、およびIoTおよびEDGEコンピューティングの可能性をカバーしています。

同じIDを持つ配列要素をJavaScriptの1つのオブジェクトにマージする方法は?データを処理するとき、私たちはしばしば同じIDを持つ必要性に遭遇します...

フロントエンドのVSCodeと同様に、パネルドラッグアンドドロップ調整機能の実装を調べます。フロントエンド開発では、VSCODEと同様のVSCODEを実装する方法...
