Leetcode 第426场周赛分析总结

在这里插入图片描述

3370. 仅含置位位的最小整数

AC代码

class Solution {
public:
    int smallestNumber(int n) {
        int x = 1;
        while (x - 1 < n) {
            x <<= 1;
        }
        return x - 1;
    }
};

分析总结

也可以先直接获取n的长度，然后计算得到，这样时间复杂度由O(logn)优化为O(1)

在C++20中可以使用头文件中的std::bit_width函数，传入一个无符号整数，会返回其所需的最小位数（也就是最高位1的位数）

如果题目要求大于n的数，我的第一思路是判断n是不是2的幂次减1，分类讨论。灵神说不必如此，相当于我们已经拥有了求大于等于n的能力，那么对于大于n的情况，我们只需要求大于等于n+1，即在整数域上：> x相当于 >= x + 1，这是一种思维的转换能力。

class Solution {
public:
    int smallestNumber(int n) {
        return (1 << std::bit_width(static_cast<unsigned>(n))) - 1;
    }
};

3371. 识别数组中的最大异常值

AC代码

class Solution {
public:
    int getLargestOutlier(vector<int>& nums) {
        int n = nums.size();
        ranges::sort(nums);
        int sum = reduce(nums.begin(), nums.end());
        auto check = [&](int idx) -> bool {
            //[0, idx) [idx + 1, n)
            int seg_sum = sum - nums[idx];
            if (seg_sum % 2 != 0) return false;
            int target_sum = seg_sum / 2;
            int l = lower_bound(nums.begin(), nums.end(), target_sum) - nums.begin();
            int r = upper_bound(nums.begin(), nums.end(), target_sum) - nums.begin();
            //[l, r)
            if (l < r) {
                if (r <= idx || l > idx || r - l > 1 || l != idx) return true;
                else return false;
            } else {
                return false;
            }
        };
        for (int i = n - 1; i >= 0; --i) {
            if (check(i)) {
                return nums[i];
                break;
            }
        }
        return nums[0];
    }
};

分析总结

比赛过程中，我的第一想法是，整个数组的和等于异常值和剩下数字的和以及剩下的数字组成，那么我可以遍历异常值，判断剩下的数字是否满足情况，由于要快速判断一个数字是否存在，又忘记了使用哈希表，所以就先进行排序，从大往小遍历异常值，时间复杂度是O(nlogn)，空间复杂度O(1)。当时能够很快AC我还有点开心，觉得还是有点复杂的。

听了灵神的解析才发现自己马达马达达内。最重要的一点是判断一个数字是否出现应该考虑使用哈希表加速，其次我也没有进行数学抽象分析。要是考虑到哈希表就不会写出这么复杂的代码，通过复杂的二分判断数字是否存在。

class Solution {
public:
    int getLargestOutlier(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        unordered_map<int, int> cnt;
        for (auto x : nums) {
            sum += x;
            ++cnt[x];
        }
        int ans = numeric_limits<int>::min();
        for (auto x : nums) {
            --cnt[x];
            int t = sum - 2 * x;
            if (cnt[t]) {
                ans = max(ans, t);
            }
            ++cnt[x];
        }
        return ans;
    }
};

灵神留了一个思考题，考虑当数组已经有序的情况下如何使用空间复杂度为O(1)的算法解决问题。假设特殊数字的和是 $s$ ，异常值是 $x$ ，数组的和是 $s u m$ ，那么问题就是要找到 $2 s + x = s u m$ 的 $x$ ，要使得 $x$ 尽可能大，对于升序数组，我们从右到左遍历 $x$ ，从左往右遍历 $s$ ：

如果此时 $2 s + x > s u m$ ，则剩下的 $s$ （只会更大）都不满足情况，可以将 $x$ 向左移动；
如果此时 $2 s + x < s u m$ ，则剩下的 $x$ （只会更小）都不满足情况，可以将 $s$ 向右移动；

我本以为这就是一个简单的双指针，于是写了一下结果WA了。苦思冥想之际我发现，这个问题和普通的有序数组两数之和不同的地方在于，这里没有对称性。在两数之和中， $x + y > t a r g e t$ 和 $y + x > t a r g e t$ 是对称的，因此当两个指针相遇的时候我们可以判断数组中没有满足条件的数。但是对于这里而言， $2 s + x > s u m$ 不代表 $s + 2 x > s u m$ ，因此即使两个指针相遇仍然需要继续移动。难点就在于当指针相遇的时候应该移动哪个指针呢？

要是两个指针相遇的时候不等于 $s u m$ ，我们仍然可以按照上面的规则移动。可是如果当相遇的时候等于 $s u m$ ，应该移动哪一个指针呢？实践发现，移动右指针可以AC，移动左指针就会WA，我觉得AC可能是数据的缘故，并不表示正确性。

class Solution {
public:
    int getLargestOutlier(vector<int>& nums) {
        int n = nums.size();
        int sum = std::reduce(nums.begin(), nums.end());
        sort(nums.begin(), nums.end());
        int l = 0, r = n - 1;
        while (l < n && r >= 0) {
            if (l == r) {
                --r;
            }
            int t = 2 * nums[l] + nums[r];
            if (t > sum) {
                --r;
            } else if (t < sum) {
                ++l;
            } else {
                return nums[r];
            }
        }
        return -1;
    }
};

