2044.统计按位或能得到最大值的子集数目
2044.统计按位或能得到最大值的子集数目
题解
- 二进制枚举，真的很巧妙，比如3瓶水，枚举所有状态，可以看出7个状态，其对应的就是某个数的二进制位，
所以用二进制枚举来选择数组下标的话，则刚好可以枚举出所有的非空子集 - 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 }
