刷爆Leetcode Day3

11.最大连续1的个数III（medium）

最大连续1的个数III

class Solution {
public:int longestOnes(vector<int>& nums, int k) {//翻转最多k个0可以理解为子数组中最多可以存在k个0,用一个变量标记//滑动数组问题//for块进窗口int ret=0;for(int right=0,left=0,count=0,n=nums.size();right<n;right++){if(nums[right]==0)count++;while(count>k)//出窗口{if(nums[left]==0)count--;left++;}ret=ret>right-left+1?ret:right-left+1;}return ret;}
};

12. 将x减到0的最小操作数(medium)

将x减到0的最小操作数

class Solution {
public:int minOperations(vector<int>& nums, int x) {//题目要求x减去两端区间减到0，要求区间中的元素最少//这道题难点在两端区间并不一定是一个连续的区间，但是我们可以转化成一个连续区间//对数组求和减去x就是中间区间的值，中间区间是一个连续的空间//这样就可以使用滑动窗口方法int sum=0;int ret=-1;int n=nums.size();for(auto ch:nums)sum+=ch;int target=sum-x;if(target<0)return -1;for(int left=0,right=0,sub_sum=0;right<n;right++){sub_sum+=nums[right];while(sub_sum>target){sub_sum-=nums[left];left++;}if(sub_sum==target)ret=ret>right-left+1?ret:right-left+1;}return ret==-1?-1:n-ret;}
};

13. 水果成篮（medium)

水果成篮

class Solution {
public:int totalFruit(vector<int>& fruits) {//数组中的元素代表了元素种类//子数组当中应该只有两种元素才能入篮//多于两种元素则要出篮//滑动数组问题//考虑到同种种类的水果有多个，出窗口要将水果个数全出种类才减少//使用哈希表//数组模拟哈希表int hash[100000] ={0};int len=0;for(int left=0,right=0,kind=0;right<fruits.size();right++){if(hash[fruits[right]]==0)kind++;hash[fruits[right]]++;while(kind>2){hash[fruits[left]]--;if(hash[fruits[left]]==0)kind--;left++;}len=len>right-left+1?len:right-left+1;}return len;}
};

14. 找到字符串中所有字母异位词（medium）

找到字符串中所有字母异位词

class Solution {
public:vector<int> findAnagrams(string s, string p) {//滑动窗口问题，不过窗口大小事固定的//难点在于判断vector<int> ret;int hash1[26]={0};int hash2[26]={0};for(auto ch:p)hash1[ch-'a']++;//简单来说就是当区间子串元素个数等于p的个数时，进行for循环的判断（这里是线性的因为字符只有二十六种）//否则不断进出窗口for(int right=0,left=0;right<s.size();right++){hash2[s[right]-'a']++;while(right-left+1>p.size()){hash2[s[left]-'a']--;left++;}for(int i=0;i<26;i++){if(hash1[i]!=hash2[i])break;else if(i==25)ret.push_back(left);}}return ret;}
};

15. 串联所有单词的⼦串（hard）

串联所有单词的⼦串

再理解