【刷题日记】2044. 统计按位或能得到最大值的子集数目

本次刷题日记的第 8 篇，力扣题为：2044. 统计按位或能得到最大值的子集数目 ，中等

一、题目描述：

看题一遍好像没有怎么看明白这题到底想干啥，输入的数组和返回值有啥关系？看了示例也有点蒙圈

然后再回头仔细查看最初题目的第一句话，就能明白到底是在说什么了

不知道 xdm 有没有这种感受 ！！！

二、思路分析：

1、这道题考察了什么思想？你的思路是什么？

那么我们仔细来看看，这个题到底是需要我们做些什么呢？我们一步一步的来拆解一下：

• 题目中会给出一个数组，我们需要找到这个数组的子数组，是非空的子数组
• 计算每一个子数组元素的按位或的结果，并且找到这些结果中，结果数据最大的子数组有几个

我们可以看到，做这个题，其实我们就是要明确有这样的包含关系，我们需要的是最里面的的按位或结果最大的子数组

我们可以使用题目中的示例来推演一下：以 nums = [3,2,1,5] 为例

通过上图，我们就可以将数组的子数组，转成使用 bit 位的方式来进行处理，数组长度为 4， 我们就用 4 个 bit 位来进行表示，bit 位对应位置为 1 ，表示 nums 数组对应位置的数字被选中

如果 bit 位对应位置为 0，则表示 nums 数组对应位置的数字没有选中

这个时候，我可以按照子数组中 bit 为 1 的位置对应数组中的数字，作为一个集合，总共 2 的 n 次方 -1 个集合，每个集合计算按位或的结果，最终筛选出按位或最大的值的子数组个数即可

2、尝试编码

根据上述逻辑和分析，我们就可以翻译成如下代码

编码如下：

func countMaxOrSubsets(nums []int) int {
    maxOr := 0
    or := 0
    res := 0
    for i := 1; i< 1 << len(nums); i++ {
         or = 0
         for j,num := range nums {
            if (i >> j) & 1 == 1 {
                 or = or | num
             } 
         }
         if or > maxOr {
             maxOr = or
             res = 1
         }else if or == maxOr {
            res++
         }else{}
    }
    return res
}

• maxOr 为记录最大的值，当该值被刷新的时候，结果集重新更新为 1
• or 表示当前集合的按位或结果
• res 表示按位或最大值的集合个数
• 编码中的第一个 for 循环表示 ，轮询集合的个数
• 第二个 for 循环，表示轮询 nums 数组中的元素，找出本次集合 bit 位 为 1 的元素，并计算 按位或 的结果

四、总结：

本题的时间复杂度会相对较高，因为每一次都需要去遍历数组的长度，时间复杂度是：

O(2n∗n)O(2^n*n)O(2n∗n)

空间复杂度是数组的长度 O(n)

原题地址：2044. 统计按位或能得到最大值的子集数目

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~