一切都與模式有關!
一旦你學會了這些模式,一切都開始變得更容易了!如果你像我一樣,你可能不喜歡技術面試,我不怪你——面試可能很艱難。
陣列問題是面試中最常見的問題。這些問題通常涉及使用自然數組:
const arr = [1, 2, 3, 4, 5];
還有字串問題,本質上是字元陣列:
"mylongstring".split(""); // ['m', 'y', 'l', 'o','n', 'g', 's','t','r','i', 'n', 'g']
解決陣列問題最常見的模式之一是滑動視窗。
滑動視窗模式
滑動視窗模式涉及兩個沿同一方向移動的指針,就像在數組上滑動的視窗一樣。
何時使用它
當您需要尋找符合特定條件(例如最小值、最大值、最長或)的子陣列或子字串時,請使用滑動視窗模式最短。
規則1:如果需要尋找子陣列或子字串,且資料結構是陣列或字串,請考慮使用滑動視窗模式。
簡單的例子
這是一個介紹滑動視窗中指標概念的基本範例:
function SlidingWindow(arr) { let l = 0; // Left pointer let r = l + 1; // Right pointer while (r <p>請注意,左(L)和右(R)指針不必同時移動,但必須朝同一方向移動。 </p> <p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/172552892845227.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Interview Kit: Arrays - Sliding window."></p> <p>右指針永遠不會低於左指針。 </p> <p>讓我們透過一個真實的面試問題來探索這個概念。 </p> <h3> 現實問題:不重複字元最長的子字串 </h3> <p><strong>問題:</strong>給定一個字串 s,找出不包含重複字元的最長子字串的長度。 </p> <p><strong>關鍵字:</strong> <em>子</em>-字串,最長(最大)<br> </p> <pre class="brush:php;toolbar:false">function longestSubstr(str) { let longest = 0; let left = 0; let hash = {}; for (let right = 0; 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 <pre class="brush:php;toolbar:false">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! } </number>
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中文網其他相關文章!

JavaScript是現代網站的核心,因為它增強了網頁的交互性和動態性。 1)它允許在不刷新頁面的情況下改變內容,2)通過DOMAPI操作網頁,3)支持複雜的交互效果如動畫和拖放,4)優化性能和最佳實踐提高用戶體驗。

C 和JavaScript通過WebAssembly實現互操作性。 1)C 代碼編譯成WebAssembly模塊,引入到JavaScript環境中,增強計算能力。 2)在遊戲開發中,C 處理物理引擎和圖形渲染,JavaScript負責遊戲邏輯和用戶界面。

JavaScript在網站、移動應用、桌面應用和服務器端編程中均有廣泛應用。 1)在網站開發中,JavaScript與HTML、CSS一起操作DOM,實現動態效果,並支持如jQuery、React等框架。 2)通過ReactNative和Ionic,JavaScript用於開發跨平台移動應用。 3)Electron框架使JavaScript能構建桌面應用。 4)Node.js讓JavaScript在服務器端運行,支持高並發請求。

Python更適合數據科學和自動化,JavaScript更適合前端和全棧開發。 1.Python在數據科學和機器學習中表現出色,使用NumPy、Pandas等庫進行數據處理和建模。 2.Python在自動化和腳本編寫方面簡潔高效。 3.JavaScript在前端開發中不可或缺,用於構建動態網頁和單頁面應用。 4.JavaScript通過Node.js在後端開發中發揮作用,支持全棧開發。

C和C 在JavaScript引擎中扮演了至关重要的角色,主要用于实现解释器和JIT编译器。1)C 用于解析JavaScript源码并生成抽象语法树。2)C 负责生成和执行字节码。3)C 实现JIT编译器,在运行时优化和编译热点代码,显著提高JavaScript的执行效率。

JavaScript在現實世界中的應用包括前端和後端開發。 1)通過構建TODO列表應用展示前端應用,涉及DOM操作和事件處理。 2)通過Node.js和Express構建RESTfulAPI展示後端應用。

JavaScript在Web開發中的主要用途包括客戶端交互、表單驗證和異步通信。 1)通過DOM操作實現動態內容更新和用戶交互;2)在用戶提交數據前進行客戶端驗證,提高用戶體驗;3)通過AJAX技術實現與服務器的無刷新通信。

理解JavaScript引擎內部工作原理對開發者重要,因為它能幫助編寫更高效的代碼並理解性能瓶頸和優化策略。 1)引擎的工作流程包括解析、編譯和執行三個階段;2)執行過程中,引擎會進行動態優化,如內聯緩存和隱藏類;3)最佳實踐包括避免全局變量、優化循環、使用const和let,以及避免過度使用閉包。


熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

SecLists
SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合,這些清單在安全評估過程中經常使用,而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表,幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上,他就可以存取所需的每種類型的清單。

Dreamweaver CS6
視覺化網頁開發工具

DVWA
Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序,非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具,幫助Web開發人員更好地理解保護網路應用程式的過程,並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞,難度各不相同。請注意,該軟體中

SublimeText3 英文版
推薦:為Win版本,支援程式碼提示!

EditPlus 中文破解版
體積小,語法高亮,不支援程式碼提示功能