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

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

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

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

一、题目描述:

image.png

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


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

image.png

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

二、思路分析:

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

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

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

image.png

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

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

image.png

通过上图,我们就可以将数组的子数组,转成使用 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(2nn)

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

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

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

欢迎点赞,关注,收藏

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

image.png

好了,本次就到这里

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

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

目录
打赏
0
0
0
0
63
分享
相关文章
LeetCode-2044 统计按位或能得到最大值子集的数目
LeetCode-2044 统计按位或能得到最大值子集的数目
LeetCode每日一题——1684. 统计一致字符串的数目
给你一个由不同字符组成的字符串 allowed 和一个字符串数组 words 。如果一个字符串的每一个字符都在 allowed 中,就称这个字符串是 一致字符串 。
95 0
基础算法练习200题12、统计奇偶数
基础算法练习200题12、统计奇偶数
109 0
|
9月前
|
算法编程(二十九):统计一致字符串的数目
算法编程(二十九):统计一致字符串的数目
103 0
给出任意一个正整数,算出大于它的最小不重复数——最高效[2014百度笔试题]
<p>程序很简单,一看就懂,我就不多介绍了,直接上代码。</p> <p></p> <pre code_snippet_id="191807" snippet_file_name="blog_20140217_1_7068119" name="code" class="cpp">/** * 给出任意一个正整数,算出大于它的最小不重复数(即不存在相邻两个数相同的情况) */ #inclu
1490 0
OpenJudge就算概论-统计字符数
/*===================================== 统计字符数 总时间限制: 1000ms 内存限制: 65536kB 描述 判断一个由a-z这26个字符组成的字符串中哪个字符出现的次数最多 输入 第1行是测试数据的组数n,每组测试数据占1行,是一个由a-z这26个字符组成的字符串 每组测试数据之间有一个空行,每行数据不超过1000个字符且非空 输出 n行,每行输出对应一个输入。
990 0
LeetCode 2044. 统计按位或能得到最大值的子集数目(状态压缩DP)
LeetCode 2044. 统计按位或能得到最大值的子集数目(状态压缩DP)
167 0
|
9月前
|
leetcode2719. 统计整数数目
leetcode2719. 统计整数数目
64 0
求两个数对应二进制位不同的个数(深度剖析+补充例题)
求两个数对应二进制位不同的个数(深度剖析+补充例题)
208 0
求两个数对应二进制位不同的个数(深度剖析+补充例题)
【算法挨揍日记】day06——1004. 最大连续1的个数 III、1658. 将 x 减到 0 的最小操作数
1004. 最大连续1的个数 III 题目描述: 给定一个二进制数组 nums 和一个整数 k,如果可以翻转最多 k 个 0 ,则返回 数组中连续 1 的最大个数 。
425 1

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等