LeetCode周赛255 状态压缩DP与集合问题
边奶娃边刷题，最后一题不会，所以本次周赛重点讲一下第三题，使用位压缩DP解组合问题。
5850.找出数组的最大公约数
给你一个整数数组 nums ，返回数组中最大数和最小数的 最大公约数 。
两个数的 最大公约数 是能够被两个数整除的最大正整数。
题解：
简单水题，可以使用std::gcd函数求最大公约数
class Solution {
public:
int findGCD(vector<int>& nums) {
int max = nums[0];
int min = nums[0];
for(auto v : nums){
max = std::max<int>(max, v);
min = std::min<int>(min, v);
}
return std::gcd(max, min);
}
};
5851. 找出不同的二进制字符串
给你一个字符串数组 nums ，该数组由 n 个 互不相同 的二进制字符串组成，且每个字符串长度都是 n 。请你找出并返回一个长度为 n 且 没有出现 在 nums 中的二进制字符串。如果存在多种答案，只需返回 任意一个 即可。
题解：
这道题可以使用对角线来做，题目是n个字符串，且每个字符串的长度为n，所求字符串为s，只需要确定s[i]和第i个字符串的第i个字符不一样，那么s就和每一个字符串不一样。
class Solution {
public:
string findDifferentBinaryString(vector<string>& nums) {
int n = nums.size();
string s;
for(int i=0; i<n; i++){
if(nums[i][i] == '0'){
s += "1";
}else{
s += "0";
}
}
return s;
}
};
5852. 最小化目标值与所选元素的差
给你一个大小为 m x n 的整数矩阵 mat 和一个整数 target 。
从矩阵的 每一行 中选择一个整数，你的目标是 最小化 所有选中元素之 和 与目标值 target 的 绝对差 。
返回 最小的绝对差 。
a 和 b 两数字的 绝对差 是 a - b 的绝对值。
题解：
这道题使用dp的方式来处理，注意m、n都是小于等于70的，mat中每个值也是小于等于70，这样我们可以使用位来存储所有的结果信息。
比如对于示例1中的，对于组合1、5、7，其位信息的计算是：
定义bitset<5000> F,当前和为多少，就在多少位上设置为1。注意这里的下标1、6、13指的是第1、6、13位。C++的bitset在这里很好用。
首先处理第一行，对于1来说，设置F[1] = 1，位信息位0001，
处理第二行5，这时候和为6，那么设置F[6] = 1，位信息位100000，
处理第三行7，这时候和为13，设置F[13]=1，位信息1000000000000。
于是有如下递推公式，当前行的所有和的信息等于上一行所有和的信息左移x位（左移x就是增加了x）。
F[i] |= F[i-1] << A[i][j]，
class Solution {
public:
int minimizeTheDifference(vector<vector<int>>& A, int target) {
int n=A.size();
int m=A[0].size();
bitset<5000> F[n];
F[0]=0;
for (int i=0;i<m;++i) F[0][A[0][i]]=1;
for (int i=1;i<n;++i)
{
F[i]=0;
for (int j=0;j<m;++j)
F[i]|=F[i-1]<<A[i][j];
}
int ans=4900;
for (int i=1;i<=4900;++i)
if (F[n-1][i])
ans=min(ans,abs(target-i));
return ans;
}
};
5853. 从子集的和还原数组
存在一个未知数组需要你进行还原，给你一个整数 n 表示该数组的长度。另给你一个数组 sums ，由未知数组中全部 2n 个 子集的和 组成（子集中的元素没有特定的顺序）。
返回一个长度为 n 的数组 ans 表示还原得到的未知数组。如果存在 多种 答案，只需返回其中 任意一个 。
如果可以由数组 arr 删除部分元素（也可能不删除或全删除）得到数组 sub ，那么数组 sub 就是数组 arr 的一个 子集 。sub 的元素之和就是 arr 的一个 子集的和 。一个空数组的元素之和为 0 。
注意：生成的测试用例将保证至少存在一个正确答案。
示例：
输入：n = 3, sums = [-3,-2,-1,0,0,1,2,3]
输出：[1,2,-3]
题意说明：
给你一个数字n，和一个长度位
的数组sums，让你推算出可能的数组arr，使得sums是arr所有子集所有数之和的集合。
题解：（参考leetcode网站）
这个题使用DFS搜索来处理，可以证明，sums中最小值和次小值的差一定是 一个待求元素的绝对值，根据这个求出来的值，可以把sums平分成两半，对于找到的dif，可以把sums划分为{a} 与 {b}, 存在一个对应关系使得a与b中元素一一对应（且相差dif）
这里直接保留小的一半，作为新的sums，继续迭代。
最后得到了所有待求元素的绝对值，遍历枚举一下，确认正负号即可。
class Solution {
public:
vector<int> a;
bool check(const vector<int>& sums, int v, vector<int>& y) {
vector<int> x;
int p = 0, n = sums.size();
x.clear();
y.clear();
if (v >= 0) {
for (int i = 0; i < n; ++i)
if (p == x.size() || x[p] - v != sums[i]) x.push_back(sums[i]);
else y.push_back(sums[i]), ++p;
} else {
for (int i = n - 1; i >= 0; --i)
if (p == x.size() || x[p] - v != sums[i]) x.push_back(sums[i]);
else y.push_back(sums[i]), ++p;
reverse(y.begin(), y.end());
}
if (x.size() != n / 2) return false;
bool flag = false;
for (int i = 0; i < x.size(); ++i)
if (x[i] == v) {
flag = true;
break;
}
return flag;
}
bool dfs(int n, const vector<int>& sums) {
if (a.size() == n) return true;
int x = sums[0] - sums[1];
vector<int> nxt_sums;
if (check(sums, x, nxt_sums)) {
a.push_back(x);
if (dfs(n, nxt_sums)) return true;
a.pop_back();
}
if (check(sums, -x, nxt_sums)) {
a.push_back(-x);
if (dfs(n, nxt_sums)) return true;
a.pop_back();
}
return false;
}
vector<int> recoverArray(int n, vector<int>& sums) {
a.clear();
sort(sums.begin(), sums.end(), [&](const int &x, const int &y) {return x > y;});
dfs(n, sums);
return a;
}
};
腾讯云开发者
