3.20【L】algorithm

1

        size_t pos = line.find('/');
        string numerator_str = line.substr(0, pos);
        string denominator_str = line.substr(pos + 1);

54(未解）

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int r=matrix.size(),c=matrix[0].size();
        vector<int>res;
        int curr=0,curc=-1;
        int d=0,rb=c-1,lb=0,bb=0,tb=r-1;
        while(res.size()<r*c){//0为左，1为下，2为右，3为上//0时缩减上边界，1时缩减右边界，2时缩减下边界，3时缩减左边界
            if(d==0){
                curc++;
                bb++;
                while(curc<=rb){
                    res.push_back(matrix[curr][curc++]);   
                }
                d=(d+1)%4;
            }else if(d==1){
                curr++;
                rb--;
                while(curr<=tb){
                    res.push_back(matrix[curr++][curc]);
                }
                d=(d+1)%4;
            }else if(d==2){
                curc--;
                tb--;
                while(curc>=lb){
                    res.push_back(matrix[curr][curc--]);
                }
                d=(d+1)%4;
            }else{
                curr--;
                lb++;
                while(curr>=bb){
                    res.push_back(matrix[curr--][curc]);
                }
                d=(d+1)%4;
            }
        }
        return res;
    }
};

这个问题主要就是在while里面，由于是==的，所以在最后循环出来的时候的++，使r和c超出了范围

56

这个就是最终答案如果是在违反条件时加入的，那么就会出现情况是，数组中最后一个违反了，同时也是需要加入到最终答案，但是因为数组已经遍历完了，所以会导致最后的解被意外丢弃掉，所以是需要加以特判的

这个问题，是因为想当然的认为排序后的元素的末端，是一定大于前一个的，加一个max判断就行了

解决以上两个问题，就是考虑尾插，就是说当违反条件时插入，那么对于最后一个元素，必然是不会在循环中被插入进去的，所以在循环结束后，就需要额外进行一次必须的插入操作

53

线段树分治

class Solution {
public:
    struct status{
        int lsum,rsum,res,isum;
    };
    status pushup(status l,status r){
        int lsum=max(l.lsum,l.isum+r.lsum);
        int rsum=max(r.rsum,r.isum+l.rsum);
        int isum=l.isum+r.isum;
        int res=max(max(l.res,r.res),l.rsum+r.lsum);
        return (status){lsum,rsum,res,isum};
    }
    status gets(vector<int>&nums,int l,int r){
        if(l>=r){
            return (status){nums[r],nums[r],nums[r],nums[r]};
        }
        int mid=(l+r)>>1;
        status ls=gets(nums,l,mid);
        status rs=gets(nums,mid+1,r);
        return pushup(ls,rs);
    }
    int maxSubArray(vector<int>& nums) {
        return gets(nums,0,nums.size()-1).res;
    }

};

DP

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        
        vector<int>dp(nums.size());
        dp[0]=nums[0];
        int res=dp[0];
        for(int i=1;i<nums.size();i++){
            dp[i]=max(nums[i],dp[i-1]+nums[i]);
            res=max(res,dp[i]);
        }
        return res;
    }
};

暴力法

暴力法一开始没考虑负数的情况

不出意外，暴力法的n^2超时了

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res=INT_MIN;
        vector<int>subSum(nums.size()+1);
        subSum[0]=0;
        for(int i=1;i<=nums.size();i++){
            subSum[i]=subSum[i-1]+nums[i-1];
        }
        for(int i=0;i<nums.size();i++){
            for(int j=1;j<=nums.size()-i;j++){
                int sum=subSum[i+j]-subSum[i];
                res=max(res,sum);
            }
        }
        return res;
    }
};

76

该如何判断两个子串之间是否有包含关系？

这里溢出了，

数组优化版

class Solution {
public:
    int cnt_s[128]{}; // s 子串字母的出现次数
    int cnt_t[128]{}; // t 中字母的出现次数
    bool is_covered() {
        for (int i = 'A'; i <= 'Z'; i++) {
            if (cnt_s[i] < cnt_t[i]) {
                return false;
            }
        }
        for (int i = 'a'; i <= 'z'; i++) {
            if (cnt_s[i] < cnt_t[i]) {
                return false;
            }
        }
        return true;
    }
    unordered_map<int,int>ori;
    unordered_map<int,int>cnt;
    string minWindow(string s, string t) {
        if(t.size()>s.size()){
            return "";
        }
        
        for(int i=0;i<t.size();i++){
            //ori[t[i]-'a']++;
            cnt_t[t[i]]++;
        }
        int begin=0,end=s.size()-1;
        while(cnt_t[s[begin]]==0){
            begin++;
            if(begin==s.size()){
                return "";
            }
        }
        while(cnt_t[s[end]]==0){
            end--;
            if(end==-1){
                return "";
            }
        }
        int l=begin,ans=INT_MAX,ansL=-1;
        for(int r=begin;r<=end;r++){
            cnt_s[s[r]]++;
            while(is_covered()){
                if(r-l+1<ans){
                    ans=r-l+1;
                    ansL=l;
                }
                cnt_s[s[l]]--;
                l++;
                if(l>r){break;}
            }
        }
        return (ansL==-1)?"":s.substr(ansL,ans);
    }
    bool check(){
        for(auto it:ori){
            if(cnt[it.first]<it.second){
                return false;
            }
        }
        return true;
    }
};

