2275. 按位与结果大于零的最长组合

🟠 🔖 位运算 数组 哈希表 计数 🔗 力扣open in new window LeetCodeopen in new window

题目

The bitwise AND of an array nums is the bitwise AND of all integers in nums.

For example, for nums = [1, 5, 3], the bitwise AND is equal to 1 & 5 & 3 = 1.
Also, for nums = [7], the bitwise AND is 7.

You are given an array of positive integers candidates. Evaluate the bitwise AND of every combination of numbers of candidates. Each number in candidates may only be used once in each combination.

Return the size of thelargest combination of candidates with a bitwise ANDgreater than 0.

Example 1:

Input: candidates = [16,17,71,62,12,24,14]
Output: 4
Explanation: The combination [16,17,62,24] has a bitwise AND of 16 & 17 & 62 & 24 = 16 > 0.
The size of the combination is 4.
It can be shown that no combination with a size greater than 4 has a bitwise AND greater than 0.
Note that more than one combination may have the largest size.
For example, the combination [62,12,24,14] has a bitwise AND of 62 & 12 & 24 & 14 = 8 > 0.

Example 2:

Input: candidates = [8,8]
Output: 2
Explanation: The largest combination [8,8] has a bitwise AND of 8 & 8 = 8 > 0.
The size of the combination is 2, so we return 2.

Constraints:

1 <= candidates.length <= 10^5
1 <= candidates[i] <= 10^7

题目大意

对数组 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 <= 10^5
1 <= candidates[i] <= 10^7

解题思路

按位与操作可以将多个二进制数逐位比较，如果相同位置上所有数的位均为 1，则结果的该位为 1，否则为 0。
要求按位与结果大于 0，意味着在某个位置上至少有一个 1。
问题的核心是找到使按位与结果大于 0 的最长组合长度，即在某个二进制位上为 1 的数最多的情况。

统计每个位上的 1 的数量：
- 对每个数字 num 转换成二进制表示并逐位检查。
- 对于每个位上的 1，将它记录在 bitMap 中，该 Map 的键表示二进制位的位置，值表示该位置上为 1 的数字数量。
返回最大值：
- 遍历 bitMap 的所有值，选择最大值作为结果。这是因为该最大值表示某个位上所有数字为 1 的数量，即最长组合的长度。

复杂度分析

时间复杂度：O(n log m)，其中 n 是数组长度，m 是 num 的最大值，对于每个数字 num，转换为二进制字符串的时间复杂度为 O(log m)，一共要处理 n 个数字。
空间复杂度：O(d)，其中 d 是二进制数的位数，用于存储每个位上为 1 的计数，最多 24 位，所以是常数量级的。

代码

/**
 * @param {number[]} candidates
 * @return {number}
 */
var largestCombination = function (candidates) {
	let bitMap = new Map();
	for (let num of candidates) {
		num
			.toString(2)
			.split('')
			.reverse()
			.forEach((char, index) => {
				if (char == '1') {
					bitMap.set(index, (bitMap.get(index) || 0) + 1);
				}
			});
	}
	return Math.max(...bitMap.values());
};

2275. 按位与结果大于零的最长组合

# 2275. 按位与结果大于零的最长组合

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

2275. 按位与结果大于零的最长组合

题目

题目大意

解题思路

复杂度分析

代码

相关题目