讨论/题目交流/🏆 第 159 场力扣周赛/
🏆 第 159 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

缀点成线
删除子文件夹
替换子串得到平衡字符串
规划兼职工作

展开讨论

第二题

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& f) {
        set<string> st;
        for(int i = 0;i<f.size();i++){
            st.insert(f[i]);
        }
        for(int i = 0;i<f.size();i++){
            string str;
            for(int j = 0;j<f[i].size();j++){
                if(f[i][j]=='/'){
                    if(st.find(str)!=st.end() && j<f[i].size()-1){
                        st.erase(st.find(f[i]));
                        break;
                    }
                }
                str.push_back(f[i][j]);
            }
        }
        vector<string> ans;
        for(auto& p:st){
            ans.push_back(p);
        }
        return ans;
    }
};

第三题,滑动窗口

class Solution {
public:
    int balancedString(string s) {
        int st = 0;
        int ans = s.size();
        int cntQ = 0,cntW=0,cntE=0,cntR=0;
        for(int i = 0;i<s.size();i++){
            if(s[i]=='Q') cntQ++;
            else if(s[i]=='W') cntW++;
            else if(s[i]=='E') cntE++;
            else cntR++;
        }
        int avg = s.size()/4;
        for(int i = 0;i<s.size();i++){
            if(s[i]=='Q') cntQ--;
            else if(s[i]=='W') cntW--;
            else if(s[i]=='E') cntE--;
            else cntR--;
            while(st<=i && cntQ <= avg&&cntW<=avg&&cntE<=avg&&cntR<=avg){
                ans = min(ans,i-st+1);
                if(s[st]=='Q') cntQ++;
                else if(s[st]=='W') cntW++;
                else if(s[st]=='E') cntE++;
                else cntR++;
                st++;
                if(cntQ <= avg&&cntW<=avg&&cntE<=avg&&cntR<=avg){
                    ans = min(ans,i-st+1);
                }
            }
        }
        return ans;
    }
};

第四题动态规划

class Solution {
public:
    int jobScheduling(vector<int>& s, vector<int>& e, vector<int>& p) {
        vector<tuple<int,int,int>> vp(s.size());
        int n = s.size();
        for(int i = 0;i<n;i++){
            get<0>(vp[i]) = s[i];
            get<1>(vp[i]) = e[i];
            get<2>(vp[i]) = p[i];
        }
        vector<int> v(e);
        sort(v.begin(),v.end());
        sort(vp.begin(),vp.end(),[](const tuple<int,int,int>& p1,const tuple<int,int,int>& p2)->bool{
            return get<1>(p1)<get<1>(p2);
        });
        int dp[n];
        memset(dp,0, sizeof(dp));
        for(int i = 0;i<n;i++){
            if(i==0) dp[i] = get<2>(vp[i]);
            else{
                auto it = upper_bound(v.begin(),v.end(),get<0>(vp[i]))-v.begin();
                if(it==0){
                    dp[i] = max(dp[i-1],get<2>(vp[i]));
                }else{
                    dp[i] = max(dp[i-1],dp[it-1]+get<2>(vp[i]));
                }
            }
        }
        return dp[n-1];
    }
};
展开全部 16 讨论