Weekly Contest 159

Posted on | In , | |
Words count in article: 471 | Reading time ≈ 2

1232. Check If It Is a Straight Line

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& c) {
        if(c.size() <= 2) return true;
        
        double k = ((c[1][1] - c[0][1])*1.0) / ((c[1][0] - c[0][0])*1.0);
        
        for(int i = 2; i<c.size(); i++){
            double cur = ((c[i][1] - c[0][1])*1.0) / ((c[i][0] - c[0][0])*1.0);
            
            if( cur != k ) return false;
        }
        
        return true;
    }
};

1233. Remove Sub-Folders from the Filesystem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
bool cmp(string& a, string& b){
    return a.size() < b.size();
}

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        sort(folder.begin(), folder.end(), cmp);
        vector<string> ret;
        
        for(auto str: folder){
            bool flag = true;
            
            for(auto retstr: ret){
                bool ff = true;
                int i;
                for(i=0; i<retstr.size(); i++){
                    if(retstr[i] != str[i]){
                        ff = false;
                        break;
                    }
                }
                if(ff && str[i] == '/'){
                    flag = false;
                    break;
                }
                    
            }
            
            if(flag)
                ret.push_back(str);
        }
        return ret;
    }
};

1234. Replace the Substring for Balanced String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    int balancedString(string s)
    {
        int targetCounter = s.length() / 4;
        
        vector<int> counters(128, 0);
        
        for (char c: s)
            counters[c]++;
        
        counters['Q'] = counters['Q'] - targetCounter;
        counters['W'] = counters['W'] - targetCounter;
        counters['E'] = counters['E'] - targetCounter;
        counters['R'] = counters['R'] - targetCounter;
        
        if (counters['Q'] == 0 &&
            counters['W'] == 0 &&
            counters['E'] == 0 &&
            counters['R'] == 0)
            return 0;
        
        int left = 0;
        int right = 0;
        int len = s.length() + 1;
        
        while (right < s.length())
        {
            counters[s[right]]--;
            
            ++right;
            
            if (counters['Q'] <= 0 &&
                counters['W'] <= 0 &&
                counters['E'] <= 0 &&
                counters['R'] <= 0)
            {
                while (counters['Q'] <= 0 &&
                       counters['W'] <= 0 &&
                       counters['E'] <= 0 &&
                       counters['R'] <= 0)
                {
                    counters[s[left]]++;

                    ++left;
                }

                len = std::min(len, right - left + 1);
            }
        }
        
        return len;
        
    }
};

1235. Maximum Profit in Job Scheduling

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<vector<int>> jobs;
        for(int i=0; i<n; i++){
            jobs.push_back({endTime[i], startTime[i], profit[i]});
        }
        sort(jobs.begin(), jobs.end());
        map<int, int> dp = {{0, 0}};
        for(auto& job: jobs){
            int cur = prev(dp.upper_bound(job[1]))->second + job[2];
            if(cur > dp.rbegin()->second)
                dp[job[0]] = cur;
        }
        return dp.rbegin()->second;
    }
};
Donate? comment?