209.長(zhǎng)度最小的子數(shù)組
209.長(zhǎng)度最小的子數(shù)組
題目
給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 。
找出該數(shù)組中滿足其和 ≥ target 的長(zhǎng)度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其長(zhǎng)度。如果不存在符合條件的子數(shù)組，返回 0 。
輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長(zhǎng)度最小的子數(shù)組。
輸入：target = 4, nums = [1,4,4]
輸出：1
輸入：target = 11, nums = [1,1,1,1,1,1,1,1]
輸出：0
代碼
class Solution(object):
def minSubArrayLen(self, target, nums):
"""
:type target: int
:type nums: List[int]
:rtype: int
"""
res=float("inf")# 定義一個(gè)無限大的數(shù)
Sum=0
i=0
for j in range(len(nums)):
Sum+=nums[j]
while Sum>=target:
res=min(res, j-i+1)
Sum-=nums[i]
i+=1
if res == float("inf"):
return 0
else:
return res
#return 0 if res == float("inf") else res
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0; // 滑動(dòng)窗口數(shù)值之和
int i = 0; // 滑動(dòng)窗口起始位置
int subLength = 0; // 滑動(dòng)窗口的長(zhǎng)度
for (int j = 0; j < nums.size(); j++) {
sum += nums[j];
// 注意這里使用while，每次更新 i（起始位置），并不斷比較子序列是否符合條件
while (sum >= s) {
subLength = (j - i + 1); // 取子序列的長(zhǎng)度
result = result < subLength ? result : subLength;
sum -= nums[i++]; // 這里體現(xiàn)出滑動(dòng)窗口的精髓之處，不斷變更i（子序列的起始位置）
}
}
// 如果result沒有被賦值的話，就返回0，說明沒有符合條件的子序列
return result == INT32_MAX ? 0 : result;
}
};
總結(jié)
- 滑動(dòng)窗口
- 雙指針，前半部分的計(jì)算結(jié)果可以繼續(xù)使用Sum-=nums[i]
904. 水果成籃
904. 水果成籃
題目
你正在探訪一家農(nóng)場(chǎng)，農(nóng)場(chǎng)從左到右種植了一排果樹。這些樹用一個(gè)整數(shù)數(shù)組 fruits 表示，其中 fruits[i] 是第 i 棵樹上的水果 種類 。
你想要盡可能多地收集水果。然而，農(nóng)場(chǎng)的主人設(shè)定了一些嚴(yán)格的規(guī)矩，你必須按照要求采摘水果：
- 你只有 兩個(gè) 籃子，并且每個(gè)籃子只能裝 單一類型 的水果。每個(gè)籃子能夠裝的水果總量沒有限制。
- 你可以選擇任意一棵樹開始采摘，你必須從 每棵 樹（包括開始采摘的樹）上 恰好摘一個(gè)水果 。采摘的水果應(yīng)當(dāng)符合籃子中的水果類型。每采摘一次，你將會(huì)向右移動(dòng)到下一棵樹，并繼續(xù)采摘。
- 一旦你走到某棵樹前，但水果不符合籃子的水果類型，那么就必須停止采摘。
給你一個(gè)整數(shù)數(shù)組 fruits ，返回你可以收集的水果的 最大 數(shù)目。
輸入：fruits = [1,2,1]
輸出：3
解釋：可以采摘全部 3 棵樹。
輸入：fruits = [0,1,2,2]
輸出：3
解釋：可以采摘 [1,2,2] 這三棵樹。
如果從第一棵樹開始采摘，則只能采摘 [0,1] 這兩棵樹。
輸入：fruits = [1,2,3,2,2]
輸出：4
解釋：可以采摘 [2,3,2,2] 這四棵樹。
如果從第一棵樹開始采摘，則只能采摘 [1,2] 這兩棵樹。
輸入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
輸出：5
解釋：可以采摘 [1,2,1,1,2] 這五棵樹。
代碼
class Solution(object):
def totalFruit(self, fruits):
"""
:type fruits: List[int]
:rtype: int
"""
ans=0
i=0
cnt = Counter() #Counter類統(tǒng)計(jì)出現(xiàn)次數(shù)，實(shí)現(xiàn)哈希表
for j,x in enumerate(fruits): # 同時(shí)遍歷得到數(shù)值
cnt[x]+=1 #哈希表
while len(cnt)>2:
cnt[fruits[i]]-=1
if cnt[fruits[i]]==0:
cnt.pop(fruits[i])
i+=1
ans=max(ans,j-i+1)
return ans
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int n = fruits.size();
unordered_map<int, int> cnt;
int left = 0, ans = 0;
for (int right = 0; right < n; ++right) {
++cnt[fruits[right]];
while (cnt.size() > 2) {
auto it = cnt.find(fruits[left]);
--it->second;
if (it->second == 0) {
cnt.erase(it);
}
++left;
}
ans = max(ans, right - left + 1);
}
return ans;
}
};
總結(jié)
- cnt = Counter() #Counter類統(tǒng)計(jì)出現(xiàn)次數(shù)，實(shí)現(xiàn)哈希表
- cnt[x]+=1 #哈希表
- C++中，unordered_map是一個(gè)將key和value關(guān)聯(lián)起來的容器，它可以高效的根據(jù)單個(gè)key值查找對(duì)應(yīng)的value
76. 最小覆蓋子串
題目
給你一個(gè)字符串 s 、一個(gè)字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 “” 。
對(duì)于 t 中重復(fù)字符，我們尋找的子字符串中該字符數(shù)量必須不少于 t 中該字符數(shù)量。
如果 s 中存在這樣的子串，我們保證它是唯一的答案。
輸入：s = “ADOBECODEBANC”, t = “ABC”
輸出：“BANC”
解釋：最小覆蓋子串 “BANC” 包含來自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
輸入：s = “a”, t = “a”
輸出：“a”
解釋：整個(gè)字符串 s 是最小覆蓋子串。
輸入: s = “a”, t = “aa”
輸出: “”
解釋: t 中兩個(gè)字符 ‘a(chǎn)’ 均應(yīng)包含在 s 的子串中，
因此沒有符合條件的子字符串，返回空字符串。
代碼
class Solution(object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
need=Counter() #need=collections.defaultdict(int)
for c in t:
need[c]+=1
needCnt=len(t)
i=0
res=(0,float('inf'))
for j,c in enumerate(s):
if need[c]>0:
needCnt-=1
need[c]-=1
if needCnt==0: #滑動(dòng)窗口包含了所有T元素
while True: #增加i，排除多余元素
c=s[i]
if need[c]==0:
break
need[c]+=1
i+=1
if j-i<res[1]-res[0]: #記錄結(jié)果
res=(i,j)
need[s[i]]+=1 #i增加一個(gè)位置，尋找新的滿足條件滑動(dòng)窗口
needCnt+=1
i+=1
return '' if res[1]>len(s) else s[res[0]:res[1]+1] #如果res始終沒被更新過，代表無滿足條件的結(jié)果
class Solution {
public:
string minWindow(string s, string t) {
vector<int> need(128,0);
int count = 0;
for(char c : t)
{
need[c]++;
}
count = t.length();
int l=0, r=0, start=0, size = INT_MAX;
while(r<s.length())
{
char c = s[r];
if(need[c]>0)
count--;
need[c]--; //先把右邊的字符加入窗口
if(count==0) //窗口中已經(jīng)包含所需的全部字符
{
while(l<r && need[s[l]]<0) //縮減窗口
{
need[s[l++]]++;
} //此時(shí)窗口符合要求
if(r-l+1 < size) //更新答案
{
size = r-l+1;
start = l;
}
need[s[l]]++; //左邊界右移之前需要釋放need[s[l]]
l++;
count++;
}
r++;
}
return size==INT_MAX ? "" : s.substr(start, size);
}
};
總結(jié)
-
如何判斷滑動(dòng)窗口包含了T的所有元素？
我們用一個(gè)字典need來表示當(dāng)前滑動(dòng)窗口中需要的各元素的數(shù)量，一開始滑動(dòng)窗口為空，用T中各元素來初始化這個(gè)need，當(dāng)滑動(dòng)窗口擴(kuò)展或者收縮的時(shí)候，去維護(hù)這個(gè)need字典，例如當(dāng)滑動(dòng)窗口包含某個(gè)元素，我們就讓need中這個(gè)元素的數(shù)量減1，代表所需元素減少了1個(gè)；當(dāng)滑動(dòng)窗口移除某個(gè)元素，就讓need中這個(gè)元素的數(shù)量加1。
need始終記錄著當(dāng)前滑動(dòng)窗口下，我們還需要的元素?cái)?shù)量，我們?cè)诟淖僫,j時(shí)，需同步維護(hù)need。 -
優(yōu)化
維護(hù)一個(gè)額外的變量needCnt來記錄所需元素的總數(shù)量，碰到一個(gè)所需元素c，need[c]的數(shù)量減少1，needCnt也要減少1，這樣我們通過needCnt就可以知道是否滿足條件，而無需遍歷字典了。文章來源：http://www.zghlxwxcb.cn/news/detail-401675.html -
定義數(shù)組res=(0,float(‘inf’))文章來源地址http://www.zghlxwxcb.cn/news/detail-401675.html
到了這里，關(guān)于【Leetcode刷題-Python/C++】長(zhǎng)度最小的子數(shù)組（滑動(dòng)窗口）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
