Re: [閒聊] 每日leetcode
DP stage i算出只看nums[:i+1]，所有subset對應的element-wise or的value的count
要進入stage i+1，只要把nums[i+1]跟map內所有item or過一次更新map即可
def countMaxOrSubsets(self, nums: List[int]) -> int:
target = 0
for num in nums:
target = target|num
mp = defaultdict(int)
mp[0] = 1
for num in nums:
tmp = defaultdict(int)
for k,v in mp.items():
if k|num < target:
tmp[k|num] += v
else:
tmp[target] += v
for k,v in tmp.items():
mp[k] += v
return mp[target]
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.132.58.28 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1753709861.A.EFE.html
推
07/28 21:42,
4月前
, 1F
07/28 21:42, 1F
→
07/28 21:49,
4月前
, 2F
07/28 21:49, 2F
討論串 (同標題文章)
完整討論串 (本文為第 1478 之 1554 篇)：