Re: [閒聊] 每日leetcode已回收
差點忘記寫
最近都不怎麼想寫每日，我好爛
1863. Sum of All Subset XOR Totals
給一個array，請回傳所有subset的XOR totals的總和
思路 :
正常backtracking下去就可以秒解了，沒什麼難度
然後有看到一個神奇的解法
去計算每個位元出現的次數
假設在array有k個元素
且第n個bit是1的元素有x個、是0的元素有y個，x+y=k
由於XOR的特性，我們只需要關注subset中第n位bit 1的總和是奇數的情況
有2^(x-1)*2^y=2^(k-1)種，也就是2^n會出現2^(k-1)次
接著要看第n位bi有沒有出現1，所以用for迴圈OR所有元素
接著將結果乘上2^(k-1)次就好
golang code
func subsetXORSum(nums []int) int {
res:=0
for _,val:=range nums{
res |= val
}
return res<<(len(nums)-1)
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.141.98.100 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716220514.A.088.html
討論串 (同標題文章)
完整討論串 (本文為第 250 之 1554 篇)：