推 DJYOSHITAKA: 大師 05/30 10:42
推 sustainer123: 今天這題好難:((( 恨位運算 05/30 10:42
1442. Count Triplets That Can Form Two Arrays of Equal XOR
xor sum i to j = xor sum 0 to j ^ 0 to i - 1
xor sum i to j - 1 = sum 0 to j - 1 ^ 0 to i - 1 = j to k = 0 to k ^ 0 to j - 1
兩邊的xor sum 0 to j - 1可以消掉
所以找兩個從0開始xor相等的就是i 跟k
j是其中任意的數
class Solution {
public:
int countTriplets(vector<int>& arr) {
vector<int> v(arr.size());
int sum = 0;
int ans = 0;
for(int i = 0; i < arr.size(); i++){
v[i] = sum;
sum ^= arr[i];
for(int j = 0; j < i; j++){
if(v[j] == sum){
ans += i - j;
}
}
}
return ans;
}
};
--
悠閒的 平凡的 瑣碎的 無意義的
https://i.imgur.com/sMJiZp3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.36.50.252 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1717036846.A.41C.html