昆山企業(yè)網(wǎng)站建設(shè)公司淘客推廣
🌟快來參與討論💬,點贊👍、收藏?、分享📤,共創(chuàng)活力社區(qū)。 🌟
別再猶豫了!快來訂閱我們的算法每日雙題精講專欄,一起踏上算法學(xué)習(xí)的精彩之旅吧!💪
今天,咱們就一同來探究 “水果成籃” 和 “找到字符串中所有字母異位詞” 這兩道經(jīng)典題目,看看滑動窗口算法是如何在其中施展魔法的🧙?♂?。
目錄
💯水果成籃
📖題目描述
🧠講解算法原理
💻代碼實現(xiàn)(以 C++ 為例)
💯找到字符串中所有字母異位詞
📖題目描述
?🧠講解算法原理
?💻代碼實現(xiàn)(以 C++ 為例)
💯水果成籃
題目鏈接👉【力扣】
📖題目描述
根據(jù)示例分析,該題的本質(zhì)就是:找出最長子數(shù)組的長度,子數(shù)組不超過倆種水果類型
🧠講解算法原理
解法一:
?我們用暴力解法寫一下,例如f=[1,2,3,2,2]
依次找出所以的情況👇
-
?
代碼中我們利用哈希表列舉情況,用哈希表統(tǒng)計水果出現(xiàn)的類型數(shù)
解法二:
先分析
?當我們用暴力解法時,遇到如下情況👇,我們讓 left++ ,right 回到 left的位置,繼續(xù)列舉情況
當left++時,區(qū)間的?kinds 要么不變,要么減少一個
- 當kinds不變時,right沒有必要改變
- 當kinds減少時,right可以繼續(xù)向后移動
?因此我們可以用滑動窗口的解法,right不回退嘛
滑動窗口四大步:
- ?left=0,right=0
- 進窗口——right右移動的時候
- 判斷? ? 出窗口——就是left右移動的時候
- 更新結(jié)果
舉例: f=[1,2,1,2,3,2,3,3]
每次遍歷right,讓其放入hash表里面,判斷有沒有超出類型個數(shù)
當hash.length>2時出窗口
left右移動的時候,要根據(jù)某個水果種類的數(shù)量來進行移動,因此我們創(chuàng)建的hash表要有倆個參數(shù),一個記錄種類,一個記錄個數(shù)
例如下面👇,我們要將left移動到3的前面
💻代碼實現(xiàn)(以 C++ 為例)
class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001]={0};//統(tǒng)計窗口內(nèi)出現(xiàn)了多少種結(jié)果int ret=0;for(int left=0,right=0,kinds=0;right<fruits.size();right++){if(hash[fruits[right]]==0) kinds++;hash[fruits[right]]++;//進窗口while(kinds>2)//判斷{//出窗口hash[fruits[left]]--;if(hash[fruits[left]]==0) kinds--;left++;}ret=max(ret,right-left+1);}return ret;}
};
💯找到字符串中所有字母異位詞
題目鏈接👉【力扣】
📖題目描述
?
?🧠講解算法原理
1.如何判斷倆個字符串是否是異位詞?
- 可以先排序再比較,但是時間復(fù)雜度為nlogn ,比較大
- 通過統(tǒng)計字符串中字符出現(xiàn)的個數(shù)也可以判斷,借助hash表即可
?2.解決問題
例如
暴力解法:?
計入p的長度m ,在S里依次比較?
?
優(yōu)化解法:
當字符串依次遍歷時,?,我們發(fā)現(xiàn)ba重復(fù)出現(xiàn),所以我們只要將c從hash表移除,讓e加入hash表即可,滑動窗口
?
滑動窗口四大步:
- ?left=0,right=0
- 進窗口——right右移動的時候
- 判斷? ? 出窗口——就是left右移動的時候
- 更新結(jié)果
?
3.優(yōu)化:更新結(jié)果的判斷條件
利用變量count來統(tǒng)計窗口中“有效字符”的個數(shù)
使用一個數(shù)組
targetCount
來記錄字符串p
中每個字母的出現(xiàn)次數(shù),再使用一個數(shù)組windowCount
來記錄當前窗口內(nèi)每個字母的出現(xiàn)次數(shù)。設(shè)一個變量valid
來表示窗口內(nèi)有效字母的數(shù)量,初始值為0
。?然后,將
?right
指針向右移動,每移動一次,就將新字母在windowCount
中的計數(shù)加1
,并檢查該字母的計數(shù)是否等于在targetCount
中的計數(shù),如果相等,則valid
加1
。當valid
等于p
中不同字母的數(shù)量時,說明當前窗口是一個字母異位詞。此時,將
?left
指針向右移動,同時更新windowCount
和valid
,直到valid
小于p
中不同字母的數(shù)量。在移動left
指針的過程中,如果窗口內(nèi)的子串長度等于p
的長度,就將left
指針的索引加入到結(jié)果數(shù)組中。重復(fù)上述步驟,直到
right
指針走到字符串s
的末尾。最后,返回結(jié)果數(shù)組。
?💻代碼實現(xiàn)(以 C++ 為例)
class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> result;// 如果s的長度小于p的長度,直接返回空結(jié)果if (s.length() < p.length()) return result;// 用于記錄字符串p中每個字母的出現(xiàn)次數(shù)vector<int> targetCount(26, 0);// 用于記錄當前窗口內(nèi)每個字母的出現(xiàn)次數(shù)vector<int> windowCount(26, 0);int valid = 0;// 初始化targetCount數(shù)組for (char c : p) {targetCount[c - 'a']++;}int left = 0, right = 0;while (right < s.length()) {int rightIndex = s[right] - 'a';// 將新字母在windowCount中的計數(shù)加1windowCount[rightIndex]++;// 如果該字母的計數(shù)小于等于在targetCount中的計數(shù),說明該字母在窗口內(nèi)的數(shù)量還未超過p中該字母的數(shù)量,有效字母數(shù)量加1if (windowCount[rightIndex] <= targetCount[rightIndex]) {valid++;}// 當窗口大小大于p的長度時,移動left指針縮小窗口while (right - left + 1 > p.length()) {int leftIndex = s[left] - 'a';// 將left指針指向的字母在windowCount中的計數(shù)減1windowCount[leftIndex]--;// 如果該字母的計數(shù)小于在targetCount中的計數(shù),說明該字母在窗口內(nèi)的數(shù)量已經(jīng)小于p中該字母的數(shù)量,有效字母數(shù)量減1if (windowCount[leftIndex] < targetCount[leftIndex]) {valid--;}left++;}// 如果有效字母數(shù)量等于p中不同字母的數(shù)量,說明當前窗口是一個字母異位詞,將left指針的索引加入結(jié)果數(shù)組if (valid == p.length()) {result.push_back(left);}right++;}return result;}
};
我以后還會對 算法 相關(guān)知識進行更多的創(chuàng)作,歡迎大家關(guān)注我,一起探索 算法 的奇妙世界😜
👉【A Charmer】