做图网站有哪些内容,八年级信息上册如何做网站,网站快速收录,.net网站开发过程目录
1 560. 和为 K 的子数组
2 239. 滑动窗口最大值
3 76. 最小覆盖子串 菜鸟做题第二周#xff0c;语言是 C 1 560. 和为 K 的子数组
题眼#xff1a;“子数组是数组中元素的连续非空序列。”
解决本问题的关键就在于如何翻译问题。子数组 s 的和可以看作数组 i 的…目录
1 560. 和为 K 的子数组
2 239. 滑动窗口最大值
3 76. 最小覆盖子串 菜鸟做题第二周语言是 C 1 560. 和为 K 的子数组
题眼“子数组是数组中元素的连续非空序列。”
解决本问题的关键就在于如何翻译问题。子数组 s 的和可以看作数组 i 的和减去数组 j 的和这样就把 “求子数组的和” 转换为了 “前缀和之间的差”。如下图所示 解题思路
遍历数组计算所有前缀和 sum(i)并存入哈希表中同时查看哈希表中是否存在前缀和 sum(j) 等于 sum(i) - k
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint, int hash;int pre 0, ans 0;for (auto num:nums) {pre num;if (pre k) ans;if (hash.find(pre - k) ! hash.end()) {ans hash[pre - k];}hash[pre];}return ans;}
};
说明这句代码是为了避免遗漏本身前缀和就等于 k 的情况
if (pre k) ans; 官方题解一开始就给哈希表插入了 (0, 1)应该就是为了解决这个问题但我没有照做。 2 239. 滑动窗口最大值
主要看你会不会优先队列。。。
解题思路
初始化插入前 k 个数字队列头就是最大值一格一格地右移窗口并弹出队列头若队列头的下标处在窗口内则它就是窗口内的最大值若队列头的下标处在窗口外则继续弹出直到处在窗口内
class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {int n nums.size();priority_queuepairint, int q;for (int i 0; i k; i) {q.emplace(nums[i], i);}vectorint ans {q.top().first};for (int i k; i n; i) {q.emplace(nums[i], i);while (q.top().second i - k) {q.pop();}ans.push_back(q.top().first);}return ans;}
}; 3 76. 最小覆盖子串
读懂题意很重要。。。
题目只要求当前窗口内的字母能够拼出字符串 t 即可没有要求字母数量要一致。因此判断能否覆盖的方法如下
bool succeed() {for (auto t:tCount) {if (sCount[t.first] t.second) {return false;}}return true;
}
其中tCount 和 sCount 均为哈希表。tCount 记录的是 t 的字母数量sCount 记录的是 s 的字母数量。这里只要求 sCount 中相应字母的数量比 t 的多即可而不一定要相等。
解题思路
首先移动右指针 right 使得窗口能够覆盖子串然后移动左指针 left 直到窗口刚好不能覆盖子串再移动右指针 right 使得窗口能够覆盖子串循环往复期间要维护最小长度和起始位置
思路说明图 可以类比为一只爬行的毛毛虫。首先毛毛虫伸头使得窗口能够覆盖子串 “ABC”然后毛毛虫收尾使得窗口刚好不能覆盖子串 “ABC”毛毛虫再伸头使得窗口能够再次覆盖子串 “ABC”以此类推。
class Solution {
public:unordered_mapchar, int sCount, tCount;bool succeed() {for (auto t:tCount) {if (sCount[t.first] t.second) {return false;}}return true;}string minWindow(string s, string t) {int sLen s.size(), tLen t.size();int minStart 0, minLen sLen;string ans;int flag 0;if (sLen tLen) return ;for (int i 0; i tLen; i) {tCount[t[i]];}int left 0, right 0;while (right sLen) {// 毛毛虫伸头if (tCount.find(s[right]) ! tCount.end()) {sCount[s[right]];}right;// 毛毛虫收尾while (succeed()) {flag 1;if (tCount.find(s[left]) ! tCount.end()) {--sCount[s[left]];}if (minLen right - left) {minLen right - left;minStart left;}left;}}// 处理结果if (flag) {for (int i minStart; i minStart minLen; i) {ans.push_back(s[i]);}}return ans;}
};
说明每次做如下判断是因为我们只关心子串中含有的字母的个数
if (tCount.find(s[right]) ! tCount.end()) {sCount[s[right]];
}
