LeetCode 2275. 按位与结果大于零的最长组合（位运算）

Michael阿明

发布于 2022-11-27 17:20:20

3450

发布于 2022-11-27 17:20:20

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

文章目录

1. 题目

对数组 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

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/largest-combination-with-bitwise-and-greater-than-zero 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

题目没说要是子数组，可以不连续
要求按位 & 不为0，只要有一个 bit 都是 1 就行
统计所有的位上，1 的最多的个数

class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        # 数据范围最多是 24 位 int
        ans = 1
        for i in range(24):
            ct = 0
            for j in range(len(candidates)):
                if (candidates[j]>>i)&1 == 1:
                    ct += 1
            ans = max(ans, ct)
        return ans

1124 ms 22.2 MB Python3

我的CSDN博客地址 https://michael.blog.csdn.net/

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2022-05-22，如有侵权请联系 cloudcommunity@tencent.com 删除

https