邯郸城乡建设部网站首页,北京怎样建设公司网站,哪个网站的体验做的最好,wordpress插件seo例1
209. 长度最小的子数组 ①窗口大小不固定
②求最小长度 - ret INT_MAX
③数组内的值都大于0#xff0c; 符合单调性#xff08;sum nums[right] - sum增大#xff09;
while里面符合条件#xff0c;在里面更改ret 参考代码
class Solution {
public:i…例1
209. 长度最小的子数组 ①窗口大小不固定
②求最小长度 - ret INT_MAX
③数组内的值都大于0 符合单调性sum nums[right] - sum增大
while里面符合条件在里面更改ret 参考代码
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int ret INT_MAX;for(int left 0, right 0, sum 0; right nums.size(); right){sum nums[right];while(sum target){ret min(ret, right - left 1);sum - nums[left];}}return ret INT_MAX ? 0 : ret;}
};
例2
3. 无重复字符的最长子串 while里面是不符合条件的外面与ret比较就行
参考代码
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] {0};int ret 0;for(int left 0, right 0; right s.size(); right){hash[s[right]];while(hash[s[right]] 1){hash[s[left]]--;}ret max(ret, right - left 1);}return ret;}
};
例3
1004. 最大连续1的个数 III [right, left]有效闭区间
参考代码
class Solution {
public:int longestOnes(vectorint nums, int k) {int ret 0;for(int left 0, right 0, zero 0; right nums.size(); right){if(nums[right] 0) zero;while(zero k){if(nums[left] 0) zero--;}ret max(ret, right - left 1);}return ret;}
};
例4 转换为求中间最大长度
如果要用注释掉的部分就要写上target 0因为while(tmp target) 会left这里的会导致left越界所以分开写较好把满足条件的放在外面
参考代码
class Solution {
public:int minOperations(vectorint nums, int x) {int sum 0, ret -1;for(auto e : nums)sum e;int target sum - x;if(target 0) return -1;// if(target 0) return nums.size();//for(int left 0, right 0, tmp 0; right nums.size(); right){tmp nums[right];// while(tmp target)//☆☆☆☆☆// {// if(tmp target)// ret max(ret, right - left 1);// tmp - nums[left];//的时候越界最后一次// }while(tmp target) tmp - nums[left];if(tmp target) ret max(ret, right - left 1);}return ret -1 ? -1 : nums.size() - ret;}
};例5
904. 水果成篮 后面的题都用到哈希映射
分析哈希的临界点是从0 - 1 和从 1 - 0
语法--hash[fruits[left]] 看括号里面的优先外面括号的前置“”“--” 往后稍稍所以hash的索引是fruit[left]再是left自增再是--hash[fruit[left]]
参考代码
class Solution {
public:int totalFruit(vectorint fruits) {int hash[100001] {0}, ret 0;for(int left 0 ,right 0 ,count 0; right fruits.size(); right){if(hash[fruits[right]] 0) count;while(count 2)if(--hash[fruits[left]] 0) count--;ret max(ret, right - left 1);}return ret;}
};
例6
438. 找到字符串中所有字母异位词 分析因为是固定窗口所以if(right - left 1 p.size())用的是if只用右移一次left
语法分析
①代码是全都拆开
②后置 和后置 -- 在这里两个写一起是不对的因为右操作数例有left顺序是这样的显示返回hash2[s[left],然后left然后hash2[s[left]]--这时候left已经变大了1导致左右两边left不是相同的值
③和⑤可以统一left
②③和④⑤是后置-- 和前置-- 的区别所以判断条件也会不同。个人觉得后置的更好直接理解
参考代码
class Solution {
public:vectorint findAnagrams(string s, string p) {vectorint ret;int hash1[128] {0}, hash2[128] {0};for(auto e : p)hash1[e];for(int left 0, right 0, count 0; right s.size(); right){if(hash2[s[right]] hash1[s[right]]) count;if(right - left 1 p.size()){// if(hash2[s[left]] hash1[s[left]]) count--; 1// hash2[s[left]]--;// left;//if(hash2[s[left]]-- hash1[s[left]]) count--;不对先 2// if(hash2[s[left]]-- hash1[s[left]]) count--; 3// left;//if(--hash2[s[left]] hash1[s[left]]) count--;//不行 4//这里的后缀比前置的--优先级高if(--hash2[s[left]] hash1[s[left]]) count--; //5left;}if(count p.size())ret.push_back(left);}return ret;}
};
例7 分析对比上题就是把字符换成了字符串那就只能用unordered_mapstring, int,
题目说了words里面的每个元素的长度相同次数words[0].size()
注意 leftright i不是0不然会ret是重复的数组
对于这行代码 if(hash1.count(in) hash2[in] hash1[in]) count;如果hash1[in]没有这个in那么会自己创建一个会浪费时间前面加上hash1.count(in)判断可以减少时间的消耗
参考代码
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {unordered_mapstring, int hash1;vectorint ret;for(auto e : words)hash1[e];int len words[0].size();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));if(hash1.count(in) hash2[in] hash1[in]) count;if(right - left len - 1 words.size() * len){string out(s.substr(left, len));if(hash1.count(out) hash2[out]-- hash1[out]) count--;left len;}if(count words.size())ret.push_back(left);} }return ret;}
};
例8
76. 最小覆盖子串 ①ret min(ret, right - left 1), begin left;
②if(right - left 1 ret) {ret right - left 1;begin left;}
①②两段代码是有区别的 上面不管ret是否变化begin就会改变 下面的ret变小了才会变化
依据上面的题目知道这里的left是不能写在里面的
if(hash2[s[left]]-- hash1[s[left]]) count--;left;
注这里是求最小长度那么窗口肯定是变化的肯定是while
参考代码
class Solution {
public:string minWindow(string s, string t) {int hash1[128] {0}, hash2[128] {0}, ret INT_MAX, begin -1;for(auto e : t)hash1[e];for(int left 0, right 0, count 0; right s.size(); right){if(hash2[s[right]] hash1[s[right]]) count;while(count t.size()){// ret min(ret, right - left 1), begin left;if(right - left 1 ret){ret right - left 1;begin left;}if(hash2[s[left]]-- hash1[s[left]]) count--;left;}}return ret INT_MAX ? : s.substr(begin, ret);}
};
