算法竞赛＞力扣＞周赛 | weekly-contest-457

3606. 优惠券校验器

解题思路

筛选、排序、构建。

代码实现

vector<string> validateCoupons(vector<string>& code, vector<string>& businessLine, vector<bool>& isActive) {
    int n = code.size();
    unordered_map<string, int> mp = {
        {"electronics", 1},
        {"grocery", 2},
        {"pharmacy", 3},
        {"restaurant", 4}
    };
    vector<pair<string, string>> cs;
    // 校验标识符
    auto validateCode = [](const string& s) {
        if (s.empty())return false;
        for (char c : s)
            if (!isdigit(c) && !isalpha(c) && c != '_') return false;
        return true;
    };
    // 筛选
    for (int i = 0; i < n; i++) {
        if (!isActive[i] || !mp.count(businessLine[i]) || !validateCode(code[i])) continue;
        cs.emplace_back(code[i], businessLine[i]);
    }
    // 排序
    sort(cs.begin(), cs.end(), [&](auto& s1, auto& s2) {
        if (s1.second != s2.second) return mp[s1.second] < mp[s2.second];
        return s1.first < s2.first;
    });
    // 构建
    vector<string> r;
    for (auto& [c,_] : cs) r.push_back(c);
    return r;
}

时间复杂度 $O(n+n\log n)$，空间复杂度 $O(n)$。

3607. 电网维护

解题思路

为每个连通图构建小根堆，记录每个电站所属堆，堆顶即为编号最小的电站，离线则从堆顶移除。

代码实现

vector<int> processQueries(int c, vector<vector<int>>& connections, vector<vector<int>>& queries) {
    // 构建邻接矩阵
    vector<vector<int>> g(c + 1);
    for (auto e : connections)
        g[e[0]].push_back(e[1]), g[e[1]].push_back(e[0]);

    // 构建堆的操作
    vector<int> f(c + 1, -1);
    vector<priority_queue<int, vector<int>, greater<int>>> hp;
    priority_queue<int, vector<int>, greater<int>> pq;
    function<void(int)> dfs = [&](int x) {
        // 记录节点所在堆的编号
        f[x] = hp.size();
        pq.push(x);
        // 将后续节点加入到当前堆
        for (const int y : g[x])
            if (f[y] < 0)dfs(y);
    };

    // 构建堆
    for (int i = 1; i <= c; i++) {
        if (f[i] >= 0)continue;
        dfs(i);
        hp.emplace_back(move(pq));
    }

    vector<int> res;
    vector<bool> off(c + 1, false);

    // 查询
    for (auto q : queries) {
        int x = q[1];
        // 离线操作
        if (q[0] == 2) {
            off[x] = true;
            continue;
        }
        // 检修且未离线
        if (!off[x]) {
            res.emplace_back(x);
            continue;
        }
        // 检修且离线
        auto& h = hp[f[x]];
        while (!h.empty() && off[h.top()])h.pop();
        res.push_back(h.empty() ? -1 : h.top());
    }
    return res;
}

时间复杂度 $O(c+n+q\log c)$，空间复杂度 $O(c+n)$，其中 $n$ 为连接数，$q$ 为查询数。

3608. 包含 K 个连通分量需要的最小时间

解题思路

并查集，初始 n 个并查集/连通块。将边按照时间从大到小排序，逐步合并并查集，直到连通块数小于 k 时返回当前边的时间。

代码实现

int minTime(int n, vector<vector<int>>& edges, int k) {
    // 并查集
    int c = n;
    vector<int> f(n);
    iota(f.begin(), f.end(), 0);
    // 并查集-查找
    function<int(int)> find = [&](int x) {
        if (f[x] != x)f[x] = find(f[x]);
        return f[x];
    };
    // 并查集-合并
    auto merge = [&](int a, int b) {
        const int fa = find(a), fb = find(b);
        if (fa == fb)return;
        f[fa] = fb, c--;
    };
    // 按时间从大到小排序
    sort(edges.begin(), edges.end(), [&](auto& v1, auto& v2) {
        return v1[2] > v2[2];
    });
    // 逐步合并并查集
    for (auto& e : edges) {
        // 合并
        merge(e[0], e[1]);
        // 连通块小于k
        if (c < k)return e[2];
    }
    return 0;
}

时间复杂度 $O(n+m\log m+m\log n)$，空间复杂度 $O(n)$，其中 $n$ 为节点数， $m$ 为边数。

原文链接

算法竞赛>力扣>周赛 | weekly-contest-457