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

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

image.png

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

说一下周赛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
展开全部 16 讨论