第 193 场周赛

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

5436. 一维数组的动态和

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        vector<int> res = nums;
        for(int i=1; i<res.size(); i++)
            res[i] += res[i-1];
        return res;
    }
};

5437. 不同整数的最少数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        map<int, int> mp;
        for(auto i: arr) mp[i]++;
        vector<int> cot;
        for(auto i: mp) {
            cot.push_back(i.second);
        }
        sort(cot.begin(), cot.end());
        int i=0;
        for(i=0; i<cot.size(); i++) {
            if(k >= cot[i]) {
                k -= cot[i];
            } else {
                break;
            }
        }
        return cot.size()-i;
        
    }
};

5438. 制作 m 束花所需的最少天数

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
typedef long long ll;

class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        int n = bloomDay.size();
        if (n / k < m)
            return -1;
        int l = 1, r = 1e9;
        auto check = [&](int x) {
            vector<bool> flower(n);
            for (int i = 0; i < n; ++i)
                if (bloomDay[i] <= x)
                    flower[i] = true;
            int bunch = 0, curr = 0;
            for (int i = 0; i < n; ++i) {
                if (flower[i])
                    curr++;
                else {
                    bunch += curr / k;
                    curr = 0;
                }
            }
            bunch += curr / k;
            return bunch;
        };
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid) < m)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return l;
    }
};

5188. 树节点的第 K 个祖先

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
class TreeAncestor {
public:
    vector<int> dep;
    vector<int> f[20];
    vector<vector<int>> G;
    void DFS(int u){
        for(int i = 1; i < 20; i += 1) f[i][u] = f[i - 1][f[i - 1][u]];
        for(int v : G[u]){
            dep[v] = dep[u] + 1;
            f[0][v] = u;
            DFS(v);
        }
    }
    TreeAncestor(int n, vector<int>& parent) {
        G.resize(n);
        dep.resize(n);
        for(int i = 0; i < 20; i += 1) f[i].resize(n);
        for(int i = 1; i < n; i += 1) G[parent[i]].push_back(i);
        DFS(0);
    }
    
    int getKthAncestor(int node, int k) {
        if(dep[node] < k) return -1;
        for(int i = 19; ~i; i -= 1)
            if(k >= (1 << i)){
                k -= 1 << i;
                node = f[i][node];
            }
        return node;
    }
};

/**
 * Your TreeAncestor object will be instantiated and called as such:
 * TreeAncestor* obj = new TreeAncestor(n, parent);
 * int param_1 = obj->getKthAncestor(node,k);
 */
Donate? comment?