Leetcode 2044.统计按位或能得到最大值的子集数目

题目描述

给你一个整数数组nums。请你找出nums子集按位或可能得到的最大值，并返回按位或能得到最大值的 不同非空子集的数目 。
如果数组a可以由数组b删除一些元素（或不删除）得到，则认为数组a是数组b的一个子集。如果选中的元素下标位置不一样，则认为两个子集不同。
对数组a执行按位或，结果等于 a[0] OR a[1] OR ... OR a[a.length - 1]（下标从0开始）。

提示：

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

题解：

查找子串，当然是选择二进制状态压缩的暴力查找。

class Solution {
public:
    int countMaxOrSubsets(vector<int>& nums) {
        int ans=1,maxn=-1,n=nums.size();
        for(int i=1;i<=(1<<n);i++){
            int cur=0;//记录当前子集所有数字的按位或值
            for(int j=0;j<n;j++)//枚举nums[j]，看看是否是所枚举的子集中的数字
                if(i&(1<<j)) cur|=nums[j];
            if(cur==maxn) ans++;//更新最大值和答案数量
            else if(cur>maxn){
                maxn=cur;ans=1;
            }
        }
        return ans;
    }
};

题外话

记录我的小宋老师。
没想到宋某不仅约会时拿出电脑给我演示写状态压缩，还由于我没明白，半夜两点半开了腾讯会议共享屏幕，继续认认真真地给我讲。可能最动人的情话就是我给你讲题和改bug吧。
这是浪漫吗？我不知道。但这是我们独一无二的爱情啊。