class Solution {
public:
int largestCombination(vector<int>& candidates) {
}
};
2275. 按位与结果大于零的最长组合
对数组 nums 执行 按位与 相当于对数组 nums 中的所有整数执行 按位与 。
nums = [1, 5, 3] 来说，按位与等于 1 & 5 & 3 = 1 。nums = [7] 而言，按位与等于 7 。给你一个正整数数组 candidates 。计算 candidates 中的数字每种组合下 按位与 的结果。 candidates 中的每个数字在每种组合中只能使用 一次 。
返回按位与结果大于 0 的 最长 组合的长度。
示例 1：
输入：candidates = [16,17,71,62,12,24,14] 输出：4 解释：组合 [16,17,62,24] 的按位与结果是 16 & 17 & 62 & 24 = 16 > 0 。 组合长度是 4 。 可以证明不存在按位与结果大于 0 且长度大于 4 的组合。 注意，符合长度最大的组合可能不止一种。 例如，组合 [62,12,24,14] 的按位与结果是 62 & 12 & 24 & 14 = 8 > 0 。
示例 2：
输入：candidates = [8,8] 输出：2 解释：最长组合是 [8,8] ，按位与结果 8 & 8 = 8 > 0 。 组合长度是 2 ，所以返回 2 。
提示：
1 <= candidates.length <= 1051 <= candidates[i] <= 107原站题解
golang 解法, 执行用时: 76 ms, 内存消耗: 9.1 MB, 提交时间: 2022-12-05 18:44:11
func largestCombination(candidates []int) (ans int) {
for i := 0; i < 24; i++ {
s := 0
for _, v := range candidates {
s += v >> i & 1
}
ans = max(ans, s)
}
return
}
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 924 ms, 内存消耗: 23 MB, 提交时间: 2022-12-05 18:43:39
'''
位运算题目经典技巧：逐个考虑每一个比特位。
假设元素值只有 0 和 1，那么解法就很简单了：由于不能选 0（这会导致按位与为 0），我们选择所有的 1，答案即为 1 的个数。
将上述结论推广，考虑每一个比特位，统计这一位上的 1 的个数，取所有个数的最大值作为答案。
由于 2^23 < 10^7 < 2^24，枚举比特位可以从 00 枚举到 2323。
'''
class Solution:
def largestCombination(self, candidates: List[int]) -> int:
return max(sum(num >> i & 1 for num in candidates) for i in range(24))
java 解法, 执行用时: 41 ms, 内存消耗: 55.9 MB, 提交时间: 2022-12-05 18:42:02
// 既然要求按位与大于 0, 那么一定存在某一位多个数都为 1
// 统计 32 位上哪一位出现的个数最多,那么这几个数 按位与 则大于0
class Solution {
public int largestCombination(int[] candidates) {
int[] cnt = new int[32];
int max = 0;
for (int c : candidates) {
for (int i = 0; i < 32; i++) {
if (((1 << i) & c) > 0) cnt[i]++;
}
}
for (int i = 0; i < 32; i++) {
max = Math.max(max, cnt[i]);
}
return max;
}
}
cpp 解法, 执行用时: 108 ms, 内存消耗: 56 MB, 提交时间: 2022-12-05 18:39:38
class Solution {
public:
int largestCombination(vector<int>& candidates) {
// 计算从低到高第 k 个二进制位数值为 1 的元素个数
auto maxlen = [&](int k) -> int {
int res = 0;
for (int num: candidates) {
if (num & (1 << k)) {
++res;
}
}
return res;
};
int res = 0;
for (int i = 0; i < 24; ++i) {
// 遍历二进制位
res = max(res, maxlen(i));
}
return res;
}
};
python3 解法, 执行用时: 992 ms, 内存消耗: 23.2 MB, 提交时间: 2022-12-05 18:39:24
class Solution:
def largestCombination(self, candidates: List[int]) -> int:
# 计算从低到高第 k 个二进制位数值为 1 的元素个数
def maxlen(k: int):
res = 0
for num in candidates:
if num & (1 << k):
res += 1
return res
res = 0
for i in range(24):
# 遍历二进制位
res = max(res, maxlen(i))
return res