Leetcode 第 418 场周赛题解

题目1：3309. 连接二进制表示可形成的最大数值

思路

枚举 6 种连接情况，返回其中的最大值。

代码

class Solution {
public:int maxGoodNumber(vector<int>& nums) {int a = nums[0];int b = nums[1];int c = nums[2];return max({getNum(a, b, c), getNum(a, c, b), getNum(b, a, c),getNum(b, c, a), getNum(c, a, b), getNum(c, b, a)});}// 辅函数 - 求 a、b、c 的连接数值int getNum(int a, int b, int c) {string s = trans(a) + trans(b) + trans(c);ranges::reverse(s);int res = 0;for (int i = 0; i < s.length(); i++)res += (s[i] - '0') * (int)pow(2, i);return res;}// 辅函数 - 转换成二进制表示string trans(int x) {string s;while (x) {s.insert(s.begin(), x % 2 + '0');x /= 2;}return s;}
};

复杂度分析

时间复杂度：O(logX)，其中 X=127 是元素取值上限。

空间复杂度：O(1)。

题目2：3310. 移除可疑的方法

思路

从 k 开始深度优先搜索，标记所有可以访问到的点。题目把这些点叫做可疑方法。

遍历 invocations，如果发现从「非可疑方法」到「可疑方法」的边，则无法移除可疑方法，返回数组 [0,1,2,⋯,n−1]。

否则，可以移除所有可疑方法。把没有被标记为可疑方法的点加入答案。

代码

class Solution {
public:vector<int> remainingMethods(int n, int k,vector<vector<int>>& invocations) {vector<vector<int>> grid(n);// 建图for (vector<int>& invocation : invocations) {int from = invocation[0], to = invocation[1];grid[from].push_back(to);}vector<bool> suspicious(n, false); // 可疑方法function<void(int)> dfs = [&](int x) {suspicious[x] = true;for (int& y : grid[x])if (suspicious[y] == false)dfs(y);};dfs(k);for (vector<int>& invocation : invocations) {int from = invocation[0], to = invocation[1];if (suspicious[from] == false && suspicious[to] == true) {// 有【非可疑方法】->【可疑方法】的边，无法移除可疑方法vector<int> ans(n);iota(ans.begin(), ans.end(), 0);return ans;}}// 移除所有可疑方法vector<int> ans;for (int i = 0; i < n; i++)if (suspicious[i] == false)ans.push_back(i);return ans;}
};

复杂度分析

时间复杂度：O(n+m)，其中 m 是数组 invocations 的长度。

空间复杂度：O(n+m)，其中 m 是数组 invocations 的长度。

题目3：3311. 构造符合图结构的二维矩阵

思路

题解：https://leetcode.cn/problems/construct-2d-grid-matching-graph-layout/solutions/2940423/gou-zao-fen-lei-tao-lun-by-tsreaper-qxqc/

代码

class Solution {
public:vector<vector<int>> constructGridLayout(int n, vector<vector<int>>& edges) {// 建图并记录节点度数vector<vector<int>> grid(n);vector<int> degree(n, 0);for (vector<int>& edge : edges) {grid[edge[0]].push_back(edge[1]);grid[edge[1]].push_back(edge[0]);degree[edge[0]]++;degree[edge[1]]++;}int minDegree = *min_element(degree.begin(), degree.end());int maxDegree = *max_element(degree.begin(), degree.end());// 先求出矩阵最左边一列vector<int> vec;if (minDegree == 1) {// 情况 1：一行的矩阵for (int i = 0; i < n; i++)if (degree[i] == 1) {vec.push_back(i);break;}} else {int S;for (int i = 0; i < n; i++)if (degree[i] == 2) {S = i;break;}vec.push_back(S);if (maxDegree <= 3) {// 情况 2：两行的矩阵vec.push_back(degree[grid[S][0]] == 2 ? grid[S][0]: grid[S][1]);} else {// 情况 3：矩阵至少三行int now = grid[S][0], last = S;while (degree[now] != 2) {vec.push_back(now);for (int& fn : grid[now])if (degree[fn] <= 3 && fn != last) {last = now;now = fn;break;}}vec.push_back(now);}}int row = vec.size(), col = n / row;vector<vector<int>> ans(row, vector<int>(col, 0));vector<bool> visited(n, false);for (int i = 0; i < row; i++) {ans[i][0] = vec[i];visited[vec[i]] = true;}// 每次枚举一列，找出每个元素还不在矩阵里的邻居放在右边for (int j = 0; j + 1 < col; j++)for (int i = 0; i < row; i++)for (int& fn : grid[ans[i][j]])if (!visited[fn]) {ans[i][j + 1] = fn;visited[fn] = true;}return ans;}
};

复杂度分析

时间复杂度：O(n+m)，其中 m 是数组 edges 的长度。

空间复杂度：O(n+m)，其中 m 是数组 edges 的长度。

题目4：3312. 查询排序后的最大公约数

思路

题解：https://leetcode.cn/problems/sorted-gcd-pair-queries/solutions/2940415/mei-ju-rong-chi-qian-zhui-he-er-fen-pyth-ujis/

代码

class Solution {
public:vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {int mx = *max_element(nums.begin(), nums.end());vector<int> cnt(mx + 1, 0);for (int& num : nums)cnt[num]++;vector<long long> cnt_gcd(mx + 1, 0);for (int i = mx; i > 0; i--) {int c = 0;for (int j = i; j <= mx; j += i) {c += cnt[j];// gcd 是 2i,3i,4i,... 的数对不能统计进来cnt_gcd[i] -= cnt_gcd[j];}// c 个数选 2 个，组成 c * (c - 1) / 2 个数对cnt_gcd[i] += (long long)c * (c - 1) / 2;}vector<long long> preSum(mx + 1);preSum[0] = cnt_gcd[0];for (int i = 1; i < preSum.size(); i++)preSum[i] = preSum[i - 1] + cnt_gcd[i];vector<int> ans(queries.size());for (int i = 0; i < queries.size(); i++)ans[i] = upper_bound(preSum.begin(), preSum.end(), queries[i]) - preSum.begin();return ans;}
};

复杂度分析

时间复杂度：O(n+(U+q)logU)，其中 n 是数组 nums 的长度，U=max(nums)，q 是数组 queries 的长度。

空间复杂度：O(U)，其中 U=max(nums)，返回值不计入。