因此，我觉得对于这种没有对称性的情况，即使存在单调性，也并不适合使用双指针。

3372. 连接两棵树后最大目标节点数目 I

题目要求树上距离每个节点小于等于k的节点数目，在计算之前我们可以添加一个连边将树1和树2连接起来。经过分析不难发现这个连边方案是确定的：

树1上的点肯定是当前计算的目标节点，因为从其他节点出发只会导致距离目标节点更远
树2上的点应该是一个距离它小于等于k-1的节点数目最大的节点

那么问题就变成了，我们如何快速的计算树上一个节点到其他节点的距离。如果直接从某一个节点出发进行DFS（也可以BFS，不过使用DFS编码更简单，因为可以直接使用函数栈存储信息），时间复杂度是O(n)，由于需要对每个节点计算，总的时间复杂度是 $O(n^2+m^2)$

class Solution {
public:
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {
        auto get_dfs = [](decltype(edges1) edges) -> auto {
            int n = edges.size() + 1;
            vector graph(n, vector<int>());
            for (auto &&edge : edges) {
                auto u = edge[0], v = edge[1];
                graph[u].push_back(v);
                graph[v].push_back(u);
            }
            function<int(int, int, int)> dfs;
            dfs = [graph = std::move(graph), &dfs](int u, int fa, int d) -> int {
                if (d < 0) return 0;
                int ans = 1;
                for (auto v : graph[u]) {
                    if (v == fa) continue;
                    ans += dfs(v, u, d - 1);
                }
                return ans;
            };
            return dfs;
        };
        int maxn2 = 0;
        if (k > 0) {
            auto dfs = get_dfs(edges2);
            int n = edges2.size() + 1;
            for (int i = 0; i < n; ++i) {
                maxn2 = max(maxn2, dfs(i, -1, k - 1));
            }
        }
        auto dfs = get_dfs(edges1);
        int n = edges1.size() + 1;
        vector<int> ans(n, 0);
        for (int i = 0; i < n; ++i) {
            ans[i] = dfs(i, -1, k) + maxn2;
        }
        return ans;
    }
};

这里我想模仿灵神在视频中提到的闭包的技巧，这样可以将建图和dfs的逻辑绑定起来，避免在调用的时候传递参数。实际在实现的时候我有些疑惑到底怎样在闭包函数中捕获局部变量和自身。在动态内存分配的语言中，我们不需要考虑捕获，只要直接使用，就会有C++中引用捕获的语义，而语言自身通过引用计数保证了局部变量的内存不会被错误的释放。可是在C++中这一切都是确定性的，没有额外的垃圾回收，需要我们自己保证内存的安全性，就必须要考虑捕获的变量生存周期。

对于普通的局部变量，我们肯定不能进行引用捕获，当get_dfs函数返回后，dfs捕获的引用将会失效，因此这里我们使用移动捕获，通过移动拷贝将局部变量保存在dfs函数对象中。

对于需要返回的函数对象本身，因为我们需要在lambda表达式中访问自身，所以也需要捕获。可是如果进行值捕获的话，我们在初始化dfs的过程中dfs本身是一个不完全类型，是不能拷贝的（实际测试值捕获dfs会报错），因此只能进行引用捕获。但是捕获一个局部变量（dfs本身作为局部变量）不会造成悬挂引用吗？实际上的确不会，原因是返回值作为一个特殊的局部变量其实是保存在上一层函数栈中，不会随着函数的调用结束而释放内存，具体的细节和RVO（返回值优化）等C++底层技术和编译原理有关。

分析总结

比赛中最终这道题还是没有做出来，觉得不应该。其实核心的思路当时已经思考清楚了，但是在考虑实现计算距离每个节点不超过k的节点数目时，我想着应该使用一种时间复杂度更优秀的做法，因为对于每个节点都要计算，直接简单对每个节点遍历好像会超时。但实际上当时没有认真看数据范围，只是凭感觉会超时（要是问我为什么，只能说比赛的时候脑子抽了）。

想来想去好像没有更好的做法，就去问了一下GPT，它告诉我可以先以某个节点为根节点（例如0号节点）遍历树，得到每个节点的深度和父亲，然后再求解任意两个节点的最近公共祖先，然后任意两点之间的距离可以通过 $d i s [i] [j] = d e pt h [i] + d e pt h [j] - 2 * d e pt h [l c a [i] [j]]$ 计算，我一听很有道理呀，然后就哼哧哼哧实现，结果一直报错。下来再看才发现求解lca的时候写错了，修改以后就对了。

