第 194 场周赛

Posted on | In , | |
Words count in article: 656 | Reading time ≈ 3

1486. 数组异或操作

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int xorOperation(int n, int start) {
        int res = 0;
        for(int i=0; i<n; i++) {
            res ^= start+2*i;
        }
        return res;
    }
};

1487. 保证文件名唯一

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
class Solution {
public:
    vector<string> getFolderNames(vector<string>& names) {
        unordered_set<string> past;
        unordered_map<string, int> next;
        for(string &i: names) {
            if(past.find(i) == past.end()) {
                past.insert(i);
                next[i] = 1;
            } else {
                int num = next[i];
                int original_size = i.size();
                string s = i;
                while(1) {
                    while(s.size() > original_size) s.pop_back();
                    s += '(' + to_string(num) + ')';
                    ++num;
                    if(past.find(s) == past.end()) {
                        next[i] = num;
                        next[s] = 1;
                        past.insert(s);
                        i = s;
                        break;
                    }
                }
            }
        }
        return names;
    }
};

1488. 避免洪水泛滥

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:
    vector<int> avoidFlood(vector<int>& rains) {
        int rains_size = rains.size();
        vector<int> ans(rains_size, 1);
        unordered_map<int, int> last_rain;
        set<int> sun;
        for(int i=0; i<rains_size; i++) {
            int ii = rains[i];
            if(ii == 0) {
                sun.insert(i);
                continue;
            }
            if(last_rain.find(ii) != last_rain.end()) {
                auto p = sun.lower_bound(last_rain[ii]);
                if(p == sun.end()) return {};
                ans[*p] = ii;
                sun.erase(p);
            }
            last_rain[ii] = i;
            ans[i] = -1;
        }   
        return ans;
    }
};

1489. 找到最小生成树里的关键边和伪关键边

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
public:  
    int p[110];
    
    int find(int a) {
        if (a != p[a]) p[a] = find(p[a]);
        return p[a];
    }

    int work1(int n, vector<vector<int>>& edges, int k) { // 不选第k条边的最小生成树的权重
        for (int i = 0; i < n; i ++ ) p[i] = i;
        int cost = 0, cnt = 0;
        for (auto& e:edges) {
            if (e[3] == k) continue;  //  如果是第k条边，则跳过
            int f1 = find(e[1]), f2 = find(e[2]);
            if (f1 != f2) {
                cost += e[0];
                cnt ++;
                if (cnt == n - 1) break;
                p[f1] = f2;
            }
        }
        if (cnt == n - 1) return cost;
        else return INT_MAX;
    }
    
    int work2(int n, vector<vector<int>>& edges, int k) { // 一定选第k条边的最小生成树的权重
        for (int i = 0; i < n; i ++ ) p[i] = i;
        int cost = 0, cnt = 0;
        
        for (auto& e : edges) {  // 先向第k条边加入到集合中
            if (e[3] == k) {
                cost += e[0];
                cnt ++;
                p[e[1]] = e[2];
                break;
            }
        }
        
        for (auto& e: edges) {
            int f1 = find(e[1]), f2 = find(e[2]);
            if (f1 != f2) {
                cost += e[0];
                cnt ++;
                if (cnt == n - 1) break;
                p[f1] = f2;
            }
        }
        if (cnt == n - 1) return cost;
        else return INT_MAX;
    }
    
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {        
        int m = edges.size();
        for (int i = 0; i < m; i ++ ) {
            auto& e = edges[i];
            swap(e[0], e[2]);
            e.push_back(i);
        }
        sort(edges.begin(), edges.end());
        int min_cost = work1(n, edges, -1);   // 求出最小生成树权重
        vector<vector<int>> ans(2);
        for (int i = 0; i < m; i ++ ) {
            if (work1(n, edges, i) > min_cost) ans[0].push_back(i);  // 判断是否为关键边
            else if (work2(n, edges, i) == min_cost) ans[1].push_back(i);  // 判断是否为伪关键边
        } 
        return ans;
        
    }
};
Donate? comment?