class Solution {
public:
int maximumANDSum(vector<int>& nums, int numSlots) {
}
};
2172. 数组的最大与和
给你一个长度为 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 个篮子中的最大与和。
示例 1：
输入：nums = [1,2,3,4,5,6], numSlots = 3 输出：9 解释：一个可行的方案是 [1, 4] 放入篮子 1 中，[2, 6] 放入篮子 2 中，[3, 5] 放入篮子 3 中。 最大与和为 (1 AND 1) + (4 AND 1) + (2 AND 2) + (6 AND 2) + (3 AND 3) + (5 AND 3) = 1 + 0 + 2 + 2 + 3 + 1 = 9 。
示例 2：
输入：nums = [1,3,10,4,7,1], numSlots = 9 输出：24 解释：一个可行的方案是 [1, 1] 放入篮子 1 中，[3] 放入篮子 3 中，[4] 放入篮子 4 中，[7] 放入篮子 7 中，[10] 放入篮子 9 中。 最大与和为 (1 AND 1) + (1 AND 1) + (3 AND 3) + (4 AND 4) + (7 AND 7) + (10 AND 9) = 1 + 1 + 3 + 4 + 7 + 8 = 24 。 注意，篮子 2 ，5 ，6 和 8 是空的，这是允许的。
提示：
n == nums.length1 <= numSlots <= 91 <= n <= 2 * numSlots1 <= nums[i] <= 15原站题解
golang 解法, 执行用时: 148 ms, 内存消耗: 7.7 MB, 提交时间: 2023-09-14 11:15:57
func maximumANDSum(nums []int, numSlots int) (ans int) {
f := make([]int, 1<<(numSlots*2))
for i, fi := range f {
c := bits.OnesCount(uint(i))
if c >= len(nums) {
continue
}
for j := 0; j < numSlots*2; j++ {
if i>>j&1 == 0 { // 枚举空篮子 j
s := i | 1<<j
f[s] = max(f[s], fi+(j/2+1)&nums[c])
ans = max(ans, f[s])
}
}
}
return
}
func max(a, b int) int { if b > a { return b }; return a }
cpp 解法, 执行用时: 396 ms, 内存消耗: 20.4 MB, 提交时间: 2023-09-14 11:15:44
class Solution {
public:
int maximumANDSum(vector<int> &nums, int numSlots) {
int ans = 0;
vector<int> f(1 << (numSlots * 2));
for (int i = 0; i < f.size(); ++i) {
int c = __builtin_popcount(i);
if (c >= nums.size()) continue;
for (int j = 0; j < numSlots * 2; ++j) {
if ((i & (1 << j)) == 0) { // 枚举空篮子 j
int s = i | (1 << j);
f[s] = max(f[s], f[i] + ((j / 2 + 1) & nums[c]));
ans = max(ans, f[s]);
}
}
}
return ans;
}
};
java 解法, 执行用时: 169 ms, 内存消耗: 42.4 MB, 提交时间: 2023-09-14 11:15:31
class Solution {
public int maximumANDSum(int[] nums, int numSlots) {
var ans = 0;
var f = new int[1 << (numSlots * 2)];
for (var i = 0; i < f.length; i++) {
var c = Integer.bitCount(i);
if (c >= nums.length) continue;
for (var j = 0; j < numSlots * 2; ++j) {
if ((i & (1 << j)) == 0) { // 枚举空篮子 j
var s = i | (1 << j);
f[s] = Math.max(f[s], f[i] + ((j / 2 + 1) & nums[c]));
ans = Math.max(ans, f[s]);
}
}
}
return ans;
}
}
python3 解法, 执行用时: 6632 ms, 内存消耗: 18 MB, 提交时间: 2023-09-14 11:15:05
'''
设 i 的二进制中的 1 的个数为 c，定义 f[i] 表示将 nums 的前 c 个数字放到篮子中，
且放了数字的篮子集合为 i 时的最大与和。初始值 f[0]=0。
'''
class Solution:
def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
f = [0] * (1 << (numSlots * 2))
for i, fi in enumerate(f):
c = i.bit_count()
if c >= len(nums): continue
for j in range(numSlots * 2):
if (i & (1 << j)) == 0: # 枚举空篮子 j
s = i | (1 << j)
f[s] = max(f[s], fi + ((j // 2 + 1) & nums[c]))
return max(f)