class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
        int l=0,r=nums.size()-1;
        while(l<r){
            int mid=l+r+1>>1;
            if(nums[mid]>=nums[0]) l=mid;
            else r=mid-1;
        }
        if(target>=nums[0]) l=0;    //前面的区间
        else l=r+1,r=nums.size()-1; //后面的区间

        while(l<r){
            int mid=l+r>>1;
            if(nums[mid]>=target) r=mid;
            else l=mid+1;
        }
        if (nums[r] == target) return r;
        return -1;
    }
};

继续摆

class Solution {
public:
    int f(string & s){
        map<char,int> cnt;
        for (auto c:s ) cnt[c]++;
        return cnt.begin()->second; 
    }
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        vector<int> res;
        int s[11]={0};//长度0-10
        for(auto& w:words) s[f(w)]++;
        for(int i=1;i<=10;i++) s[i]+=s[i-1];

        for(auto & q :queries){
            res.push_back(s[10]-s[f(q)]);
        }
        return res;
    }
};

dp版本

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        vector<int> f(n, 0);
        //f[i]以i结尾的最长子串 只考虑s[i]==')'
        //s[i]==')'
        //1:s[i-1]=='('  f[i]=f[i-1]+2;
        //2:s[i-1]==')'&&s[i-f[i-1]-1]=='('  f[i]=f[i-1]+2 +f[i-f[i-1]-1-1]
        for (int i = 1; i < n; i++)
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                     f[i] = (i>=2? f[i - 2]:0) + 2;
                } 
                else {
                    if (i - f[i - 1] - 1 >= 0 && s[i - f[i - 1] - 1] == '(')
                        f[i] = f[i - 1] + 2 + ((i - f[i - 1] - 2>=0)?f[i - f[i - 1] - 2]:0);
                }
            }

        int ans = 0;
        for (int i = 0; i < n; i++)  if(s[i]==')')ans = max(ans, f[i]);

        return ans;
    }
};

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        int res=0;
        int start=-1;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                stk.push(i);
            }
            else{

                if(stk.size()){
                    stk.pop();
                    if(stk.size()) res=max(res,i - (stk.top() + 1) + 1);
                    else res=max(res,i-start);
                }
                else{
                    start=i;
                }
            }
        }
        return res;
     }
};

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k=nums.size()-1;
        while(k>0&&nums[k-1]>=nums[k]) k--;
        //从后往前

        //321情况
        if(k==0){
            reverse(nums.begin(),nums.end());
        }
        else{
            //24531 swap 后23541 =》23145
            int t=k;
            while(t<nums.size()&&nums[k-1]<nums[t]) t++;
            swap(nums[t-1],nums[k-1]);
            reverse(nums.begin()+k,nums.end());
        }
    }
};

class Solution {
public: 
    //滑动窗口
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        if(!words.size()) return res;
        unordered_map<string,int> tot;
        for(auto  str:words) tot[str]++;
        int n=s.size();
        int m=words.size();
        int k=words[0].size();
        for(int i=0;i<k;i++){//起始位置的不同
            unordered_map<string,int> wd;
            int cnt=0;//如果暴力计算wd和tot是否匹配会TLE
            for(int j=i;j+k<=n;j+=k){
                if(j>=i+m*k){
                    auto word=s.substr(j-m*k,k);
                    wd[word]--;
                    //有效单词--
                    if(wd[word]<tot[word]) cnt--;
                }

                auto word = s.substr(j, k);//此时的下标为j+k—1<n <==> j+k<=n
                wd[word]++;
                //有效单词++
                if(wd[word]<=tot[word]) cnt++;
                //此时j处于倒数第一个单词
                if(cnt==m) res.push_back(j-(m-1)*k);
            }
        }

        return res;
    }
};

class Solution {
public:
    int divide(int dividend, int divisor) {

        int flag=1;
        if(dividend<0&&divisor>0||dividend>0&&divisor<0) flag=-1;
        int x=abs(dividend);
        int y=abs(divisor);

        long long  l=0,r=x;
        while(l<r){
            long long  mid=l+r+1>>1;
            if(x>=mul(mid,y)) l=mid;
            else r=mid-1;
        }
        long long res=flag==1?l:-l;
        if(res>INT_MAX||res<INT_MIN) return INT_MAX;
        return res;
    }

    long long  mul(long long   mid,long long  y){
        long long res=0;
        while(y){
            if((y&1)==1)res+=mid;
            y>>=1;
            mid+=mid;
        }
        return res;
    }
};



       /*
        if(dividend==INT_MIN&&divisor==-1) return INT_MAX;
        int flag=1;
        if(dividend<0&&divisor>0||dividend>0&&divisor<0) flag=-1;

        long long  up=abs(dividend);
        long long  down=abs(divisor);
        long long  res=0;
        for(int i=31;i>=0;i--){
            if((up>>i)>=down){
                res+=1<<i;
                up-=(down<<i);
            }
        }
        if (res > INT_MAX || res < INT_MIN) return INT_MAX;

        return flag==1?res:-res;
       */

class Solution {
public:
    int strStr(string s, string p) {
        int n = s.size(), m = p.size();
        if(m == 0) return 0;
        //设置哨兵
        s=" "+s;
        p=" "+p;
        vector<int> next(m + 1);
        //预处理next数组
        for(int i = 2, j = 0; i <= m; i++){
           while(j&&p[i]!=p[j+1]) j=next[j];
            if(p[i] == p[j + 1]) j++;
            next[i] = j;
        }
        //匹配过程
        for(int i = 1, j = 0; i <= n; i++){
            while(j&&s[i]!=p[j+1]) j=next[j];
            if(s[i] == p[j + 1]) j++;
            if(j == m) return i - m;//匹配成功 返回下标
        }
        return -1;
    }
};

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=val) nums[k++]=nums[i];
        }
        return k;
    }
};

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k=0;
        for(int i=0;i<nums.size();i++){
            if(!(i&&nums[i]==nums[i-1])){
                nums[k++]=nums[i];
            }
        }
        return k;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode * dummy=new ListNode(-1);
        ListNode * p=dummy;
        dummy->next=head;

      while(p){

            auto q=p;
            for(int i=0;i<k&&q;i++) q=q->next;
            if(!q) break;
            auto a=p->next;
            auto b=a->next;
            for(int i=0;i<k-1;i++){
                auto c=b->next;
                b->next=a;
                a=b;
                b=c;
            }
            auto c=p->next;
            p->next=a;
            c->next=b;
            p=c;
        }
        return dummy->next;
    }
};