2044. 统计按位或能得到最大值的子集数目 :「二进制枚举」&「状压 DP」&「DFS」

简介: 2044. 统计按位或能得到最大值的子集数目 :「二进制枚举」&「状压 DP」&「DFS」

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 2044. 统计按位或能得到最大值的子集数目 ,难度为 中等


Tag : 「二进制枚举」、「位运算」、「DFS」、「状压 DP」


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


如果数组 aa 可以由数组 bb 删除一些元素(或不删除)得到,则认为数组 aa 是数组 bb 的一个 子集 。如果选中的元素下标位置不一样,则认为两个子集 不同 。


对数组 aa 执行 按位或 ,结果等于 a[0]a[0]ORa[1]a[1]OR...ORa[a.length - 1]a[a.length1](下标从 00 开始)。


示例 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 <= 161<=nums.length<=16
  • 1 <= nums[i] <= 10^51<=nums[i]<=105


二进制枚举



nnnumsnums 的长度,利用 nn 不超过 1616,我们可以使用一个 int 数值来代指 numsnums 的使用情况(子集状态)。


假设当前子集状态为 statestatestatestate 为一个仅考虑低 nn 位的二进制数,当第 kk 位为 11,代表 nums[k]nums[k] 参与到当前的按位或运算,当第 kk 位为 00,代表 nums[i]nums[i] 不参与到当前的按位或运算。


在枚举这 2^n2n 个状态过程中,我们使用变量 max 记录最大的按位或得分,使用 ans 记录能够取得最大得分的状态数量。


代码:


