# Leetcode 第194场周赛题解

# Problem A - 数组异或操作 (opens new window)

模拟。

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

# Problem B - 保证文件名唯一 (opens new window)

按要求进行模拟。

参考代码(C++)
class Solution {
public:
    vector<string> getFolderNames(vector<string>& names) {
        unordered_set<string> s;
        unordered_map<string, int> dict;
        vector<string> ans;
        for (string name : names) {
            if (!s.count(name)) {
                ans.emplace_back(name);
                s.insert(name);
                dict[name] = 1;
            } else {
                int idx = dict[name];
                while (s.count(name + "(" + to_string(idx) + ")"))
                    idx++;
                string t = name + "(" + to_string(idx) + ")";
                s.insert(t);
                ans.emplace_back(t);
                dict[name] = idx + 1;
                dict[t] = 1;
            }
        }
        return ans;
    }
};
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

# Problem C - 避免洪水泛滥 (opens new window)

首先一次遍历找到每一个下雨天下雨的池塘上一次下雨的日子。然后开始从最后一天倒推:

  • 如果这一天下雨,那么需要检查下雨的池塘是否为空。
    • 如果不为空,说明有无法解决的冲突,无解。
    • 如果为空,那么将其置为满。同时,如果这一池塘之前还下过雨,就把之前下雨的记录加入大根堆中,等待消除矛盾。
  • 如果这一天不下雨,并且大根堆非空(有需要消除的矛盾),就取出堆顶元素(最靠近的一个下雨天),将对应的池塘排空。

如果最后大根堆非空,代表还有未消除的矛盾,无解。

总时间复杂度为O(nlogn)O(n\log n)

参考代码(C++)
class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        int n = rains.size();
        vector<int> ans(n);
        unordered_map<int, int> pos;
        vector<int> last(n, -1);
        unordered_map<int, bool> full;
        for (int i = 0; i < n; ++i) {
            if (rains[i] > 0) {
                if (pos.count(rains[i]))
                    last[i] = pos[rains[i]];
                pos[rains[i]] = i;
            }
        }
        priority_queue<pair<int, int>> pq;
        for (int i = n - 1; i >= 0; --i) {
            if (rains[i] > 0) {
                if (full[rains[i]])
                    return {};
                ans[i] = -1;
                full[rains[i]] = true;
                if (last[i] == -1)
                    continue;
                else
                    pq.push({last[i], rains[i]});
            } else {
                if (pq.empty())
                    ans[i] = 1;
                else {
                    pair<int, int> top = pq.top();
                    pq.pop();
                    ans[i] = top.second;
                    full[top.second] = false;
                }
            }
        }
        if (!pq.empty())
            return {};
        return ans;
    }
};
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

# Problem D - 找到最小生成树里的关键边和伪关键边 (opens new window)

本题与CF160D - Edges in MST相同。

# 方法一 暴力枚举

首先用Kruskal算法进行一次常规的MST,得到最小权值。

对于每条边,再进行两次额外的MST:

  • 强制从该边开始MST(直接将该边加入生成树的边集):如果最后的权值大于最小权值,说明该边既不是关键边,也不是非关键边
  • 删除该边后再MST:如果最后的权值大于最小权值,或者图不连通,说明该边为关键边;否则该边可能为非关键边(结合上面一次的结果可以最终判断该边是否是非关键边)。

该方法的时间复杂度为O(E2)O(E^2),在本题的数据范围内可以通过。

参考代码(C++)
struct Edge {
    int u, v, w, idx;

    bool operator<(const Edge &other) const {
        return w < other.w || (w == other.w && u < other.u) || (w == other.w && u == other.u && v < other.v);
    }
};

class UnionFind {
    int n;
    vector<int> parent, size;

public:
    UnionFind(int n) {
        this->n = n;
        parent = vector<int>(n);
        size = vector<int>(n, 1);
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }

    int find(int idx) {
        if (parent[idx] == idx)
            return idx;
        return parent[idx] = find(parent[idx]);
    }

    bool is_connected(int a, int b) {
        return find(a) == find(b);
    }

    void connect(int a, int b) {
        int fa = find(a), fb = find(b);
        if (fa != fb) {
            if (size[fa] > size[fb]) {
                parent[fb] = fa;
                size[fa] += size[fb];
            } else {
                parent[fa] = fb;
                size[fb] += size[fa];
            }
        }
    }

    int components() {
        vector<bool> is_root(n);
        for (int i = 0; i < n; ++i)
            is_root[find(i)] = true;
        int ans = 0;
        for (int i = 0; i < n; ++i)
            ans += is_root[i];
        return ans;
    }
};

class Solution {
    int n;
    vector<Edge> e;
    vector<vector<int>> edges;

