原文链接: https://leetcode-cn.com/problems/count-number-of-maximum-bitwise-or-subsets

英文原文

Given an integer array nums, find the maximum possible bitwise OR of a subset of nums and return the number of different non-empty subsets with the maximum bitwise OR.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b. Two subsets are considered different if the indices of the elements chosen are different.

The bitwise OR of an array a is equal to a[0] OR a[1] OR ... OR a[a.length - 1] (0-indexed).

 

Example 1:

Input: nums = [3,1]
Output: 2
Explanation: The maximum possible bitwise OR of a subset is 3. There are 2 subsets with a bitwise OR of 3:
- [3]
- [3,1]

Example 2:

Input: nums = [2,2,2]
Output: 7
Explanation: All non-empty subsets of [2,2,2] have a bitwise OR of 2. There are 23 - 1 = 7 total subsets.

Example 3:

Input: nums = [3,2,1,5]
Output: 6
Explanation: The maximum possible bitwise OR of a subset is 7. There are 6 subsets with a bitwise OR of 7:
- [3,5]
- [3,1,5]
- [3,2,5]
- [3,2,1,5]
- [2,5]
- [2,1,5]

 

Constraints:

• 1 <= nums.length <= 16
• 1 <= nums[i] <= 105

中文题目

给你一个整数数组 nums ，请你找出 nums 子集 按位或 可能得到的 最大值 ，并返回按位或能得到最大值的 不同非空子集的数目 。

如果数组 a 可以由数组 b 删除一些元素（或不删除）得到，则认为数组 a 是数组 b 的一个 子集 。如果选中的元素下标位置不一样，则认为两个子集 不同 。

对数组 a 执行 按位或 ，结果等于 a[0] OR a[1] OR ... OR a[a.length - 1]（下标从 0 开始）。

 

示例 1：

输入：nums = [3,1]
输出：2
解释：子集按位或能得到的最大值是 3 。有 2 个子集按位或可以得到 3 ：
- [3]
- [3,1]

示例 2：

输入：nums = [2,2,2]
输出：7
解释：[2,2,2] 的所有非空子集的按位或都可以得到 2 。总共有 23 - 1 = 7 个子集。

示例 3：

输入：nums = [3,2,1,5]
输出：6
解释：子集按位或可能的最大值是 7 。有 6 个子集按位或可以得到 7 ：
- [3,5]
- [3,1,5]
- [3,2,5]
- [3,2,1,5]
- [2,5]
- [2,1,5]

 

提示：

• 1 <= nums.length <= 16
• 1 <= nums[i] <= 105

通过代码

高赞题解

思路

• 这道题中要找的是 子序列 中，包含几个可行解，很容易的可以想到 dfs：

  • 观察数据规模， 1 ≤ n ≤ 16，最暴力的 dfs 也才 $2^{16} = 64, 000$，可以接受

• 还需要找到 按位或 的 最大值 。观察到所有的数字都是正数，则显然有 $a\ |\ b ≥ max(a, b)$，即一个正数A按位或另一个正数B，得到的结果C一定是不减的。

  • 由此我们可以知道：我们要寻找的最大值 = 所有数字按位或结果

一、寻找按位或最大值

思路证明

随便举例两个正数：

1 0 0 0 1 0 0 1   A

0 1 0 1 1 1 0 1   B

----------------这条横线表示竖式的按位或

1 1 0 1 1 1 0 1   C

A 和 B 都是正数,观察上面的竖式，可以发现对于每一位 $C[i] = A[i]\ |\ B[i]$

|A[i]|B[i]|A[i] | B[i]|

|:———:|:———:|:———:|

|0|0|0|

|0|1|1|

|1|0|1|

|1|1|1|

可得对于数字每一位，都有 $C[i] ≥ max(A[i], B[i])$

则 $C ≥ max(A , B)$

则对于一个全集 S，和一个 S 的子集 S'，假设$S = S’ + {x}$

有 $or(S) = or(S’ \ | \ x) ≥ or(S’)$，其中 or 表示对某个集合所有元素集体按位或。

也就是说，我们要找的全局按位或最大值，就等于原数组所有元素按位或结果。

具体代码

[]

