作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
今天和大家聊聊昨天刚刚结束的LeetCode第280场周赛。
这场周赛是美团和LeetCode合作举办的，整体的题目质量不错，难度梯度很好，当然题目也相对比较难。
居然要前200名才能获得内推机会，emmm，不得不吐槽，着实有些苛刻了。能够进200名的大佬，估计也不缺内推机会。
好了，废话不多说，我们来看题吧。
得到0的操作数
难度：0星
给你两个 非负 整数 num1 和 num2 。
每一步 操作 中，如果 num1 >= num2 ，你必须用 num1 减 num2 ；否则，你必须用 num2 减 num1 。
- 例如，num1 = 5 且 num2 = 4 ，应该用 num1 减 num2 ，因此，得到 num1 = 1 和 num2 = 4 。然而，如果 num1 = 4且 num2 = 5 ，一步操作后，得到 num1 = 4 和 num2 = 1 。
返回使 num1 = 0 或 num2 = 0 的 操作数 。
解法
模拟题，在极端情况下，如num1为1，num2为1e5时，需要1e5次操作才能得到0，不过即使如此也依然在可接受的范围内。
所以直接模拟即可。
代码语言：javascript复制class Solution {
public:
int countOperations(int num1, int num2) {
int ret = 0;
while (num1 > 0 && num2 > 0) {
if (num1 >= num2) num1 -= num2;
else num2 -= num1;
ret ;
}
return ret;
}
};
使数组成交替数组的最少操作数
难度：☆☆
给你一个下标从 0 开始的数组 nums ，该数组由 n 个正整数组成。
如果满足下述条件，则数组 nums 是一个 交替数组 ：
- nums[i - 2] == nums[i] ，其中 2 <= i <= n - 1 。
- nums[i - 1] != nums[i] ，其中 1 <= i <= n - 1 。
在一步 操作 中，你可以选择下标 i 并将 nums[i] 更改 为 任一 正整数。
返回使数组变成交替数组的 最少操作数 。
解法
我们需要改变数组中的一些数，让数组变成交替数组。不难想到，我们要尽可能地保留相同的数字，于是自然可以想到贪心算法。
即我们将数组中的元素根据下标的奇偶性分成两组，分别取出两组当中出现次数最多的元素，将剩余的元素全部转换成出现最多的元素，计算一下开销即可。但本题当中有一个trick，就是明确说了相邻的元素不能相等，也就是说奇偶位置的元素不能相同。如果恰好奇偶位置出现最多的元素相等，我们就要选择出现次数第二多的元素。
整个题目的思路比较清晰，比较容易想到，只不过由于逻辑比较复杂，代码量不小，因此有一星赋予编码量。
代码语言：javascript复制class Solution {
public:
map<int, int> separate(vector<int>& nums, int s=0) {
// 对数组进行分组，统计分组中每个元素出现的次数
int n = nums.size();
map<int, int> mp;
for (int i = s; i < n; i = 2) {
mp[nums[i]] ;
}
return mp;
}
pair<int, int> get_pair(map<int, int>& mp, vector<int>& nums, int s=0, bool haslimit = false, int limit = 0) {
// 获取出现次数最多的元素以及它出现的次数
// 如果haslimit为true，则返回出现元素第二多的元素
int maxi = 0, num = nums[s];
int n = nums.size();
for (int i = s; i < n; i =2) {
if (haslimit && nums[i] == limit) continue;
if (mp[nums[i]] > maxi) {
maxi = mp[nums[i]];
num = nums[i];
}
}
return make_pair(num, maxi);
}
int minimumOperations(vector<int>& nums) {
int n = nums.size();
if (n == 1) return 0;
// 将数组分奇偶统计
auto odd_map = separate(nums), even_map = separate(nums, 1);
// 获取出现次数最多的元素
auto odd = get_pair(odd_map, nums), even = get_pair(even_map, nums, 1);
int left = n / 2 n % 2, right = n / 2;
// 如果出现最多的元素不相等，那么直接贪心求解
if (odd.first != even.first) {
return left - odd.second right - even.second;
}
// 如果相等，需要做取舍
return min(left - odd.second right - get_pair(even_map, nums, 1, true, odd.first).second, left - get_pair(odd_map, nums, 0, true, odd.first).second right - even.second);
}
};
拿出最少数目的魔法豆
难度：☆☆☆
给你一个 正 整数数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。
请你从每个袋子中 拿出 一些豆子（也可以 不拿出），使得剩下的 非空 袋子中（即 至少 还有 一颗 魔法豆的袋子）魔法豆的数目 相等 。一旦魔法豆从袋子中取出，你不能将它放到任何其他的袋子中。
请你返回你需要拿出魔法豆的 最少数目。
解法
题目的表达稍稍有些复杂，可以稍稍简化，简化成通过拿出若干豆子之后，使得数仅只包含0和x两种值，要求取出豆子的最少数量。
由于只能减少不能增加，所以原数组当中所有小于x的值全部置为0，所有大于等于x的值拿出若干颗变成x，显然x应该选数组当中本身有的值最优。
如果采用暴力求解的方法，我们依次遍历数组，枚举所有可能的x，然后再遍历一次数组计算出取出的豆子总数。显然这样的复杂度是O(n^2) ，在1e5的量级下是不能接受的。所以我们要做的就是针对这个复杂度进行优化。
怎么优化呢？
我们简单分析一下会发现，我们计算的逻辑根据是否大于等于x分成两种，如果大于等于x则变成x，否则变成0。进而我们可以想到，我们可以首先对数组进行排序。这样当我们枚举x的时候，可以保证x的左侧就是所有小于x的值，x的右侧是大于等于x的值。
对于小于x的部分，因为要将它们全部置为0，所以我们直接求和即可。麻烦的是右侧的部分，我们需要将它们置为x。但其实也很好办，我们把式子简单列一下，我们假设x对应的下标是k：
经过转化之后， 我们可以通过右侧部分的总和和nums[k]计算得到。只要我们知道左右两边的元素和，就可以快速求到x对应的答案。对于快速求解区间和的问题，我们可以通过前缀和快速实现。也就是说我们用sum[i]维护nums[0]到nums[i]的和，当我们要求sum_{k=i}^j nums[k] 时就可以通过sum[j] - sum[i-1]来快速得到。
AC代码如下：
代码语言：javascript复制class Solution {
public:
long long minimumRemoval(vector<int>& beans) {
sort(beans.begin(), beans.end());
int n = beans.size();
vector<long long> sb(n 2, 0);
sb[0] = beans[0];
for (int i = 1; i < n; i ) sb[i] = sb[i-1] beans[i];
long long ret = 0x7fffffffffffffff;
for (int i = 0; i < n; i ) {
// 左侧部分，即左侧的所有元素和
long long left = i > 0 ? sb[i-1]: 0;
// 右侧部分，即右侧所有元素和减去 (n-i-i) * beans[i]
long long right = sb[n-1] - sb[i] - (long long)beans[i] * (long long) (n-i-1);
ret = min(ret, left right);
}
return ret;
}
};
要注意我们的答案可能会超过int的范围， 所以要使用long long类型，不仅在计算的时候需要用long long，一些计算的中间步骤也需要使用强制类型转换，将beans[i]转化成long long，否则C 编译器可能会隐式地使用int进行计算。
数组的最大与和
难度：☆☆☆☆☆
给你一个长度为 n 的整数数组 nums 和一个整数 numSlots ，满足2 * numSlots >= n 。总共有 numSlots 个篮子，编号为 1 到 numSlots 。
你需要把所有 n 个整数分到这些篮子中，且每个篮子 至多 有 2 个整数。一种分配方案的 与和 定义为每个数与它所在篮子编号的 按位与运算 结果之和。
- 比方说，将数字 [1, 3] 放入篮子 1 中，[4, 6] 放入篮子 2 中，这个方案的与和为 (1 AND 1) (3 AND 1) (4 AND 2) (6 AND 2) = 1 1 0 2 = 4 。
请你返回将 nums 中所有数放入 numSlots 个篮子中的最大与和。
解法
这道题难度不小，即使和hard题目比，也算是比较难的了。
我们先来分析题目，每个篮子当中最多放入两个数，也可以不放，虽然题目中给的范围很小，nums[i]最多只有15，numslots最多也只有9。但我们简单估算一下也会发现，如果暴力枚举的话， 可能性依然非常多。
从元素的角度出发，每个元素放到不同的篮子里会有不同的收益，但如果我们从篮子的角度出发。其实我们并不需要关心篮子里都放了哪些元素，只关心篮子里已经装的数量，这样好决定之后还能继续装几个。由此，可以想到动态规划，即我们维护篮子的状态，通过状态转移求解。
到这里遇到了第一个难点，篮子有多个，每个篮子装入的数量是一个数组，用数组来表示状态显然太奢侈，会带来大量的空间和时间的开销，因此需要对状态进行压缩。但想到了压缩仍然有问题，因为我们常规的压缩方式是二进制压缩，即将一个状态用二进制表示，0和1分别表示两种不同的状态。但这题当中篮子的状态有3种分别是0、1、2，所以需要用三进制表示。
三进制表示显然比二进制麻烦，因为计算机当中的数据是天然以二进制的形式存储的。那有没有办法继续用二进制表示呢？当然是有的，比较简单的方式是将篮子按照容量拆分，也就是说我们用两个只能最多装一个元素的篮子来代替原本可以最多装两个元素的篮子，这样就可以继续使用二进制表示了。
如果熟悉状态压缩的同学，应该不难写出代码：
代码语言：javascript复制class Solution {
public:
int maximumANDSum(vector<int>& nums, int numSlots) {
int n = nums.size();
int dp[1000000];
memset(dp, 0, sizeof dp);
int ret = 0;
// 枚举元素
for (int i = 0; i < n; i ) {
// 枚举状态，为了防止同一个元素重复放入，所以倒叙遍历状态
for (int s = (1 << (2 * numSlots)); s >= 0; s--) {
// 如果状态中1的数量超过n，说明状态不可能成立，则跳过
int c = __builtin_popcount(s);
if (c >= n) continue;
// 枚举篮子
for (int j = 0; j < 2 * numSlots; j ) {
// 如果篮子为空
if ((s & (1 << j)) == 0) {
int ns = s (1 << j);
int slots;
if (j >= numSlots) slots = j - numSlots 1;
else slots = j 1;
dp[ns] = max(dp[ns], dp[s] (nums[i] & slots));
ret = max(ret, dp[ns]);
}
}
}
}
return ret;
}
};
很遗憾，即使写出了这样的代码也无法通过，因为耗时太长了。
所以我们必须得进行优化，不得不说在比赛的时间内能够想到正确的解法，并且把代码写出来调试通已经不容易了，还要再想优化确实有点难了。
优化的方式有一些取巧，就是我们去掉枚举元素的那一重循环，那怎么枚举元素呢？我们用状态当中二进制的数量表示当前枚举的元素。当前枚举的状态当中有i个1，我们当前要放入的元素就是nums[i]。当我们从0开始遍历状态时，状态中的1的数量恰好也是从0开始递增的，所以就完美囊括了元素的枚举，这样就可以去掉一重循环。
class Solution {
public:
int maximumANDSum(vector<int>& nums, int numSlots) {
int n = nums.size();
int dp[1 << 20];
memset(dp, 0, sizeof dp);
int ret = 0;
for (int s = 0; s < (1 << (2 * numSlots)); s ) {
// c为s中1的数量
int c = __builtin_popcount(s);
if (c >= n) continue;
for (int j = 0; j < 2 * numSlots; j ) {
if ((s & (1 << j)) == 0) {
int ns = s (1 << j);
int slots = j / 2 1;
dp[ns] = max(dp[ns], dp[s] (nums[c] & slots));
ret = max(ret, dp[ns]);
}
}
}
return ret;
}
};
另外，我在题解库当中还看到了蒙特卡洛的方法，随机若干次求最大的方法，不得不说实在是太秀了……
老梁试了一下，还真的能通过，并且运行速度是Python里最快的……实在是太不讲武德了。
代码语言：javascript复制class Solution:
def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
ans=0
for i in range(1000):
random.shuffle(nums)
cur=0
counter=defaultdict(int)
for n in nums:
j=0
for i in range(1,numSlots 1):
if counter[i]<2 and n&i>n&j:
j=i
counter[j] =1
cur =n&j
ans=max(ans,cur)
return ans
好了，关于这次比赛的四道题就算是写完了，关于这次的周赛大家有什么想说的吗？
欢迎在评论区畅所欲言，感谢大家的阅读~
