平面設(shè)計(jì)圖網(wǎng)站有哪些?,wordpress_主題教程,臺(tái)州建設(shè)網(wǎng)站,免費(fèi)php網(wǎng)站模板場景翻譯#xff1a; 題目說#xff1a;你有兩個(gè)籃子#xff0c;每個(gè)籃子只能裝一種水果。你從任意一棵樹開始往右走#xff0c;每棵樹摘一個(gè)#xff0c;一旦遇到第三種水果#xff0c;你就不能摘了#xff08;因?yàn)榛@子裝不下了#xff09;#xff0c;采摘結(jié)束。 人話…場景翻譯題目說你有兩個(gè)籃子每個(gè)籃子只能裝一種水果。你從任意一棵樹開始往右走每棵樹摘一個(gè)一旦遇到第三種水果你就不能摘了因?yàn)榛@子裝不下了采摘結(jié)束。人話翻譯給定一個(gè)數(shù)組fruits請你找到最長的連續(xù)子數(shù)組使得這個(gè)子數(shù)組中至多包含 2 種不同的元素。例子fruits [1, 2, 3, 2, 2][1, 2]有 1 和 2 兩種。長度 2。遇到 3變成[1, 2, 3]三種了不行。必須扔掉前面的 1窗口變成[2, 3]。遇到 2[2, 3, 2]還是 2 和 3 兩種可以長度 3。遇到 2[2, 3, 2, 2]還是 2 和 3 兩種可以長度 4。最終答案4。力扣 904. 水果成籃https://leetcode.cn/problems/fruit-into-baskets/題目分析輸入整數(shù)數(shù)組fruits。目標(biāo)找到包含不超過 2 種元素的最長子數(shù)組長度。輸出最大長度。核心思維Map 計(jì)數(shù)器 滑動(dòng)窗口我們需要一個(gè)哈希表 (Map)來充當(dāng)“籃子”的角色。Key水果的種類 ID。Value該種類在當(dāng)前窗口內(nèi)的數(shù)量。操作邏輯進(jìn)窗口 (right)把水果加入 Map計(jì)數(shù) 1。檢查籃子 (Map.size)如果Map.size 2說明窗口里有 3 種水果了超載了出窗口 (left)開始收縮左邊界把fruits[left]從 Map 里減 1。關(guān)鍵點(diǎn)如果減完之后某個(gè)水果的數(shù)量變成了0必須把它從 Map 里delete掉只有當(dāng)Map.size重新回到 2或更少時(shí)while循環(huán)才能停止。更新答案每次窗口合法時(shí)更新maxLen。代碼實(shí)現(xiàn) (JavaScript)JavaScript/** * param {number[]} fruits * return {number} */ var totalFruit function(fruits) { let left 0; let maxLen 0; // 籃子記錄當(dāng)前窗口中每種水果的數(shù)量 // key: 水果ID, value: 數(shù)量 const basket new Map(); for (let right 0; right fruits.length; right) { // 1. 進(jìn)窗口把右邊的水果放進(jìn)籃子 const rightFruit fruits[right]; basket.set(rightFruit, (basket.get(rightFruit) || 0) 1); // 2. 檢查如果籃子里的種類超過 2 種必須收縮左邊界 while (basket.size 2) { const leftFruit fruits[left]; // 把左邊的水果拿出去 basket.set(leftFruit, basket.get(leftFruit) - 1); // 核心細(xì)節(jié)如果這種水果的數(shù)量減為 0 了必須徹底從 Map 中刪除 // 否則 Map.size 還是 3循環(huán)不會(huì)停邏輯就錯(cuò)了 if (basket.get(leftFruit) 0) { basket.delete(leftFruit); } // 左指針前移 left; } // 3. 此時(shí)籃子里一定 2 種更新最大長度 maxLen Math.max(maxLen, right - left 1); } return maxLen; };深度辨析為什么必須delete假設(shè)窗口是[1, 2, 3]Map 是{1:1, 2:1, 3:1}(Size3)。 如果不deleteleft移出 1。Map 變成{1:0, 2:1, 3:1}。Map.size 依然是 3(因?yàn)?key1還在只是值為 0)。while循環(huán)會(huì)繼續(xù)執(zhí)行繼續(xù)移出 2... 直到把籃子空到只剩兩種 Key 為止。這會(huì)導(dǎo)致窗口縮得過小甚至邏輯死循環(huán)。所以“數(shù)量歸零 徹底移除”是這道題的邏輯核心。總結(jié)這道題是“至多包含 K 個(gè)不同字符的最長子串”問題的標(biāo)準(zhǔn)模板本題 K2。 如果你以后遇到求“至多 K 個(gè)”的題目直接把代碼里的basket.size 2改成basket.size K即可直接秒殺。下一題預(yù)告最小覆蓋子串好了簡單的滑動(dòng)窗口結(jié)束了。我們要迎來雙指針專題的終極 BOSS——LC 76. 最小覆蓋子串(Hard)。之前的題都是窗口**“太胖了”**超標(biāo)了才收縮。這道題正好相反窗口**“太瘦了”還沒湊齊目標(biāo)字符就要擴(kuò)張一旦“吃飽了”湊齊了就要開始拼命收縮**試圖找到一個(gè)最短的、能滿足要求的窗口。這就好比你要去超市買齊清單上的[A, B, C]三樣?xùn)|西。你一直往前走直到購物車?yán)餃慅R了這三樣可能還有多余的 D, E。然后你嘗試從購物車底部拿走一些東西看看能不能在保持 A, B, C 依然齊全的情況下讓付錢的東西最少。準(zhǔn)備好挑戰(zhàn)這道 Hard 題了嗎這將是你滑動(dòng)窗口的畢業(yè)考試