Leetcode 第 418 场周赛题解
Leetcode 第 418 场周赛题解
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),返回值不计入。
原文地址:https://blog.csdn.net/ProgramNovice/article/details/142726903
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!