5617. 设计 Goal 解析器
按题意模拟，基础题。
class Solution {
public:
string str;
string interpret(string command) {
for(int i = 0; i < command.size();i++){
if(command[i] == 'G') str += 'G';
else if(i != command.size() - 1 && command[i] == '(' && command[i + 1] == ')') str += 'o';
else if(command[i] == 'a') str += "al";
}
return str;
}
};
5618. K 和数对的最大数目
经典技巧题，比较好的解法是排序之后双指针求解。当然可以用map投机就很好写了。
双指针求解
class Solution {
public:
int maxOperations(vector<int>& nums, int k) {
int N = nums.size();
sort(nums.begin(), nums.end());
int ans = 0;
int l = 0, r = nums.size() - 1;
while (l<r) {
int s = nums[l]+nums[r];
if (s == k) l++, r--, ans++;
else if (s < k) l++;
else r--;
}
return ans;
}
};
map
class Solution {
public:
int maxOperations(vector<int>& nums, int k) {
map<int, int> mp;
int ans = 0;
for(int x: nums) {
if(mp[k - x] > 0) {
mp[k - x] -= 1;
++ ans;
}else mp[x] += 1;
}
return ans;
}
};
5620. 连接连续二进制数字
从后往前求每个数的贡献值即可
class Solution {
public:
int concatenatedBinary(int n) {
long long mod = pow(10,9) + 7;
long long ans = 0, base = 1;
for(int i = n; i >= 1; --i) {
n = i;
while(n > 0) {
long long x = n & 1;
n >>= 1;
ans = (ans + base * x) % mod;
base = base * 2 % mod;
}
}
return (int)ans;
}
};
5619. 最小不兼容性
数组和权值范围最大只有16，因为要把数组分成k个子集，那么每个子集大小就是n/k。
第一种方法：
通过set判断子集中的重复元素，搜索+剪枝即可，具体见代码
class Solution {
public:
int N;//总个数
int K;//子集个数
int M;//每个子集中的元素个数
int ans;//求解值
void dfs(vector<int>& nums,int index,vector<set<int>> &vSet,int have){
/*
index 表示当前数组取到的值
vSet 表示子集
*/
if(index>=N){//当取到最后一位时终止，判断
ans=min(ans,have);
return;
}
for(int i=0;i<K;i++){
if(vSet[i].empty()){// 子集个数为空
vSet[i].insert(nums[index]);
dfs(nums,index+1,vSet,have);//取下个元素
vSet[i].erase(nums[index]);
break;//当有出现大于K个相同数时，不可能
}
if(vSet[i].size()<M&&vSet[i].find(nums[index])==vSet[i].end()){//当前子集个数未满且当前元素子集中未存在
if(have + nums[index] - *vSet[i].rbegin()>=ans){
//剪枝 当前数已经比最小值大
continue;
}
int nhave = have + nums[index] - *vSet[i].rbegin();
vSet[i].insert(nums[index]);
dfs(nums,index+1,vSet,nhave);
vSet[i].erase(nums[index]);
}
}
}
int minimumIncompatibility(vector<int>& nums, int k) {
N=nums.size();
sort(nums.begin(),nums.end());
ans = INT_MAX;
K=k;
M=N/K;
vector<set<int>> vSet(k);
dfs(nums,0,vSet,0);
if(ans == INT_MAX){
return -1;
}
return ans;
}
};
第二种方法：
首先二进制枚举求出所有合法的子集，这样的子集个数不会太多。
可以通过二进制枚举求出所以合法的子集，同状态压缩。
然后写一个搜索+剪枝即可。
class Solution {
public:
int ans, n, sz;
vector<pii> vs;
void dfs(int c, int cnt, int sta, int res, int k) {
if(cnt == k) {
ans = min(ans, res);
return ;
}
if(res >= ans) return ;
for(int i = c; i < sz; ++i) {
if((sta & vs[i].se) == 0) dfs(i + 1, cnt + 1, sta | vs[i].se, res + vs[i].fi, k);
}
}
int minimumIncompatibility(vector<int>& nums, int k) {
vector<int> cnt(20, 0);
int flag = 1;
ans = INF;
for(int x: nums) {
++ cnt[x];
if(cnt[x] > k) flag = 0;
}
if(flag == 0) return -1;
n = nums.size();
int sta = 1 << n;
sort(all(nums));
for(int i = 1; i < sta; ++i) {
int cnt = 0, Mx = 0, Mn = 100, las = -1;
for(int j = 0; j < n; ++j) {
if(i & (1 << j)) {
++ cnt;
Mx = max(Mx, nums[j]);
Mn = min(Mn, nums[j]);
if(nums[j] == las) cnt = -100;
las = nums[j];
}
}
if(cnt * k == n) {
vs.emplace_back(make_pair(Mx - Mn, i));
}
}
sort(all(vs));
sz = vs.size();
dfs(0, 0, 0, 0, k);
vs.clear();
return ans;
}
};