int sum = 0;

for(auto p : nums){

    sum |= p;

}

[]

int sum = 0;

for(int p : nums){

    sum |= p;

}

二、朴素的暴力DFS

思路

使用一个 idx 来记录目前遍历到哪个数字了，使用一个 cur 来记录前面的若干位的 或结果。

具体代码

[]

int ans = 0;

void dfs(vector<int>& nums, int& sum, int idx, int cur){

    // 到达dfs终点

    if(idx == nums.size()){

        if(cur == sum) ans++;

        return;

    }

    // 尝试加入当前数字

    dfs(nums, sum, idx + 1, cur | nums[idx]);

    // 尝试不加入当前数字

    dfs(nums, sum, idx + 1, cur);

}

[]

private int ans = 0;

public void dfs(int[] nums, int sum, int idx, int cur){

    // 到达dfs终点

    if(idx == nums.length){

        if(cur == sum) ans++;

        return;

    }

    // 尝试加入当前数字

    dfs(nums, sum, idx + 1, cur | nums[idx]);

    // 尝试不加入当前数字

    dfs(nums, sum, idx + 1, cur);

}

三、剪枝

思路

由于 一、寻找按位或最大值 中已经证明了，按位或是一个不减的操作。

因此加入我们 dfs 到某一个位置时，发现已经达到最大值，则后面未处理的 k 个值，$2^k$ 种取法均能满足要求。

我们以此为依据，添加剪枝

具体代码

[]

int ans = 0;

void dfs(vector<int>& nums, int& sum, int idx, int cur){

    // 到中间某时刻，已经达到最大值，剪枝

    if(cur == sum){

        // 还剩 nums.size() - idx个值未处理

        ans += 1 << (nums.size() - idx);

        return;

    }

    // 到达dfs终点

    if(idx == nums.size()){

        return;

    }

    // 尝试加入当前数字

    dfs(nums, sum, idx + 1, cur | nums[idx]);

    // 尝试不加入当前数字

    dfs(nums, sum, idx + 1, cur);

}

[]

private int ans = 0;

public void dfs(int[] nums, int sum, int idx, int cur){

    // 到中间某时刻，已经达到最大值，剪枝

    if(cur == sum){

        // 还剩 nums.length - idx个值未处理

        ans += 1 << (nums.length - idx);

        return;

    }

    // 到达dfs终点

    if(idx == nums.length){

        return;

    }

    // 尝试加入当前数字

    dfs(nums, sum, idx + 1, cur | nums[idx]);

    // 尝试不加入当前数字

    dfs(nums, sum, idx + 1, cur);

}

四、完整代码及注释

[]

class Solution {

public:

    int ans = 0;

    int countMaxOrSubsets(vector<int>& nums) {

        // 按位或是不减的操作，所以全部 | 起来是最大值

        int sum = 0;

        for(auto p : nums){

            sum |= p;

        }

        dfs(nums, sum, 0, 0);

        return ans;

    }

    void dfs(vector<int>& nums, int& m, int idx, int cur){

        // 剪枝

        if(cur == m){

            ans += 1 << (nums.size() - idx);

            return;

        }

        if(idx == nums.size()){

            return;

        }

        // 加上这个数

        dfs(nums, m, idx + 1, cur | nums[idx]);

        // 不加这个数

        dfs(nums, m, idx + 1, cur);

    }

};

[]

class Solution {

    private int ans = 0;

    public int countMaxOrSubsets(int[] nums) {

        // 按位或是不减的操作，所以全部 | 起来是最大值

        int sum = 0;

        for(int p : nums){

            sum |= p;

        }

        dfs(nums, sum, 0, 0);

        return ans;

    }

    public void dfs(int[] nums, int sum, int idx, int cur){

        // 剪枝

        if(cur == sum){

            ans += 1 << (nums.length - idx);

            return;

        }

        if(idx == nums.length){

            return;

        }

        // 加上这个数

        dfs(nums, sum, idx + 1, cur | nums[idx]);

        // 不加这个数

        dfs(nums, sum, idx + 1, cur);

    }

}

五、写在最后

最后上传一个封面图

统计信息

通过次数	提交次数	AC比率
4955	6685	74.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言