算法疑难杂症

按位单独处理的技巧

字数统计: 853字   |   阅读时长: 3分
, , ,

摘要: 按位单独处理的技巧一例

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，今天我们来看一个中等题，不涉及设么算法，主要是通过分析问题发现最优解的特性，进而想到按位单独处理的技巧。像这种没有用到某种标准算法或主流算法，需要现场分析问题发现某些特性进而解决的问题，具备一定的创新性，称为 Ad-Hoc 问题。此前我们也解决过一些这类问题，参考以下文章：

按位单独处理的技巧此前我们也解决过类似问题，参考文章 按位单独处理，本文是新的一例。

题目

对数组 nums 执行 按位与 相当于对数组 nums 中的所有整数执行 按位与 。

  • 例如，对 nums = [1, 5, 3] 来说，按位与等于 1 & 5 & 3 = 1 。
  • 同样，对 nums = [7] 而言，按位与等于 7 。

给你一个正整数数组 candidates 。计算 candidates 中的数字每种组合下 按位与 的结果。

返回按位与结果大于 0 的 最长 组合的长度。

提示：

1
2
1 <= candidates.length <= 1e5
1 <= candidates[i] <= 1e7

示例 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 。

题解

算法: 按位单独处理的技巧

合法的子集需要按位与的结果大于 0，找到合法子集的元素数的最大值。

重点是发现子集元素按位与的结果大于 0 等价于子集中所有元素都要在至少某一位上均为 1 这一特性。

有了这一特性，我们就知道最优解一定在某一位上均为 1。再结合元素的取值范围，我们知道可能的位是很少的，比较常见比如 int 的位的范围是 32。那么我就可以先预处理出第 $i$ 个位为 1 的最大子集，记其元素数为 $a[i]$，$i=0,2,\cdots,31$。然后 $\max(a)$ 即为答案。

通俗讲就是有多少个元素第 $i$ 位为 1，$i=0,1,\cdots,31$，最优解一定在其中，那这 32 个数的最大值自然就是最优解。

代码 (Python)

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