golang力扣leetcode 2044.统计按位或能得到最大值的子集数目

简介: golang力扣leetcode 2044.统计按位或能得到最大值的子集数目

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

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

题解

  1. 二进制枚举,真的很巧妙,比如3瓶水,枚举所有状态,可以看出7个状态,其对应的就是某个数的二进制位,所以用二进制枚举来选择数组下标的话,则刚好可以枚举出所有的非空子集
  2. dfs,对于每一个数,只有选与不选
000 001 010
011 100 101
110 111
func binaryEnumeration() {
  for i := 0; i <= 7; i++ {
    for j := 0; j < 3; j++ {
      if i>>j&1 == 1 {
        fmt.Println(i, "的第", j+1, "个二进制位为1")
      }
    }
  }
}

代码

# 暴力枚举
func countMaxOrSubsets1(nums []int) (ans int) {
  maxOr := 0
  n := 1<<len(nums) - 1 //2^n - 1 个非空子集
  for i := 1; i <= n; i++ {
    or := 0
    for j, v := range nums {
      if i>>j&1 == 1 {
        or |= v
      }
    }
    if or > maxOr {
      maxOr = or
      ans = 1
    } else if or == maxOr {
      ans++
    }
  }
  return
}
# dfs
func countMaxOrSubsets2(nums []int) (ans int) {
  maxOr := 0
  var dfs func(int, int)
  dfs = func(pos int, or int) {
    if pos == len(nums) {
      if or > maxOr {
        maxOr = or
        ans = 1
      } else if or == maxOr {
        ans++
      }
      return
    }
    dfs(pos+1, or|nums[pos]) //选当前的值
    dfs(pos+1, or)           //不选当前的值
  }
  dfs(0, 0)
  return
}
目录
相关文章
|
3月前
2670.找出不同元素数目差数组-力扣(LeetCode)
2670.找出不同元素数目差数组-力扣(LeetCode)
24 0
|
3月前
|
索引
821.字符的最短距离-力扣(LeetCode)
821.字符的最短距离-力扣(LeetCode)
25 0
|
4月前
|
算法 数据可视化 数据挖掘
最佳加油站选择算法:解决环路加油问题的两种高效方法|LeetCode力扣134
最佳加油站选择算法:解决环路加油问题的两种高效方法|LeetCode力扣134
|
15天前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
47 6
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析,判断一棵树B是否是另一棵树A的子结构。
40 4
|
2月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
90 2
|
15天前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
2月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
40 7
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码,确保min、push和pop操作的时间复杂度为O(1)。
21 4