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

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

image.png

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

共 16 个回复

第三题翻译的,愣是一直都没读懂,这个中括号一个又一个的。。是JOJO看多了吗??

6

白天有点事,晚上补的题目。先上总结:本次周赛除了hard是陈题以外,其他的质量都很高,推荐:

  • 缀点成线
    判断每个点到第一个点的斜率是否相同即可,需要注意横线和竖线的情况。时间复杂度 O(n)O(n)

  • 删除子文件夹
    这道题乍一看有一个直接的反应是 trie 树,用 trie 树也确实是正解。但是这道题有复杂度稍高但是代码量更少的做法。如果我们把所有字符串排序,会看到类似下面的场景:

    /a
    /a/b
    /a/bc/c
    /a/bc/d

    其实排序字符串以后,根目录必然会在子目录上面,而且和子目录是连着的。所以,开始的时候,我们以第一个目录作为我们的根目录,对于后续的每一个目录,判断根目录是否是他的根目录。如果是,那么就跳过这个文件夹,否则我们更新根目录为当前目录。

    做法时间复杂度的瓶颈在于排序字符串,为 O(nmlog(n))O(nmlog(n))nn 为字符串的数量,mm 为字符串的长度,不同于数字排序,字符串之间的比较也是有代价的,计算复杂度的时候也需要考虑进去。

    而如果使用 trie 树的话,我们可以把 log(n)log(n) 部分优化掉,复杂度为 O(nm)O(nm)

  • 替换子串得到平衡字符串
    应该是本场最好的题目,题目让我们替换最小的子串,换句话说就是保留最长的串,使得所有字母的数量不大于 n/4n/4,这里之所以说串而不是子串了,是因为我们保留的串是有可能左右各一半的。

    使用双指针,开头分别指向字符串的头和尾,我们先把左指针尽量右移,使得所有字母的数量不大于 n/4n/4,然后开始右移右指针,同样使用到的字母总数不大于 n/4n/4,最后记录现在的使用的字符串长度。

    然后我们每次把左指针往回移动一个,那么右指针也可以继续向左试探,记录现在的情况下的最大字符串长度。
    最后我们遍历完所有的情况,就可以得到最后的结果了。时间复杂度为 O(n)O(n)

  • 规划兼职工作
    非常老的题目了,甚至都怀疑是不是可以在前面的题目里找到一模一样的原题。做法也很经典:首先把所有范围为 10910^9 的坐标都离散化为从 [1,n][1,n] 的点,由于总共就 55 万的区间,所以 nn 是小于 1010 万的。那么对于每个任务,也可以转变为 [start,end,profit][start,end,profit] 的三元组。对于每个三元组,我们把这个任务记录在 endend 上,具体做法是用一个dict记录每一个时间上的所有任务。

    做好预处理以后,剩下的工作就是 dp 了, dp[i]dp[i] 表示从 0i0-i 时刻,做任务能拿到的最大价值,那么首先 dp[i]>=dp[i1]dp[i]>=dp[i-1]。接着,如果 i 时刻有任务结束的话(我们记录在dict里了),dp[i]=max(dp[i],dp[start]+profit)dp[i] = max(dp[i],dp[start]+profit) ,会有这样的转移。最后在dp数组里取max就是结果了。总体复杂度是 nlog(n)nlog(n),也就是瓶颈在离散化的排序上。

细节和代码等后面的详细题解吧。

6

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

说一下周赛1,2,4题的解答:

第一题:

不用多说,直接考虑相邻点的斜率

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& co) {
        if(co.size() <= 2) return true;
        int x, y;
        x = co[1][0] - co[0][0];
        y = co[1][1] - co[0][1];
        for(int i = 1 ;i < co.size();++i){
               if(((co[i][0] - co[i-1][0])*y != (co[i][1] - co[i-1][1])*x)) return false;
        }
        return true;
    }
};
第二题:

看起来很复杂,实际上有一个比较巧妙的方法:先排序,然后遍历一遍folder,然后用一个0,1数组记录一下s要删除的子文件,封装了一个函数isc(a, b) 返回b是a的子目录:

class Solution {

    public:
    bool isc(string b, string a){
        if(a.length() < b.length()) return 0;
        else {
            int i;
             for( i =0 ;i<b.length();++i)
                 if(a[i] != b[i]) return 0;
            if(i < a.length() && a[i] != '/') return 0;
        }
       
        return 1;
    }
    
    vector<string> removeSubfolders(vector<string>& folder) {
        vector<string> ans;
        int u[40005] ={0};
        sort(folder.begin(), folder.end());
        int l=folder.size();
        int tmp=0;
        for(int i =1 ;i < folder.size();++i){
          if(isc(folder[tmp], folder[i])){
              u[i] = 1;
       
          }else{
              tmp=i;
              
          }
        }
        
        for(int i =0 ;i < folder.size();++i){if(u[i] == 0)  ans.push_back(folder[i]);}
        return ans;
    }
};
第四题

