→ Smallsh: 大師 05/30 12:03
→ devilkool: 你好聰明 05/30 12:12
→ JIWP: 別卷了 05/30 12:17
※ 引述《ray90514 ()》之銘言：
: 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;
: }
: };
思路:
題目要求尋找a == b
a == b可以換成 a^b == 0
a^b == 0 等於
arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]^arr[j] ^ arr[j + 1] ^ ... ^ arr[k] == 0
我們先把arr[i]變成arr[i] ^ arr[i - 1] ^ ... ^ arr[0]
所以arr[i+1] ^= arr[i]
因為處理不到原本的arr[0] 所以開頭插入0
假如arr[i] == arr[i+1] 代表
arr[i+1] ^ arr[i] ^ arr[i - 1] ^ ... ^ arr[0]等於0
所以相減加進res
Python Code:
class Solution:
def countTriplets(self, arr: List[int]) -> int:
res = 0
arr.insert(0,0)
for i in range(len(arr)-1):
arr[i+1] ^= arr[i]
for i in range(len(arr)):
for j in range(i+1,len(arr)):
if arr[i] == arr[j]:
res += j - i -1
return res
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.119.235.6 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1717041579.A.1D8.html