目标
对数组 nums 执行 按位与 相当于对数组 nums 中的所有整数执行 按位与 。
- 例如，对 nums = [1, 5, 3] 来说，按位与等于 1 & 5 & 3 = 1 。
- 同样，对 nums = [7] 而言，按位与等于 7 。
给你一个正整数数组 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 <= 10^5
- 1 <= candidates[i] <= 10^7
思路
求数组 nums 符合条件（子序列按位与的结果大于 0）的子序列的最大长度。
如果使用 dfs 考虑选或者不选，枚举所有子序列肯定超时。
看了题解，说是统计所有数字相同 bit 位上 1 的出现次数，取其最大值。
代码
/**
* @date 2025-01-12 21:50
*/
public class LargestCombination2275 {
public int largestCombination(int[] candidates) {
int[] cnt = new int[24];
for (int candidate : candidates) {
for (int i = 0; i < 24; i++) {
cnt[i] += (candidate >> i) & 1;
}
}
int res = 0;
for (int i : cnt) {
res = Math.max(i, res);
}
return res;
}
}
性能
