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

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

中等(按位与运算，二进制运算符)

对数组 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
2
3
4
5
6
7
8
9
10
class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        m = max(candidates).bit_length()
        ans = 0
        for i in range(m):
            count = 0
            for x in candidates:
                count += x >> i & 1     #统计第i位上是1的个数
            ans = max(ans,count)
        return ans

思路：枚举比特位

找出列表中最大的数字，它的比特位也是列表中最长的。统计列表中一共有多少个第 i 个比特位是1，其中最多的就是答案。

解释步骤：

  1. 计算候选数字的最大位数 (bit_length)：

    • .bit_length() 返回最大值的二进制表示中所需的位数。
    • 例如，如果最大值是 13（二进制表示为 1101），bit_length() 返回 4，因为 1101 有 4 位。

  2. 计算每一位上有多少个1：

    • x >> i & 1：右移 x 的二进制表示 i 位，然后与 1 进行按位与操作，得到第 i 位的值（0 或 1）。
      • 例如，假设 x 是 13（1101），如果 i 是 1，则 x >> 1 是 110，110 & 1 是 0。
      • 按位与运算符（&）是一个二进制运算符，它对两个整数的每一位进行按位与操作。按位与操作的规则是：只有当两个对应位都是1时，结果才是1，否则结果是0。

代码二：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        lst = [0]*24
        for x in candidates:
            i = 0
            while x:
                lst[i] += x & 1
                x >>= 1
                i += 1
        return max(lst)

思路：一次遍历

代码一需要多次遍历 candidates 数组，我们也可以只遍历一次。
创建一个大小为 24（10^7 的二进制长度）的 lst 数组，统计每个比特位上的 1 的个数。
最后答案为 lst 的最大值。