    int MST(int prioritize, int ignore) {
        UnionFind uf(n);
        int ans = 0;
        if (prioritize != -1) {
            vector<int> v = edges[prioritize];
            uf.connect(v[0], v[1]);
            ans += v[2];
        }
        for (Edge ei : e) {
            if (ei.idx == prioritize || ei.idx == ignore)
                continue;
            if (!uf.is_connected(ei.u, ei.v)) {
                uf.connect(ei.u, ei.v);
                ans += ei.w;
            }
        }
        if (uf.components() > 1)
            return INT_MAX;
        return ans;
    }

public:
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>> &edges) {
        this->n = n;
        this->edges = edges;
        for (int i = 0; i < edges.size(); ++i)
            e.emplace_back(Edge{edges[i][0], edges[i][1], edges[i][2], i});
        sort(e.begin(), e.end());
        int mst = MST(-1, -1);
        vector<int> critical, non_critical;
        for (int i = 0; i < edges.size(); ++i) {
            int with = MST(i, -1);
            int without = MST(-1, i);
            if (with > mst)
                continue;
            if (without > mst)
                critical.emplace_back(i);
            else
                non_critical.emplace_back(i);
        }
        return {critical, non_critical};
    }
};
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

# 方法二 Tarjan+并查集

维护一个所有顶点的并查集。将所有边按权值升序排序,然后将权值相同的边作为一组,从权值最小的组开始逐组处理。

每一组处理过程中,如果某条边的两个顶点已经在同一连通分量中,该边一定不在任何最小生成树中。否则该边至少是在一个最小生成树中,也即至少为非关键边。

接下来,将这些边加入邻接表构成新的图,然后在新的图上使用Tarjan算法找出所有的桥边。桥边一定是关键边。

最后,合并新连通的连通分量,也即“缩点”。

运行过程的瓶颈是排序,所以总时间复杂度为O(ElogE)O(E\log E)

参考代码(C++)
#define INF 0x3f3f3f3f

struct Edge {
    int from, to, value;

    Edge(int from, int to, int value) : from(from), to(to), value(value) {}
};

class Graph {
    int n, idx;
    vector<Edge> edges;
    vector<vector<int>> adj;
    vector<int> dfn, low, ans, parent, size;
    vector<bool> vis;

    int find(int a) { return parent[a] == a ? a : parent[a] = find(parent[a]); }

    void connect(int a, int b) {
        int fa = find(a), fb = find(b);
        if (fa != fb) {
            if (size[fa] > size[fb]) {
                parent[fb] = fa;
                size[fa] += size[fb];
            } else {
                parent[fa] = fb;
                size[fb] += size[fa];
            }
        }
    }

    void tarjan(int u) {
        dfn[u] = low[u] = ++idx;
        for (int ei : adj[u]) {
            if (vis[ei])
                continue;
            vis[ei] = true;
            Edge &e = edges[ei];
            int cv = find(e.from) + find(e.to) - u;
            int v = find(cv);
            if (!dfn[v]) {
                tarjan(v);
                if (dfn[u] < low[v])
                    ans[ei] = 0;
            }
            low[u] = min(low[u], low[v]);
        }
    }

public:
    explicit Graph(int n) : n(n) {
        adj = vector<vector<int >>(n);
        dfn = vector<int>(n, -1);
        low = vector<int>(n, INF);
        parent = vector<int>(n);
        size = vector<int>(n, 1);
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }

    void add_edge(int u, int v, int w) {
        adj[u].emplace_back(edges.size());
        adj[v].emplace_back(edges.size());
        edges.emplace_back(u, v, w);
    }

    vector<vector<int>> solve() {
        int m = edges.size();
        vector<int> order(m);
        for (int i = 0; i < m; ++i)
            order[i] = i;
        sort(order.begin(), order.end(),
             [&](int i, int j) { return edges[i].value < edges[j].value; });
        ans = vector<int>(m, -1);
        vis = vector<bool>(m);
        for (int start = 0; start < m; ++start) {
            int end = start;

            // 将相同权值的边归为一组进行处理
            while (end + 1 < m &&
                   edges[order[end + 1]].value == edges[order[start]].value)
                end++;

            // 清除处理上一组时连的边
            for (int k = start; k <= end; ++k) {
                auto[u, v, w] = edges[order[k]];
                int fu = find(u), fv = find(v);
                adj[fu].clear();
                adj[fv].clear();
                dfn[fu] = dfn[fv] = 0;
            }

            // 连上新边
            // 如果该边的两个端点已经在一个连通分量中,该边一定不在最小生成树中
            for (int k = start; k <= end; ++k) {
                auto[u, v, w] = edges[order[k]];
                int fu = find(u), fv = find(v);
                if (fu != fv) {
                    adj[fu].emplace_back(order[k]);
                    adj[fv].emplace_back(order[k]);
                    ans[order[k]] = 1;
                }
            }

            // Tarjan算法找出桥边
            // 桥边是关键边,其余非桥边是非关键边
            idx = 0;
            for (int k = start; k <= end; ++k) {
                auto[u, v, w] = edges[order[k]];
                int fu = find(u), fv = find(v);
                if (!dfn[fu])
                    tarjan(fu);
                if (!dfn[fv])
                    tarjan(fv);
            }

            // 合并连通分量,也就是所谓的“缩点”
            for (int k = start; k <= end; ++k) {
                auto[u, v, w] = edges[order[k]];
                connect(u, v);
            }
            start = end;
        }

        vector<vector<int>> ret(2);
        for (int i = 0; i < m; ++i)
            if (~ans[i]) ret[ans[i]].emplace_back(i);
        return ret;
    }
};

class Solution {
public:
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>> &edges) {
        Graph g(n);
        for (auto v : edges)
            g.add_edge(v[0], v[1], v[2]);
        return g.solve();
    }
};
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139