2134. 最少交换次数来组合所有的 1 II

断环成链+滑动窗口

思路先算出数组中1有多少，然后看这么长的窗口里0最少是多少，此时即为最少交换次数。

首先遍历算出1的数量k，然后用Insert拼接数组，从而实现循环。

然后双指针遍历数组，是0就ant++,如果窗口长度超了，缩一下j，当窗口建立完毕时更新mi

class Solution {
public:int minSwaps(vector<int>& nums) {int k=0;for(auto i:nums)if(i)k++;nums.insert(nums.end(),nums.begin(),nums.end());int l=nums.size();int ant=0,mi=INT_MAX;for(int i=0,j=0;i<l;i++){ if(!nums[i])ant++;while(i-j+1>k){if(!nums[j])ant--;j++;}if(i-j+1==k)mi=min(mi,ant);}return mi;}
};

1888.使二进制字符串交替的最少反转次数

详细题解链接

class Solution {
public:int minFlips(string s) {int k=s.size();int ant=0,mi=INT_MAX;s+=s; int l=s.size();for(int i=0,j=0;i<l;i++){if((i-j)%2&&s[i]==s[j]||((i-j)%2==0&&s[i]!=s[j]))ant++;if(i-j+1>k){if(s[j]==s[j+1])ant=k-ant;j++;}if(i>=k-1)mi=min(mi,ant);}return mi;}
};

567. 字符串的排列

这个题我们先遍历一遍s1,存到数组中，然后滑动窗口，只要该字符超出了s2的就移动左指针，直到窗口长度等于子字符串的长度。

class Solution {
public:bool checkInclusion(string s1, string s2) {int l1=s1.size(),l2=s2.size();int a[30]={0};for(auto i:s1)a[i-'a']++;for(int i=0,j=0;i<l2;i++){a[s2[i]-'a']--;while(j<=i&&a[s2[i]-'a']<0){a[s2[j]-'a']++;j++;}if(i-j+1==l1)return 1;}return 0;}
};

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

跟上一题思路基本一样

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ant;int ls=s.size(),lp=p.size();int a[30]={0};for(auto i:p)a[i-'a']++;for(int i=0,j=0;i<ls;i++){a[s[i]-'a']--;while(j<=i&&a[s[i]-'a']<0){a[s[j]-'a']++;j++;}if(i-j+1==lp)ant.push_back(j);}return ant;}
};

30. 串联所有单词的子串

这个题在前面题的思路上复杂一点，每次i，j加k个长度，并且要多起点开始遍历，这样才能找出所有的单词。

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ant; int k=words[0].size(),l=words.size();int ls=s.size();unordered_map<string,int> m;for(auto i:words)m[i]++;for(int q=0;q<k;q++){unordered_map<string ,int> a;for(int i=q,j=q;i<ls;i+=k){string st=s.substr(i,k);a[st]++;while(j<=i&&m[st]<a[st]){a[s.substr(j,k)]--;j+=k;}if(i-j+k==k*l)ant.push_back(j);}}return ant;}
};

2156. 查找给定哈希值的子串

主要是取模，需要从尾部遍历，因为除法的取模不好处理，采用乘法

class Solution {
public:string subStrHash(string s, int power, int modulo, int k, int hashValue) {long long hash=0;long long p=1; int l=s.size();int ant=INT_MAX;for(int i=l-1;i>=l-k;i--){hash=((s[i]&31)+hash*power)%modulo;p=p*power%modulo;}if(hash==hashValue) ant=l-k;for(int i=l-1,j=l-k-1;j>=0;i--,j--){hash=(hash*power+(s[j]&31)-p*(s[i]&31)%modulo+modulo)%modulo;if(hash==hashValue)ant=j;}return s.substr(ant,k);}
};