LC Weekly Contest 426

https://leetcode.com/contest/weekly-contest-426/

3370. Smallest Number With All Set Bits

class Solution {
public:
    int smallestNumber(int n) {
        int ans = 0;
        int idx = 31;
        while (!((n >> idx) & 1)) idx -= 1;
        return pow(2, idx + 1) - 1;
    }
};

Time Complexity: O(31)
Space: O(1)

3371. Identify the Largest Outlier in an Array

class Solution {
public:
    int getLargestOutlier(vector<int>& nums) {
        vector<int> record(2001, 0);
        int total = 0;
        for (auto &x: nums) {
            record[x + 1000] += 1;
            total += x;
        }
        for (int outlier = 1000; outlier >= -1000; outlier--) {
            if (record[outlier + 1000] < 1) continue;
            record[outlier + 1000] -= 1;
            for (int sum = 1000; sum >= -1000; sum--) {
                if (record[sum + 1000] < 1) continue;
                total = total - outlier - sum;
                if (total == sum) return outlier;
                total = total + outlier + sum;
            }
            record[outlier + 1000] += 1;
        }
        return INT_MAX;
    }
};

Time Complexity: O(1000^2)
Space: O(2000)

這題可以在紀錄時透過將所有的值平移 +1000 就可以避免使用 unordered_map 加速運算的速度。

3372. Maximize the Number of Target Nodes After Connecting Trees I

class Solution {
public:
    int findNeighbor(int root, int step, vector<vector<int>> &edges) {
        int ans = 0;
        queue<pair<int, int>> q;
        q.push({-1, root});
        while (step--) {
            int sz = q.size();
            ans += sz;
            while (sz--) {
                auto [pre, cur] = q.front();
                q.pop();
                for (auto &x: edges[cur]) {
                    if (x == pre) continue;
                    q.push({cur, x});
                }
            }
        }
        return ans;
    }

    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {
        int m = edges1.size() + 1, n = edges2.size() + 1;
        vector<vector<int>> graph1(m), graph2(n);
        for (auto &x: edges1) {
            graph1[x[0]].push_back(x[1]);
            graph1[x[1]].push_back(x[0]);
        }
        for (auto &x: edges2) {
            graph2[x[0]].push_back(x[1]);
            graph2[x[1]].push_back(x[0]);
        }

        int mxNeighbor = 0;
        for (int i = 0; i < n; i++) {
            mxNeighbor = max(mxNeighbor, findNeighbor(i, k, graph2));
        }

        vector<int> ans(m);
        for (int i = 0; i < m; i++) {
            ans[i] = findNeighbor(i, k + 1, graph1) + mxNeighbor;
        }
        return ans;
    }
};

Time Complexity: O(n^2)
Space: O(n)

在這題我們可以得出在 Tree2 上找到一點，此點有最多距離小於等於 k - 1 的鄰居數量。然後在 Tree1 上就所有點都去找自己的鄰居再加上這個 Tree2 上計算出來的值就可以了。

3373. Maximize the Number of Target Nodes After Connecting Trees II

class Solution {
public:
    pair<int, int> prepare(int pre, int cur, vector<vector<int>> &edges, vector<unordered_map<int, pair<int, int>>> &nodes) {
        pair<int, int> total = {0, 1};
        for (auto &x: edges[cur]) {
            if (x == pre) continue;
            auto [odd, even] = prepare(cur, x, edges, nodes);
            nodes[cur][x] = {even, odd};
            total.first += even;
            total.second += odd;
        }
        return total;
    }
    void findNeighbor(int pre, int cur, vector<vector<int>> &edges, vector<unordered_map<int, pair<int, int>>> &nodes, vector<pair<int, int>> &nei, pair<int, int> up) {
        pair<int, int> total = up;
        total.second += 1;
        for (auto &x: edges[cur]) {
            if (x == pre) continue;
            total.first += nodes[cur][x].first;
            total.second += nodes[cur][x].second;
        }
        nei[cur] = total;
        for (auto &x: edges[cur]) {
            if (x == pre) continue;
            total.first -= nodes[cur][x].first;
            total.second -= nodes[cur][x].second;
            findNeighbor(cur, x, edges, nodes, nei, {total.second, total.first});
            total.first += nodes[cur][x].first;
            total.second += nodes[cur][x].second;
        }
    }
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
        int m = edges1.size() + 1, n = edges2.size() + 1;
        vector<vector<int>> graph1(m), graph2(n);
        vector<unordered_map<int, pair<int, int>>> nodes1(m), nodes2(n);
        for (auto &x: edges1) {
            graph1[x[0]].push_back(x[1]);
            graph1[x[1]].push_back(x[0]);
        }
        for (auto &x: edges2) {
            graph2[x[0]].push_back(x[1]);
            graph2[x[1]].push_back(x[0]);
        }

        prepare(-1, 0, graph1, nodes1);
        prepare(-1, 0, graph2, nodes2);

        vector<pair<int, int>> nei1(m), nei2(n);
        findNeighbor(-1, 0, graph1, nodes1, nei1, {0, 0});
        findNeighbor(-1, 0, graph2, nodes2, nei2, {0, 0});

        int mxNei = 0;
        for (int i = 0; i < n; i++) {
            mxNei = max(mxNei, nei2[i].first);
        }
        vector<int> ans(m);
        for (int i = 0; i < m; i++) {
            ans[i] = nei1[i].second + mxNei;
        }

        return ans;
    }
};

Time Complexity: O(n + m)
Space: O(n + m)

我好菜，人家一下就解出來了，啊我怎麼搞這麼久還寫有夠長。