官方题解优化版

class Solution {
public:
    unordered_map<int,int>ori;
    unordered_map<int,int>cnt;
    string minWindow(string s, string t) {
        if(t.size()>s.size()){
            return "";
        }
        
        for(int i=0;i<t.size();i++){
            ori[t[i]-'a']++;
        }
        int begin=0,end=s.size()-1;
        while(ori.find(s[begin]-'a')==ori.end()){
            begin++;
            if(begin==s.size()){
                return "";
            }
        }
        while(ori.find(s[end]-'a')==ori.end()){
            end--;
            if(end==-1){
                return "";
            }
        }
        int l=begin,ans=INT_MAX,ansL=-1;
        for(int r=begin;r<=end;r++){
            cnt[s[r]-'a']++;
            while(check()){
                if(r-l+1<ans){
                    ans=r-l+1;
                    ansL=l;
                }
                cnt[s[l]-'a']--;
                l++;
                if(l>r){break;}
            }
        }
        return (ansL==-1)?"":s.substr(ansL,ans);
    }
    bool check(){
        for(auto it:ori){
            if(cnt[it.first]<it.second){
                return false;
            }
        }
        return true;
    }
};

239

优先队列版

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int,int>>pq;
        for(int i=0;i<k;i++){
            pq.push({nums[i],i});
        }
        vector<int>res;
        res.push_back(pq.top().first);
        for(int i=1;i<nums.size()-k+1;i++){
            pq.push({nums[i+k-1],i+k-1});
            pair<int,int> top=pq.top();
            while(top.second<i){
                pq.pop();
                top=pq.top();
            }
            res.push_back(top.first);
        }
        return res;
    }
};

单调栈版 

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<pair<int,int>>dq;
        vector<int>res;
        for(int i=0;i<k;i++){
            if(dq.empty()){
                dq.push_back({nums[i],i});
            }
            pair<int,int>tmp=dq.back();
            while(tmp.first<=nums[i]){
                dq.pop_back();
                if(dq.empty()){
                    break;
                }
                tmp=dq.back();
            }
            dq.push_back({nums[i],i});
        }
        res.push_back(dq.front().first);
        for(int i=k;i<nums.size();i++){
            pair<int,int>tmp=dq.back();
            while(tmp.first<=nums[i]){
                dq.pop_back();
                if(dq.empty()){
                    break;
                }
                tmp=dq.back();
            }
            dq.push_back({nums[i],i});
            tmp=dq.front();
            while(tmp.second<i-k+1){
                dq.pop_front();
                tmp=dq.front();
            }
            res.push_back(tmp.first);
        }
        return res;
    }
};

42接雨水

class Solution {
public:
    int trap(vector<int>& height) {
       vector<int>lh;
       vector<int>rh;
       lh.resize(height.size());
       rh.resize(height.size());
       lh[0]=height[0];
       rh[height.size()-1]=height[height.size()-1];
       for(int i=1;i<height.size();i++){ 
            lh[i]=max(lh[i-1],height[i]);
       }
       for(int i=height.size()-2;i>=0;i--){
            rh[i]=max(rh[i+1],height[i]);
       }
    //    for(int i=0;i<height.size();i++) 
       int sum=0;
       for(int i=1;i<height.size()-1;i++){
            //int subSum=;
            //cout<<"has accumulate: "<<subSum<<endl;
            sum+=min(lh[i],rh[i])-height[i];
       }
       return sum;
    }
};

3

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size()==0){return 0;}
        int res=1,tmp=1;
        set<char>table;
        table.insert(s[0]);
        for(int i=1;i<s.size();i++){
            if(table.find(s[i])==table.end()){
                tmp++;
                table.insert(s[i]);
            }else{
                //cout<<" cur index: "<<i<<" cur lenth: "<<tmp<<" cur letter: "<<s[i]<<endl;
                res=max(tmp,res);
                tmp=1;
                table.clear();
                table.insert(s[i]);
            }
        }
        return res;
    }
};

这个会出问题，就是更新结果需要依赖相同字母的出现，如果一直都是不同字母，就会导致结果无法发生更改，所以需要在最后加个更新补充

一个窗口，右侧遇到新字母时，在窗口内去搜索，看是否有重复，

如果有，那么移动左指针到这个新字母，因为即使一步一步移动指针，必然不会有最左侧的情况好

如果没有，那么就更新窗口

窗口内部使用哈希表来加快搜索

438

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if(s.size()<p.size()){return {};}
        vector<int>scount,pcount,res;
        scount.resize(26);
        pcount.resize(26);
        for(int i=0;i<p.size();i++){
            pcount[p[i]-'a']+=1;
            scount[s[i]-'a']+=1;
        }
        if(pcount==scount){
            res.push_back(0);
        }
        for(int i=p.size();i<s.size();i++){
            scount[s[i]-'a']+=1;
            scount[s[i-p.size()]-'a']-=1;
            if(pcount==scount){
                res.push_back(i-p.size()+1);
            }
        }
        return res;
    }
};//如果新字母不在p时，那么必然含p的子串必然也不在