织梦小说网站源wap站,wordpress需要付费才能看某些页面,最新黑帽seo教程,汽配网站建设文章目录 例题1#xff1a;长度最小的子数组例题2#xff1a;无重复字符的最长子串例题3#xff1a;最大连续1的个数 III例题4#xff1a;将 x 减到 0 的最小操作数例题5#xff1a;水果成篮例题6#xff1a;找到字符串中所有字母异位词例题7#xff1a;串联所有单词的子… 文章目录 例题1长度最小的子数组例题2无重复字符的最长子串例题3最大连续1的个数 III例题4将 x 减到 0 的最小操作数例题5水果成篮例题6找到字符串中所有字母异位词例题7串联所有单词的子串例题8最小覆盖子串 例题1长度最小的子数组
长度最小的子数组 分析 若暴力枚举用三重循环列出所有可能
int n nums.size();
for(int i 0; i n; i){//以i位置开头的所有子数组for(int j i; j n; j){//以j位置为结尾int n 0;for(int k i; k j; k){//依次算出各个子数组的和然后比较和大于等于target的子数组的长度那个最小n nums[k];
………………………………………………………………
//时间复杂度 O(N^3)简单的优化计算子数组和时不需要每次都从头开始
int n nums.size();
for(int i 0; i n; i){//以i位置开头的所有子数组int n 0;for(int j i; j n; j){n nums[j];//时间复杂度 O(N^2)因为这道题说数组中的数全为正整数所以 操作后 n 肯定是递增的单调性 —— 当 n target 时就没有继续 的必要了此时 n 就是这个循环中 长度最小的、和大于等于target的子数组的和
以 2 3 1 2 4 3target 7 为例第一层循环过后我们知道了以0位置开头的子数组中2 3 1 2 是我们想要的第二次循环会从3开始我们需要再从头开始枚举子数组吗 —— 我们可以记录第一次循环结束位置然后直接以3 1 2为基础继续
● 根据以上的分析我们改用两个指针同向双指针同向指两个指针都不回退向着一个方向移动来实现上述的操作 left 和 right 两个“指针”之间形成一个区间并记录维护着这个区间内的信息子数组和、长度两个指针从左向右移动的过程中这个区间就像一个窗口一样在数组中滑动 —— 滑动窗口 以上的思路为利用单调性使用“同向双指针滑动窗口”优化问题 ● 怎么用 1.left 0right 0 2.进窗口 3.判断 - 出窗口
● 这个方法的正确性 利用单调性规避了很多没有必要的枚举行为 在暴力解法中若发现了单调性可以考虑用这个方法 class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int n nums.size(), sum 0, len INT_MAX;//结果for(itn left 0, right 0; right n; right){sum nums[right];//进窗口新进入left和right之间的数据会产生什么影响--sumnums[right]while(sum target)//判断{len min(len, right - left 1);//更新结果 -- 可能在判断后也可能在出窗口后因题而异sum - num[left];//出窗口left过后左侧数据不再处于left和right之间}}return len;}
};● 时间复杂度 我们的每一步操作都让 left / right 向右移动直至最后 - O(N)
例题2无重复字符的最长子串
无重复字符的最长子串 暴力解法暴力枚举从左往右依次枚举以左侧数字为开头的满足要求的所有子串-- 判断满足要求可以用哈希表储存已遍历子串部分的字符依次判断字符是否重复
模拟
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] {0};//使用数组模拟哈希表0表示没有1出现一次2出现两次int len 0;for(int left 0, right 0; right s.size(); right){hash[s[right]];//进窗口while(hash[s[right]] 1)//判断 hash[s[left]]--;//出窗口len max(len, right - left 1);//更新结果}return len;}
};例题3最大连续1的个数 III
最大连续1的个数 III 问题转化找出0的个数不超过k个的最长子数组
暴力求解从左往右依次以每个数为开头往后找最长可以到哪 -O(N^2) 模拟示例1
class Solution {
public:int longestOnes(vectorint nums, int k) {int ret 0;for(int left 0, right 0, zero 0; right nums.size(); right){//zero记录0的个数//对于right而言1进窗口时不用管if(nums[right] 0) zero;//0进窗口while(zero k)//判断if(nums[left] 0) zero--;//出窗口ret max(ret, right - left 1);//更新结果}return ret;}
};例题4将 x 减到 0 的最小操作数
将 x 减到 0 的最小操作数 分析 正 难 则 反 class Solution {
public:int minOperations(vectorint nums, int x) {//题目说了nums[i]0int sum_ 0;for(auto e : nums) sum_ e;int target sum_ - x;if(target 0) return -1;//!int n nums.size(), len -1;for(int left 0, right 0, sum 0; right n; right){sum nums[right];//入窗口while(sum target){//判断sum - nums[left];//出窗口 }if(sum target) len max(len,right - left 1);//更新结果}return len -1 ? -1 : n - len;//如果len初始被赋予 0这地方用len 0做判断遇到 target 0 的情况会出问题}
};例题5水果成篮
水果成篮 class Solution {
public:int totalFruit(vectorint fruits) {int n fruits.size();int hash[100001] {0};//数组模拟哈希表表示各水果类型所持数目 //也可以用unordered_map似乎更方便些//题目说 1 fruits.length 10^5结果开10010个空间不给过合着 10^5的意思是数量级不是具体数呗这个老六int num 0, sort 0;for(int left 0, right 0; right n; right){if(hash[fruits[right]] 0) sort;hash[fruits[right]];//入窗口while(sort 2){if((--hash[fruits[left]]) 0)//出窗口sort--;}num max(num, right - left 1);}return num;}
};这个方法我和老师写的几乎一模一样 —— 我终于出息了 老师用哈希表的演示 class Solution {
public:int totalFruit(vectorint fruits) {unordered_mapint, int hash;int ret 0;for(int left 0, right 0; right fruits.size(); right){hash[fruits[right]];//进窗口while(hash.size() 2){//出窗口hash[fruits[left]]--;if(hash[fruits[left]] 0)hash.erase(fruits[left]);left;}ret max(ret, right - left 1);}return ret;}
};例题6找到字符串中所有字母异位词
找到字符串中所有字母异位词 不同于之前的题目的是这道题的滑动窗口是固定长度的长度为p的大小
可以用两个哈希表分别表示 p 中每个字符出现的次数 和 滑动窗口中每个字符出现的次数。通过比较两哈希表是否相同判断异位词 class Solution {
public:vectorint findAnagrams(string s, string p) {int hash1[26] {0};//p中每个字符出现的次数for(auto ch : p) hash1[ch-a];int hash2[26] {0};//滑动窗口中每个字符出现的次数vectorint ret;for(int left 0, right 0, count 0; right s.size(); right){char in s[right];//进窗口的字符 hash2[in - a];//进窗口if(hash2[in - a] hash1[in - a]) count;//判断if(right - left p.size()){//固定的窗口长度:p.size()char out s[left];if(hash2[out - a]-- hash1[out - a]) count--;//出窗口}if(count p.size()) ret.push_back(left);//更新结果}return ret;}
};例题7串联所有单词的子串
串联所有单词的子串 例题6 的加强版试着将子串当做一整个数据就像单个字符一样
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {unordered_mapstring, int hash1;//存储 words 中的子串for(auto str : words) hash1[str];int len words[0].size();//一个子串的长度可视作一个整体数据vectorint ret;for(int i 0; i len; i){//自不同的起点出发遍历所有情况unordered_mapstring, int hash2;//维护滑动数组内的子串for(int left i, right i, count 0; right len s.size(); right len){string in s.substr(right, len);//进窗口的子串hash2[in];//进窗口if(hash1.count(in) hash2[in] hash1[in]) count;if(right - left len * words.size()){string out s.substr(left, len);//出窗口的数据if(hash1.count(out) hash2[out] hash1[out]) count--;hash2[out]--;left len;//出窗口}if(count words.size()) ret.push_back(left);}}return ret;}
};例题8最小覆盖子串
最小覆盖子串 分析
class Solution {
public:string minWindow(string s, string t) {int hash1[58] { 0 };//开了57个空间然后不够……建议直接开128个空间还省去了后面 -A 的麻烦for (auto ch : t) hash1[ch - A];int hash2[58] { 0 };int begin -1, len INT_MAX;for (int left 0, right 0, count 0; right s.size(); right) {char in s[right];//进窗口数据hash2[in - A];//进窗口if (hash2[in - A] hash1[in - A]) count;while (count t.size()) {//判断if (right - left 1 len) {//更新结果len right - left 1;begin left;}char out s[left];//出窗口数据if (hash2[out - A] hash1[out - A]) count--;hash2[out - A]--;//出窗口left;}}return len INT_MAX ? : s.substr(begin, len);}
};