class Solution {
    public int countMaxOrSubsets(int[] nums) {
        int n = nums.length, mask = 1 << n;
        int max = 0, ans = 0;
        for (int s = 0; s < mask; s++) {
            int cur = 0;
            for (int i = 0; i < n; i++) {
                if (((s >> i) & 1) == 1) cur |= nums[i];
            }
            if (cur > max) {
                max = cur; ans = 1;
            } else if (cur == max) {
                ans++;
            }
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:令 numsnums 长度为 nn,共有 2^n2n 个子集状态,计算每个状态的按位或得分的复杂度为 O(n)O(n)。整体复杂度为 O(2^n * n)O(2nn)
  • 空间复杂度:O(1)O(1)


状压 DP



为了优化解法一中「每次都要计算某个子集的得分」这一操作,我们可以将所有状态的得分记下来,采用「动态规划」思想进行优化。


需要找到当前状态 statestate 可由哪些状态转移而来:假设当前 statestate 中处于最低位的 11 位于第 idxidx 位,首先我们可以使用 lowbit 操作得到「仅保留第 idxidx11 所对应的数值」,记为 lowbitlowbit,那么显然对应的状态方程为:


f[state] = f[state - lowbit] \wedge nums[idx]f[state]=f[statelowbit]nums[idx]

再配合我们从小到大枚举所有的 statestate 即可确保计算 f[state]f[state] 时所依赖的 f[state - lowbit]f[statelowbit] 已被计算。


最后为了快速知道数值 lowbitlowbit 最低位 11 所处于第几位(也就是 idxidx 为何值),我们可以利用 numsnums 长度最多不超过 1616 来进行「打表」预处理。


代码:


class Solution {
    static Map<Integer, Integer> map = new HashMap<>();
    static {
        for (int i = 0; i < 20; i++) map.put((1 << i), i);
    }
    public int countMaxOrSubsets(int[] nums) {
        int n = nums.length, mask = 1 << n;
        int[] f = new int[mask];
        int max = 0, ans = 0;
        for (int s = 1; s < mask; s++) {
            int lowbit = (s & -s);
            int prev = s - lowbit, idx = map.get(lowbit);
            f[s] = f[prev] | nums[idx];
            if (f[s] > max) {
                max = f[s]; ans = 1;
            } else if (f[s] == max) {
                ans++;
            }
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:O(2^n)O(2n)
  • 空间复杂度:O(2^n)O(2n)


DFS



解法一将「枚举子集/状态」&「计算状态对应的得分」两个过程分开进行,导致了复杂度上界为 O(2^n * n)O(2nn)


事实上,我们可以在「枚举子集」的同时「计算相应得分」,设计 void dfs(int u, int val)DFS 函数来实现「爆搜」,其中 uu 为当前的搜索到 numsnums 的第几位,valval 为当前的得分情况。


对于任意一位 xx 而言,都有「选」和「不选」两种选择,分别对应了 dfs(u + 1, val | nums[x])dfs(u + 1, val) 两条搜索路径,在搜索所有状态过程中,使用全局变量 maxans 来记录「最大得分」以及「取得最大得分的状态数量」。


该做法将多条「具有相同前缀」的搜索路径的公共计算部分进行了复用,从而将算法复杂度下降为 O(2^n)O(2n)


代码:


class Solution {
    int[] nums;
    int max = 0, ans = 0;
    public int countMaxOrSubsets(int[] _nums) {
        nums = _nums;
        dfs(0, 0);
        return ans;
    }
    void dfs(int u, int val) {
        if (u == nums.length) {
            if (val > max) {
                max = val; ans = 1;
            } else if (val == max) {
                ans++;
            }
            return ;
        }
        dfs(u + 1, val);
        dfs(u + 1, val | nums[u]);
    }
}
复制代码


  • 时间复杂度:令 numsnums 长度为 nn,共有 2^n2n 个子集状态。整体复杂度为 O(2^n)O(2n)
  • 空间复杂度:忽略递归带来的额外空间开销,复杂度为 O(1)O(1)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.2044 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
消息中间件 安全 Kafka
Kafka、RabbitMQ、RocketMQ 消息中间件的对比 | 消息发送性能篇
消息中间件性能究竟哪家强? 带着这个疑问,我们消息队列测试小组对常见的三类消息产品(Kafka、RabbitMQ、RocketMQ)做了性能比较。
26445 129
|
Java 开发工具 开发者
IDEA中配置类与方法注释模板
IDEA是当前使用最为广泛的集成开发工具之一,其功能的多样性与便捷性为开发者在开发过程提供了很多方便。 我们在用IDEA创建java类和方法的时候,可以自动生成文档注释,便于代码的阅读与理解。
IDEA中配置类与方法注释模板
|
前端开发 测试技术 数据库
使用Ruby on Rails进行快速Web开发的技术探索
【8月更文挑战第12天】Ruby on Rails以其高效、灵活和易于维护的特点,成为了快速Web开发领域的佼佼者。通过遵循Rails的约定和最佳实践,开发者可以更加专注于业务逻辑的实现,快速构建出高质量的Web应用。当然,正如任何技术框架一样,Rails也有其适用场景和局限性,开发者需要根据项目需求和个人偏好做出合适的选择。
|
9月前
|
人工智能 自然语言处理 架构师
字节面试: es怎么提升性能和精准度?(尼恩独家,史上最全)
本文由40岁老架构师尼恩撰写,针对ES(Elasticsearch)提升搜索性能和精准度的面试题进行详细解析。文章首先指出,提升ES速度和精准度是两个独立的问题,分别涉及性能优化和精准度优化。这些内容不仅有助于应对面试中的难题,还能帮助开发者在实际项目中构建更高效的搜索系统。尼恩强调,掌握这些知识后可以在面试中“吊打”面试官,轻松获得理想Offer。同时,他还提供了《尼恩Java面试宝典PDF》等资源供读者学习参考。
|
机器学习/深度学习 传感器 算法
改进黑猩猩优化算法SLWCHOA 可直接运行 提供23个基准函数对比与秩和检验 注释详细适合新手小白~Matlab
改进黑猩猩优化算法SLWCHOA 可直接运行 提供23个基准函数对比与秩和检验 注释详细适合新手小白~Matlab
|
SQL API
【vision transformer】DETR原理及代码详解(四)
【vision transformer】DETR原理及代码详解
798 0
|
存储 Java 关系型数据库
【Elasticsearch 技术分享】—— 十张图带大家看懂 ES 原理 !明白为什么说:ES 是准实时的!
说到 Elasticsearch ,其中最明显的一个特点就是 near real-time 准实时 —— 当文档存储在Elasticsearch中时,将在1秒内以几乎实时的方式对其进行索引和完全搜索。那为什么说 ES 是准实时的呢?
1506 0
SQL:union all和union的区别 和使用
SQL:union all和union的区别 和使用
|
关系型数据库 MySQL Unix
nginx代理DB & ip限制
nginx代理DB & ip限制
|
XML 开发框架 监控
面试题:springboot比spring有哪些优点?
面试题:springboot比spring有哪些优点?
389 0