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

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

image.png

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

展开讨论
力扣 (LeetCode)发起于 2019-10-20
最近编辑于 2019-10-20

2,3,4题解

这比赛之间怎么难度差距这么大啊,竟然出现了树状数组和离散化,字典树(后来发现根本不存在的),代码差点写崩。万年没写数据结构了,差点bug挑不出来,最后还发现这玩意根本不是字典树。太智障了。。。结果第三题就没时间做了。。。
下面是2,3,4的题解,代码有点丑,内存瞎🐔儿开。

第二题

一开始脑残字典树(代码懒得删除了),最后发现暴力就好。时间浪费太多了。。。

class Solution {
public:
    
    int s[10004][30];
    bool end[10004*30];
    int cnt = 0;
    void insert(string str) {
        // cout << str << endl;
        int len = str.length();
        int r = 0;
        int num;
        for(int i = 0; i < len; ++i) {
            if(str[i] == '/')    num = 27;
            else num = str[i]-'a';
            if(s[r][num]) r = s[r][num];
            else { 
                s[r][num] = ++cnt;
                r = s[r][num];
            }
        }
        end[r] = true;
        
    }
    
    vector<string> bfs() {
        queue<pair<int, string> > que;
        que.push(make_pair(0,""));
        vector<string> v;
        while(!que.empty()) {
            pair<int,string> p = que.front();
            que.pop();
            
            for(int i = 0; i < 28; ++i) {
                string t = p.second;
                if(s[p.first][i]) {
                    if(i == 27) {
                        t += "/";
                    } else 
                        t += 'a'+i;
                    if(end[s[p.first][i]]) {
                         v.push_back(t);
                    } else 
                        que.push(make_pair(s[p.first][i], t));
                }
                
            }
            
        }
        return v;
    }
    set<string> has;
    vector<string> removeSubfolders(vector<string>& folder) {
        for(auto& it: folder) {
            
            // insert(it);
            has.insert(it);
        }
        // return bfs();
        vector<string> v;
        for(int i = 0; i < folder.size(); ++i) {
            string t ="";
            bool flag = true;
            for(int j = 0; j < folder[i].length()-1; ++j) {
                t += folder[i][j];
                if(folder[i][j+1] == '/') {
                    if(has.count(t)) {
                        // cout << t << endl;
                        flag =false;
                        break;
                    }
                }
                    
            }
            if(flag)
                v.push_back(folder[i]);
        }
        return v;
    }
};

第三题:

做法:统计多于n/4个的字符alps,以及它们分别多出的数目mores。
二分最小长度len。
二分check方法:遍历字符串,找到是否存在长度为len的子串中包含alp,且每个alp的数目大于等于各自more。这里需要前缀和优化一下,能快速统计。

class Solution {
public:
    int cnt[4];
    map<char, int> mp;
    int len = 0;
    int pre[1000005][4];
    vector<int> v;
    
    int n;
    bool ok(int x) {
        
        for(int i = 0; i+x <= n; i++) {
            int sum = 0;
            bool flag = true;
            for(int j = 0; j < v.size(); ++j) {
                if(!(pre[i+x][v[j]]-pre[i][v[j]] >= cnt[v[j]]))
                    flag = false;
            }
            
            if(flag) {
                
                return true;
            }
        }
        return false;
    }
    int balancedString(string s) {
        n = s.length();
        mp['Q'] = 0; mp['W'] = 1; mp['E'] = 2; mp['R'] = 3;
        for(int i = 0; i < s.length(); ++i) {
            cnt[mp[s[i]]]++;
            

            for(int j = 0; j < 4; ++j)
                pre[i+1][j] = pre[i][j];
            pre[i+1][mp[s[i]]]++;
            
        }
        int biao = s.length()/4;
        // cout << biao << endl;
        for(int i = 0; i < 4; ++i) {
            // cout << i << " " << cnt[i] << endl;
            cnt[i] -= biao;
            if(cnt[i] > 0) {
                len += cnt[i];
                v.push_back(i);
            }
        }
      
        int l = len, r = s.length(), ans = r;
        while(l <= r) {
            int mid = (l+r) >> 1;
            if(ok(mid)) {
                // cout << ans << endl;
                ans = mid;
                r = mid-1;
            } else 
                l = mid+1;
                
        }
        return ans;
        
    }
};

第四题

离散化时间,用树状数组统计[1,time]时间内的最大收益。
对于一个[start,end],更新树状数组的end,更新方法:update(end, max(1,start)+profit)

代码中的dp是多余的。

class Solution {
public:
    
    // 当前时刻i的最大profit  dp[i] = max{dp[j]+v};
    vector<int> v;
    int cnt;
    int star[50005],endt[50005];
    int dp[1000000];
      struct node {
        int be, ed;
          
        int pro;
        
    } t[50005];
    static bool cmp(node i, node j) {
        return j.ed == i.ed ? i.be < j.be : i.ed < j.ed;
    }
    int h[1000000];
    int N;
    int lowbit(int x)
     {
         return x&(-x);
     }
      void update(int x, int v)
    {
        while(x<=N)
        {
            h[x]=v;
            for(int i=1;i<lowbit(x);i<<=1)
            h[x]=max(h[x],h[x-i]);
            x+=lowbit(x);
        }
        return ;
    }
    int findans(int begin,int end)
    {
        int ans=0;
        while(end>=begin)
        {
            ans=max(ans,h[end]);
            end--;
            for(;end-lowbit(end)>=begin;end-=lowbit(end))
            ans=max(ans,h[end]);
        }


        return ans;
    }
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        for(int i = 0; i < n; ++i)
            t[i].be = startTime[i], t[i].ed = endTime[i], t[i].pro = profit[i];
        sort(t, t+n, cmp);
        for(auto&it : endTime) 
            v.push_back(it);
        for(auto&it : startTime)
            v.push_back(it);
        sort(v.begin(), v.end());
        v.erase( unique(v.begin(),v.end()), v.end());
        // a.erase(unique(a.begin(),a.end()),a.end())
        for(int i = 0; i < n; ++i) {
            endt[i] = int(lower_bound(v.begin() , v.end() , t[i].ed) - v.begin())+1;
            star[i] = int(lower_bound(v.begin() , v.end() , t[i].be) - v.begin())+1;
         
        }
     
	    N = v.size();
        int mx = 0;
        for(int i = 0; i < n; ++i) {
            dp[endt[i]] = max(mx, findans(1, star[i])+t[i].pro);
            update(endt[i], dp[endt[i]]);
        
            // cout << t[i].ed << " dp:" << dp[endt[i]] <<" " << t[i].be << " dp:" << dp[star[i]] <<" " << t[i].pro << endl;
            mx = max(mx, dp[endt[i]]);
        }
        return mx;    
    }
    /*
    1 2 3 4 6 . 3 5 10 6 9
    0 1 2 3 5   3 4 7  5 6
    */
};
3
展开全部 16 讨论