第 29 场双周赛

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

5432. 去掉最低工资和最高工资后的工资平均值

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    double average(vector<int>& salary) {
        double res = 0;
        int curmax = salary[0], curmin = salary[0];
        for(auto s: salary) {
            curmax = max(curmax, s);
            curmin = min(curmin, s);
            res += s;
        }
        return (res-curmax-curmin) / ((salary.size()-2)*1.0);
    }
};

5433. n 的第 k 个因子

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int kthFactor(int n, int k) {
        int c = 0;
        for(int i=1; i<=n; i++) {
            if(n % i == 0) {
                c++;
                if(c == k) return i;
            }
        }
        return -1;
    }
};

5434. 删掉一个元素以后全为 1 的最长子数组

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
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n), right(n);
        int cur = 0;
        for(int i=0; i<n; i++) {
            if(nums[i] == 1) cur++;
            left[i] = cur;
            if(nums[i] == 0) cur = 0;
        }
        cur = 0;
        for(int i=n-1; i>=1; i--) {
            if(nums[i] == 1) cur++;
            if(nums[i] == 0) cur = 0;
            right[i-1] = cur;
        }
        int m = 0;
        for(int i=0; i<n; i++) {
            m = max(m, left[i] + right[i]);
        }
        if(m == n) return m-1;
        return m;
    }
};

5435. 并行课程 II

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
class Solution {
public:
    int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {
        vector<int> indegree(n+1, 0);
        vector<int> outdegree(n+1, 0);
        for(auto& p: dependencies) {
            indegree[p[1]]++;
            outdegree[p[0]]++;
        }
        queue<int> q;
        int res = 0;
        for(int i=1; i<=n; i++) {
            if(indegree[i] == 0) {
                q.push(i);
            }
        }
        while(!q.empty()) {
            int size = q.size();
            res ++;
            vector<int> f;
            for(int i=0; i<size; i++) {
                int c = q.front(); q.pop();
                f.push_back(c);
            }
            sort(f.begin(), f.end(), [&](int a, int b) {return outdegree[a] > outdegree[b];});
            int z = min(k, size);
            for(int i=0; i<z; i++) {
                int c = f[i];
                for(int j=0; j<dependencies.size(); j++) {
                    if(c == dependencies[j][0]) {
                        indegree[dependencies[j][1]]--;
                        if(indegree[dependencies[j][1]] == 0) q.push(dependencies[j][1]);
                    }
                }
            }
            if(k < size) {
                for(int i=k; i<size; i++) {
                    q.push(f[i]);
                }
            }
        }
        return res;
    }
};
Donate? comment?