题目

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

思路

第一，题目求的是按位与后「大于0」的最长的子序列长度，也就是说只要大于0就好，不关心是多少，关心的是子序列的长度。

第二，对于一组数，如果按位与的结果大于0，说明这些数的二进制表示最少有一位上全部都是1，否则结果不会大于0。另外，如果还存在一个数在这个二进制位上为1，那么加入这个数会使组合长度再加1。

因此，我们希望组合中的数在某一位上尽可能有更多的1，那么求出每个二进制位上有多少数为1，二进制位最多的1的个数就是最长的组合长度。

代码

  1. class Solution {
  2.     public int largestCombination(int[] candidates) {
  3.         int n = candidates.length;
  4.         int ans = 0;
  5.         int[] cnt = new int[30];
  6.         for (int i = 0; i < 30; i++) {
  7.             for (int j = 0; j < n; j++) {
  8.                 if ((candidates[j] >> i & 1) == 1) {
  9.                     cnt[i]++;
  10.                 }
  11.             }
  12.             ans = Math.max(ans, cnt[i]);
  13.         }
  14.         return ans;
  15.     }
  16. }