文章目录
关于滑窗
滑窗是通过两个指针(数组下标)维护的。
3. 无重复字符的最长子串
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
请注意,你的答案必须是 子串 的长度,子序列不是子串。
思路:滑窗范围[pl, pr),用cnt数组维护滑窗内的每个字符的出现次数(实际上,不是1就是0),对于即将进入滑窗中的字符s[pr],如果滑窗中已经出现过了,那么pl右移缩小滑窗范围,使得s[pr]加入滑窗之后,s[pr]的出现次数仍为1,不会超出即可。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int cnt[130] = {0};
int pl = 0, pr = 0, maxlen = 0, n = s.length();
while (pr < n) {
if (cnt[s[pr]] == 0) {
cnt[s[pr]]++;
pr++;
} else {
do {
cnt[s[pl]]--;
pl++;
} while (s[pr] != s[pl - 1]);
}
if (maxlen < pr - pl)
maxlen = pr - pl;
}
return maxlen;
}
};
438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
思路:滑窗范围是[i, j),对于每个即将加入滑窗的字符s[j],看一下滑窗中该字符的个数(用cnts数组来维护),如果已经满了,那么滑窗左侧就要往右移动(缩小范围)了。
class Solution {
int cntp[130], cnts[130];
vector<int> ans;
public:
vector<int> findAnagrams(string s, string p) {
int i = 0, j = 0, ns = s.length(), np = p.length();
// 计算出p的每个字符的个数
for (auto ch : p)
cntp[ch]++;
while (j <= ns) {
if (cnts[s[j]] == cntp[s[j]]) // 满了
{
if (j - i == np)
ans.push_back(i);
while (s[i] != s[j]) {
cnts[s[i]]--;
i++;
}
cnts[s[i]]--;
i++;
}
cnts[s[j]]++;
j++;
}
return ans;
}
};
567. 字符串的排列
这道题和438一模一样。
class Solution {
int cnt2[130] = {0}, cnt1[130] = {0};
public:
bool checkInclusion(string s2, string s1)
{
s1 += " ";
for (auto ch : s2)
cnt2[ch]++;
int pl = 0, pr = 0, n1 = s1.length(), n2 = s2.length();
while (pr <= n1)
{
cnt1[s1[pr]]++;
if (cnt1[s1[pr]] > cnt2[s1[pr]])
{
if (pr - pl == n2) return true;
// pl右移
while (cnt1[s1[pr]] > cnt2[s1[pr]])
{
cnt1[s1[pl]]--;
pl++;
}
}
pr++;
}
return false;
}
};
76. 最小覆盖子串
76题跟前面几道题有不同。
class Solution {
int cnts[130] = {0}, cntt[130] = {0};
int pl = 0, pr = 0;
bool hasFindAns = false;
bool check()
{
for (char c = 'A'; c <= 'z'; c++)
if (cnts[c] < cntt[c]) return false;
return true;
}
public:
string minWindow(string s, string t)
{
int ns = s.length(), nt = t.length();
int lo = 0, hi = 0; //答案
for (auto ch : t)
cntt[ch]++;
//滑窗范围左开右闭
while (pr < ns)
{
cnts[s[pr]]++;
pr++;
while (pl < pr && cnts[s[pl]] > cntt[s[pl]])
{
cnts[s[pl]]--;
pl++;
}
if (check())
{
if (!hasFindAns || pr - pl <= hi - lo)
{
lo = pl;
hi = pr;
hasFindAns = true;
}
}
}
return s.substr(lo, hi-lo);
}
};
239. 滑动窗口最大值
虽然题名叫“滑动窗口”,但解法不是上面的滑动窗口。
方法一:优先队列+延迟删除 O(nlogn)
struct p{
int n;
int i;
bool operator < (const p & a) const{
return n < a.n;
}
};
class Solution {
priority_queue<p> pq;
vector<int> ans;
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if (nums.size()< k) return ans;
for (int i=0; i<k-1; i++)
pq.push(p{nums[i], i});
for (int i=k-1 ;i<nums.size(); i++)
{
pq.push(p{nums[i], i});
while (pq.top().i <= i - k)
pq.pop();
ans.push_back(pq.top().n);
}
return ans;
}
};
方法二:单调队列 O(n)
因为STL的queue不能从末尾删除元素,所以自己写一个queue
struct p {
int n, i;
};
template <typename T> struct myQueue {
T q[100010];
int head = 0, tail = 0;
bool empty() { return head == tail; }
T back() { return q[tail - 1]; }
void pop_back() { tail--; }
void pop() { head++; }
T front() { return q[head]; }
void push(T elem) { q[tail++] = elem; }
};
class Solution {
myQueue<p> q;
vector<int> ans;
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if (nums.size() < k)
return ans;
for (int i = 0; i < nums.size(); i++) {
while (!q.empty() && q.back().n <= nums[i])
q.pop_back();
q.push(p{nums[i], i});
if (q.front().i <= i - k)
q.pop();
if (i > k - 2)
ans.push_back(q.front().n);
}
return ans;
}
};