首先按左端点sort一下:
然后利用dp的思想:a[i]表示已经决定参加编号为i的活动以及i之后的活动,可以获得的最大收益(i是必须参加的)。最后返回的应该是max(a[0], a[1],.....a[n-1])。转移方程也很好写: a[i] = profit[i] + max(a[j+1], a[j+2],...);(j表示第一个在i后与i不冲突的s工作),这里需要注意的是在求max的时候应该用一个数组b记录一下每次的s最大值,否则亲测c会TLE:

class Solution {
    private:
    int a[50004];
    int b[50004];
 
    public:
    void fsort (vector<int>& a, vector<int>& b , vector<int>& c,int left, int right)
{
    if(left>=right) return ;
        
    int x=a[left],i=left,j=right,y =b[left],z=c[left];
    while(i<j)
    {
        while(i<j&&a[j]>=x)
            j--;
        a[i]=a[j];
        b[i] = b[j];
        c[i]= c[j];
        while(i<j&&a[i]<=x)
            i++;
        a[j]=a[i];
        b[j] = b[i];
        c[j] = c[i];
    }
    a[i]=x;b[i] = y;c[i] =z;
        
    fsort(a,b,c,left,i-1);
    fsort(a,b,c,i+1,right);
}
    
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
              int len = startTime.size();
        if(len == 0) return 0;
        if(len == 1) return profit[0];
         int max__ = -1;
        fsort(startTime, endTime, profit, 0, len - 1);
      // for(int i =0 ;i < len;++i) cout << startTime[i] << endTime[i] << profit[i] <<endl;
        
        a[len-1] = profit[len-1];
        b[len -1] = a[len-1];
      //  b[len-1] = profit[len-1];
        for(int i = len-2;i >= 0;--i){
           int  j, f = 0;
            for(j = i+1;j < len;++j){
               if(startTime[j] >= endTime[i]) {f = 1;break;}
           }
            if(f == 0) {a[i] = profit[i];b[i] = max(a[i], b[i+1]);}
            else{
                int max_ = -1;
                //for(int k = j;k < len;++k)
                  //  max_ = max(a[k],max_ );
                
                
              // cout << "!" <<  profit[i] << " " <<max_<<endl;
                a[i] = profit[i] + b[j];
                b[i] = max(b[i+1], a[i]);
            }
            
         
        }
       // for(int i = 0;i<len;++i) cout << a[i]<<" ";
       
                for(int k = 0;k < len;++k)
                    max__ = max(a[k],max__ );
        return max__;
        
    }
};

.

3

5230. 缀点成线

原题链接

取出前两个点根据 y=kx+by = kx + b 求解直线方程,再将后续的点套入方程中判断是否在直线上。

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        x1, y1 = coordinates[0][0], coordinates[0][1]
        x2, y2 = coordinates[1][0], coordinates[1][1]
        # 求斜率 k
        if x1 == x2:
            k = 0
        else:
            k = (y2 - y1) / (x2 - x1)
        b = y1 - k * x1
        
        for i in range(2, len(coordinates)):
            x = coordinates[i][0]
            y = coordinates[i][1]
            if k * x + b != y:
                return False
            
        return True

5231. 删除子文件夹

原题链接

思路

folder 按字典序排序,如果目录 xfolder 中存在根目录,那么这个根目录必定在 x 之前。

  1. 将第一个目录作为根目录
  2. 从第二个目录开始遍历,判断 folder[i] 是否以当前根目录为前缀:
    • 是:folder[i] 是子目录,跳过该目录,不记录到结果中
    • 否:将当前根目录更新为 folder[i]

ps: 作为根目录时结尾加个 /,不然 "/a/b/c" 就是 "/a/b/ca" 的前缀了。

实现

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        # 排序
        folder.sort()
        res = [folder[0]]
        # 将第一个目录设为当前根目录
        root = folder[0] + "/"
        
        for i in range(1, len(folder)):
            # 是否以 root 为前缀
            if not folder[i].startswith(root):
                # 不是子目录
                root = folder[i] + "/" # 更新根目录
                res.append(folder[i])
                
        return res

5232. 替换子串得到平衡字符串

原题链接

思路

题目要求 QWER 每个字符都需要出现 n / 4 次,那么统计这 4 个字母出现的次数,超出 n / 4 部分的即为需要删除的字母,即只要在字符串中找到包含所有多出字母的一个子串即可。用双指针圈定最终的子串范围。

实现

