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

【LetMeFly】2275.按位与结果大于零的最长组合：按位与

力扣题目链接：https://leetcode.cn/problems/largest-combination-with-bitwise-and-greater-than-zero/

对数组 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 <= 105
• 1 <= candidates[i] <= 107

解题方法：位运算(按位与)

假设最终选择了$a$、$b$、$c$且它们的与运算结果非零，那么二进制下$abc$至少有一位都非零。

因此我们可以对每一位分别计算，对于某一位，遍历数组中所有元素，统计这一位非零元素的个数。这些元素按位与的话，结果一定非零。

在所有位中，非零数量最多的“数量”即为所求。

• 时间复杂度$O(\log\max(candidates[i])\times len(canndidates))$，其中$2^{24}=16,777,216\gt10^7$，$\log\max(candidates[i])\approx24$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-01-14 17:04:21
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-14 17:05:30
 */
class Solution {
public:
    int largestCombination(vector<int>& candidates) {
        int ans = 0;
        for (int i = 0; i < 24; i++) {
            int cnt = 0;
            for (int t : candidates) {
                cnt += t >> i & 1;
            }
            ans = max(ans, cnt);
        }
        return ans;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-01-14 17:13:33
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-14 17:15:52
'''
from typing import List

class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        return max(sum(t >> i & 1 for t in candidates) for i in range(24))

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-01-14 17:16:21
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-14 17:16:23
 */
class Solution {
    public int largestCombination(int[] candidates) {
        int ans = 0;
        for (int i = 0; i < 24; i++) {
            int cnt = 0;
            for (int t : candidates) {
                cnt += t >> i & 1;
            }
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-01-14 17:17:36
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-14 17:18:45
 */
package main

func largestCombination(candidates []int) (ans int) {
    for i := 0; i < 24; i++ {
        cnt := 0
        for _, t := range candidates {
            cnt += t >> i & 1
        }
        if cnt > ans {
            ans = cnt
        }
    }
    return ans
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/145144347