推 oin1104: 大師 10/18 18:58
推 orangeNoob: 你好棒 10/18 18:59
→ Lilchicken: 大師 幫我做上古6 10/18 18:59
→ DJYOSHITAKA: 別卷了 10/18 19:31
2044. Count Number of Maximum Bitwise-OR Subsets
## 思路
最大值會是整個nums做or
因為nums最多只有16個數字, 直接暴力搜所有組合
時間複雜度 O(N 2^N)
比解答的DP慢好多QQ
## Code
```python
class Solution:
def countMaxOrSubsets(self, nums: List[int]) -> int:
n = len(nums)
max_or = 0
for num in nums:
max_or |= num
res = 0
for i in range(1 << n):
curr = 0
for j in range(n):
if i & (1 << j):
curr |= nums[j]
if curr == max_or:
res += 1
return res
```
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.26 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729248954.A.EBB.html