class Solution:
    def balancedString(self, s: str) -> int:
        length = len(s)
        n = length // 4
        
        m = {"Q": 0, "W": 1, "E": 2, "R": 3}
        dp = [[0, 0, 0, 0] for i in range(length)]
        c_count = [0 for _ in range(4)]
        need = [0 for _ in range(4)]
        
        # 计算每个字母出现的个数
        for i in range(length):
            c = s[i]
            index = m[c]
            c_count[index] += 1
            dp[i] = [c_count[0], c_count[1], c_count[2], c_count[3]]
            
        # 计算多出来的字母个数(即需要删除的个数)
        all_zero = True
        for i in range(4):
            count = c_count[i]
            if count > n:
                need[i] = count - n
                if need[i] != 0:
                    all_zero = False
        # 如果全为 0,说明不需要替换
        if all_zero:
            return 0
                
        # 双指针,确定右指针所在的最小位置
        last = length - 1
        for i in range(length):
            if dp[i][0] >= need[0] and dp[i][1] >= need[1] and dp[i][2] >= need[2] and dp[i][3] >= need[3]:
                last = i
                break  
        
        i = 0
        j = last
        res = last + 1
        while i < length and j < length:
            # 两指针中间区域不满足要求,右指针右移
            if dp[j][0] - dp[i][0] < need[0] or dp[j][1] - dp[i][1] < need[1] or dp[j][2] - dp[i][2] < need[2] or dp[j][3] - dp[i][3] < need[3]:
                j += 1
            # 满足要求,左指针尽量向右移,看是否可以缩短字串长度
            else:
                res = min(j - i, res)
                i += 1
                
        return res

5233. 规划兼职工作

原题链接

思路

动态规划。在开始计算之前,先把题目给出的数据整理一下。将 [startTime[i], endTime[i], profit[i]] 整理为数组,并按 startTime[i] - endTime[i] - profit[i]] 排序。

dp[i] 表示完成第 i 份工作所能获得的最大收益。假设有第 x 份工作(x < i):

  • 如果 xi 时间上不重合,表示即可完成工作 x 又可以完成工作 i,那么有:dp[i] = max(dp[i], dp[x] + profit[i])
  • 如果 xi 在时间上重合了,那么将无法完成工作 x

由此可见,dp[i] 的值取决于在它前面所有与之时间不重合的工作收益,即:

dp[i] = max(dp[0], dp[1], ..., dp[j]) + profit[i] (`j``i` 之前最后一个与之时间区域不重合的工作)

但是,如果每次都遍历 0 ~ j 必然会超时,所以需要记录下时间区域不重合的工作所在的最大位置。

实现

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        length = len(startTime)
        times = [[0, 0, 0] for _ in range(length)]
        for i in range(length):
            times[i][0] = startTime[i]
            times[i][1] = endTime[i]
            times[i][2] = profit[i]
        times.sort() # 排序
                
        dp = [0 for i in range(length)]
        
        res = 0
        s = 0
        pos = 0 # 标记位置
        for i in range(length):
            for j in range(pos, i):
                # 区间不重合
                if times[i][0] >= times[j][1]:
                    # 移动 pos 的位置
                    if j == pos:
                        pos += 1
                    s = max(s, dp[j])
             
            dp[i] = s + times[i][2]
            res = max(res, dp[i])
                              
        return res
2

第二道题超时,这个用例怎么这么长

为什么我一直觉得第三题测试用例有的答案错了???

第一题直接用方程式判断,直线方程的一般式 ax+by+c=0; 那么可以令a=y2-y1,则b=x1-x2,c=-ay1-by2;取两个点得到a,b,c,然后判断每个点代入方程是否成立即可;

class Solution {
public:
   bool checkStraightLine(vector<vector<int>>& coordinates) {
        int len=coordinates.size();
        if(len==2){
            return true;
        }
        //取两个点求a,b,c
        int a=coordinates[1][1]-coordinates[0][1];
        int b=coordinates[0][0]-coordinates[1][0];
        int c=-b*coordinates[0][1]-a*coordinates[0][0];
        //每个点代入方程进行计算判断方程成立于否
        for(int i=2;i<len;++i){
            if(a*coordinates[i][0]+b*coordinates[i][1]+c!=0){//判断 ax+by+c=0成立与否
                return false;//不满足方程
            }
        }
        return true;//全部满足
    }
};

第四题划了,二分+贪心最后发现应该是个dp。。。

第一题

  • 过同一点的斜率,选第一个点
class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        sk = set()
        if len(coordinates) == 2:
            return True
        sx, sy = coordinates[0]
        for x, y in coordinates[1:]:
            if x == sx:
                sk.add(float("inf"))
            else:
                sk.add((y - sy) / (x - sx))
        return len(sk) == 1

第二题

  • 排序
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        ans = []
        folder.sort()
        while folder:
            ans.append(folder.pop(0))
            while folder and folder[0].startswith(ans[-1] + "/"):
                folder.pop(0)
        return ans

第三题

  • 滑动窗口
class Solution:
    def balancedString(self, s: str) -> int:
        t = len(s) // 4
        co = collections.Counter(s)
        dy = {} # 确定有哪些字符一定要换成别的
        for c in co:
            if co[c] > t:
                dy[c] = co[c] - t
        if not dy:
            return 0
        cur = {}

        def check():
            for c in dy:
                if cur.get(c, 0) < dy[c]:
                    return False
            return True
        i = j = 0 # 从i到j的滑动窗口中包含所有的需要变化的字符
        ans = len(s)
        while j < len(s):
            cur[s[j]] = cur.get(s[j], 0) + 1
            j += 1
            while check():
                ans = min(ans, j - i)
                cur[s[i]] = cur.get(s[i], 0)-1
                i += 1

        return ans