第 218 场周赛（如果喜欢记得点赞并关注作者噢~~~）
题目1：5617. 设计 Goal 解析器
思路：模拟
代码：
class Solution {
public:
string interpret(string s) {
int n = s.size();
int i = 0;
string ret = "";
while(i < n) {
if(s[i] == '(' && s[i + 1] == ')') {
i += 2;
ret += "o";
} else if(s[i] == '(') {
i += 4;
ret += "al";
} else {
i++;
ret += "G";
}
}
return ret;
}
};
复杂度分析：
题目2：5618. K 和数对的最大数目
思路：哈希表
代码：
class Solution {
public:
int maxOperations(vector<int>& nums, int k) {
unordered_map<int, int> mp;
int ret = 0;
for(int x : nums) {
if(mp[k - x]) {
mp[k - x]--;
ret++;
} else {
mp[x]++;
}
}
return ret;
}
};
复杂度分析：
题目3：5620. 连接连续二进制数字
思路：模拟
代码：
class Solution {
public:
const int M = 1e9 + 7;
int concatenatedBinary(int n) {
int ret = 0;
int p = 1;
for (int i = 1; i <= n; ++i) {
while (p <= i) { // 相当于求log(i)
p *= 2;
}
ret = ((long long)ret * p + i) % M;
}
return ret;
}
}; 复杂度分析：
题目4：5619. 最小不兼容性
思路：状压DP
代码：
const int INF = 0x3f3f3f3f;
int memo[65536], v[16];
class Solution {
int n, k, sz;
vector<int> nums;
int solve(int state) {
if (memo[state] != -1)
return memo[state];
// 边界条件：当前集合刚好包含n/k个元素，不需要继续划分
if (__builtin_popcount(state) == sz) {
int idx = 0;
for (int i = 0; i < n; ++i) {
if (state & (1 << i)) {
// 将包含的元素存入分组
v[idx++] = i;
}
}
for (int i = 0; i + 1 < sz; ++i) {
// 一个分组有两数相同，则说明是不满足要求的分组
if (nums[v[i]] == nums[v[i + 1]]) {
return memo[state] = INF;
}
}
return memo[state] = nums[v[n / k - 1]] - nums[v[0]];
}
int ans = INF;
// 优化二：子集枚举优化
for (int sub = state - 1; sub; sub = (sub - 1) & state) {
if (__builtin_popcount(sub) % sz != 0)
continue;
// left 和 right 分别表示将当前集合再分为两个子集
int left = solve(sub);
// 优化三：如果左边的最优值已经达到了当前总和的最优值，则不需要继续计算右边。
if (left >= ans)
continue;
int right = solve(state ^ sub);
ans = min(ans, left + right);
}
return memo[state] = ans;
}
public:
int minimumIncompatibility(vector<int>& nums, int k) {
n = nums.size();
sz = n / k;
// 优化一：每个子集的大小为1，不兼容性显然为0，总和也是0。
// 这种情况的筛除非常重要，因为它需要最多的枚举次数。
if (sz == 1)
return 0;
sort(nums.begin(), nums.end());
vector<int> cnt(n + 1);
for (int num : nums) {
// 记录每个数字出现的次数，若大于组数则说明不能分组
cnt[num]++;
if (cnt[num] > k)
return -1;
}
this->k = k; // 更新全局变量
this->nums = nums;
for (int i = 0; i < (1 << n); ++i)
memo[i] = -1;
return solve((1 << n) - 1);
}
}; 复杂度分析：
全部评论
(0) 回帖