推 DJYOMIYAHINA: 別卷了 11/08 08:38
→ sixB: constraint number < 2^mxbit 就沒啥意思了 11/08 08:55
→ sixB: 每個result都 = mask那你做n次幹嘛ㄋ 11/08 08:55
推 scmono: 大師 我不敢想像你這樣的高手月薪會有多少 11/08 09:08
→ sixB: 好了啦 11/08 10:47
1829
這兩天都bitwise好好玩
##
一次少一個 先做prefix sum
xor k完找max, k < 2^mxbit
意思就是xor完 mxbit以下都是1
做一個mxbit都是1的mask
presum xor k = max result = presum or mask
所以 presum xor maxresult = k
然後順序反了==翻一下
class Solution {
public:
vector<int> getMaximumXor(vector<int>& nums, int mxb) {
int n = nums.size();
vector<int> res(n, 0);
res[0] = nums[0];
int mask = (1 << mxb) - 1;
//presum
for(int i = 1; i < n; i++){
res[i] = nums[i] ^ res[i-1];
}
for(int i = n-1; i >= 0; i--){
res[i] ^= (res[i] | mask);
}
reverse(res.begin(), res.end());
return res;
}
};
-----
Sent from JPTT on my iPad
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731026036.A.AD4.html