class Solution {
    vector<vector<int>> buildGraph(const vector<vector<int>>& edges) {
        int n = edges.size() + 1;
        vector graph(n, vector<int>());
        for (auto &&edge : edges) {
            int u = edge[0], v = edge[1];
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        return graph;
    }
    vector<vector<int>> getDis(const vector<vector<int>>& graph) {
        int n = graph.size();
        vector dis(n, vector<int>(n, 0));
        vector depth(n, 0);
        vector father(n, -1);
        vector lca(n, vector<int>(n, -1));

        function<void(int, int, int)> dfs;
        dfs = [&](int u, int fa, int d) {
            father[u] = fa;
            depth[u] = d;
            for (auto v : graph[u]) {
                if (v == fa) continue;
                dfs(v, u, d + 1);
            }
        };
        dfs(0, -1, 0);
        father[0] = 0;
        /*
        for (int i = 0; i < n; ++i) {
            cout << "depth " << i << ": " << depth[i] << endl;
        }
        */

        function<int(int, int)> get_lca;
        get_lca = [&](int u, int v) -> int {
            int ret = lca[u][v];
            if (ret != -1) return ret;
            if (depth[u] > depth[v]) {
                ret = get_lca(father[u], v);
            } else if (depth[u] < depth[v]) {
                ret = get_lca(father[v], u);
            } else {
                if (u == v) {
                    ret = u;
                } else {
                    ret = get_lca(father[u], father[v]);
                }
            }
            lca[u][v] = ret;
            lca[v][u] = ret;
            return ret;
        };

        for (int i = 0; i < n; ++i) {
            dis[i][0] = 1;//(i, i)
            for (int j = i + 1; j < n; ++j) {
                int d = depth[i] + depth[j] - 2 * depth[get_lca(i, j)];
                //cout << depth[i] << " " << depth[j] << " " <<depth[get_lca(i, j)] << endl;
                //cout << i << "---" << j << " : " << d << endl;
                dis[i][d]++;
                dis[j][d]++;
            }
        }
        
        return dis;
    }
public:
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {
        auto graph1 = buildGraph(edges1);
        auto graph2 = buildGraph(edges2);
        int n = graph1.size();
        int m = graph2.size();
        vector ans(n, 0);
        auto dis1 = getDis(graph1);
        auto dis2 = getDis(graph2);
        int max_target2 = [&]() -> int {
            int t = min(m, k);
            int ret = -1;
            for (int i = 0; i < m; ++i) {
                ret = max(ret, reduce(dis2[i].begin(), dis2[i].begin() + t));
            }
            return ret;
        }();
        //cout << "max_target2 = " << max_target2 << endl;
        int t = min(n, k + 1);
        for (int i = 0; i < n; ++i) {
            ans[i] = reduce(dis1[i].begin(), dis1[i].begin() + t) + max_target2;
        }
        return ans;
    }
};

求解lca的时候用了记忆化。实际上认真思考这种方式的时间复杂度也是 $O(n^2)$ 的，甚至常数更大。

比赛的时候编码想着把建图和搜索的逻辑封装起来，通过参数传递。与闭包的方式比起来，这种方式耦合度更低，但是对于这个具体的场景会有参数传递的麻烦，可见编码的高级技巧可以简化工作量，闭包函数作为一种比较高级的编码技巧我还是不太熟悉。

另一方面也暴露出我对树上搜索还是不够熟悉，这种简单的操作本来应该直接写出来的。

3373. 连接两棵树后最大目标节点数目 II

这道题比赛的时候完全没有看，觉得主要的难点相比第三题在于，意识到一个树上距离某个节点距离为偶数的所有节点形成的集合互相满足距离为偶数，剩下的节点形成了另一个互相满足距离为偶数的集合。

那么在树1上，答案就固定的分成两种，我们只需要对节点进行染色分类，记录每种颜色节点的数目和每个节点的颜色。剩下的问题是如何和树2进行连边：

我们可以从距离树1目标节点x为偶数（例如从x出发）连边，目标就是找到树2上距离为奇数的节点数目最大的节点
也可以从距离树1目标节点x为奇数（例如从x的某个相连的节点出发）连边，目标就是找到树2上距离为偶数的节点数目最大的节点

无论哪种情况，这个数目都是固定的，和x的选取没有关系，其实就是两种颜色集合大小的较大值。

class Solution {
public:
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
        auto aux = [](decltype(edges1) edges) -> pair<vector<int>, vector<int>> {
            int n = edges.size() + 1;
            vector graph(n, vector<int>());
            for (auto &&edge : edges) {
                int u = edge[0], v = edge[1];
                graph[u].push_back(v);
                graph[v].push_back(u);
            }

            vector colors(n, -1);
            vector cnt(2, 0);

            function<void(int,int,int)> dfs;
            dfs = [&](int u, int fa, int c) {
                colors[u] = c;
                cnt[c]++;
                for (auto v : graph[u]) {
                    if (v == fa) continue;
                    dfs(v, u, c ^ 1);
                }
            };
            dfs(0, -1, 0);

            return {colors, cnt};
        };
        auto [colors1, cnt1] = aux(edges1);
        auto [colors2, cnt2] = aux(edges2);

        int maxn2 = max(cnt2[0], cnt2[1]);
        int n1 = edges1.size() + 1;
        vector ans(n1, 0);
        for (int i = 0; i < n1; ++i) {
            ans[i] = cnt1[colors1[i]] + maxn2;
        }
        
        return ans;
    }
};