golang刷leetcode：按位与结果大于零的最长组合

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

1 <= candidates[i] <= 107

解题思路：

1，这是个套路题，乍一看像最长递增子序列，其实不然，i位置不能由dp[i-1]决定

2，位运算思路：既然要求按位与大于 0, 那么一定存在某一位多个数都为 1 3，统计 32 位上哪一位出现的个数最多,那么这几个数 按位与 则大于0

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

复制