第 179 场周赛

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

1374. 生成每种字符都是奇数个的字符串

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    string generateTheString(int n) {
        if(n & 1){
            return string(n,'a');
        }else{
            return string(n-1,'a') + "b";
        }
    }
};

1375. 灯泡开关 III

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int numTimesAllBlue(vector<int>& light) {
        int m=0, cnt=0;
        for(int i=0; i<light.size(); i++) {
            m = max(light[i], m);
            if(m == i+1) cnt++;
        }
        return cnt;
    }
};

1376. 通知所有员工所需的时间

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 numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        vector<vector<int>> my_son(manager.size());
        for(int i=0;i<manager.size();i++){
            if(manager[i]!=-1) my_son[manager[i]].push_back(i);
        }
        queue<pair<int,int>> Q;
        Q.push({headID,0});
        int max=0;
        pair<int,int> cur;
        while(!Q.empty()){
            cur=Q.front();
            Q.pop();
            if(cur.second>max) max=cur.second;
            for(auto it:my_son[cur.first]){
                Q.push({it,cur.second+informTime[cur.first]});
            }
        }
        return max;
    }
};

1377. T 秒后青蛙的位置

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
class Solution {
public:
    struct node {
        int id;
        double p;
        int t;
        node(int a, double b, int c) {
            id = a; p = b; t = c;
        }
    };
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        vector<int> vis(n+1);
        vector<vector<int>> gh(n+1);
        for(auto& edge: edges) {
            gh[edge[0]].push_back(edge[1]);
            gh[edge[1]].push_back(edge[0]);
        } 
        queue<node> q;
        q.push(node(1, 1.0, 0));
        vis[1] = 1;
        while(!q.empty()) {
            node u = q.front(); q.pop();
            if(u.id == target && u.t == t) return u.p;
            int sz = 0;
            for(int i=0; i<gh[u.id].size(); i++) {
                if(vis[gh[u.id][i]] == 0) {
                    sz++;
                }
            }
            if(u.t < t) {
                int flag = 0;
                for(int i=0; i<gh[u.id].size(); i++) {
                    if(vis[gh[u.id][i]] == 0) {
                        flag = 1;
                        vis[gh[u.id][i]] = 1;
                        q.push(node(gh[u.id][i], u.p/sz, u.t+1));
                    }
                }
                if(flag == 0) {
                    q.push(node(u.id, u.p, u.t+1));
                }
            }
        }
        return 0.0;
    }
};
Donate? comment?