推 SecondRun: 別捲了 07/31 22:09
→ wwndbk: 別捲了 07/31 22:14
898. Bitwise ORs of Subarrays
思路 :
用三個map : rec、prev、cur
rec記錄所有出現過的or值
prev紀錄0~i-1所有可能的or值
cur紀錄prev裡的or值跟nums[i]or後的結果以及nums[i]自己本身
最後回傳rec裡有多少個or值就好
golang code :
func subarrayBitwiseORs(nums []int) int {
prev := make(map[int]bool)
rec := make(map[int]bool)
for _, val := range nums {
cur := make(map[int]bool)
cur[val], rec[val] = true, true
for k := range prev {
num := k | val
cur[num] = true
rec[num] = true
}
prev = cur
}
return len(rec)
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1753970932.A.FE6.html