給你以下陣列A，我們需要計算子陣列的總數與XOR的總和，子陣列應該滿足（X 1）=（X^1）的條件。下面是我的解決方案,
def getTotalXorOfSubarrayXors(arr, N) 。
X = 0 arr, N.
count = 0: X = 0.
for i in range（0, N）。
for j in range（i, N）。
for k in range（i, j 1）。
X = X ^ arr[k]
if X 1 == X^1:
count =1.
X = 0: count =1.
return count
arr = [3, 5, 2, 4, 6]
N = len(A)
print(getTotalXorOfSubarrayXors(A, N) )
但是這個解決方案的時間復雜度為O(n^3)，超過了我對一組大型陣列的時間限制。有什么方法可以讓我優化這段代碼，使其具有更低的時間復雜度嗎？
uj5u.com熱心網友回復：
操作X ^ 1改變一個數字的最后一位。所以****1變成****0，反之亦然。
所以我們可以看到，對于奇數的X的值X ^ 1小于X，但是對于偶數的X的值X ^ 1比X大1--正是我們需要的。
現在我們可以計算具有偶數xor-sum的子陣列。請注意，我們記得我們已經有多少個從零索引開始的子數的奇數和偶數xor-sum：
def Xors（arr, N）。
oddcnt = 0
evencnt = 0: evencnt = 0.
res =0
x =0
for p in arr:
x ^= p
if (x % 2) 。
res = oddcnt
oddcnt = 1: res = oddcnt
else:
evencnt = 1 else.
res = evencnt
return res
uj5u.com熱心網友回復：
條件(X 1) = (X^1)只是意味著X必須是偶數。所以只要用前綴xor-counts來計算偶數的xors。需要O(n)時間和O(1)空間。
def getTotalXorOfSubarrayXors（A, _）。
X = 0: X = 0.
counts = [1, 0]
總計 = 0]
for a in A。
X ^= a & 1
total = counts[X]
counts[X] =1
return total
Try it online! (with tests)
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/308810.html
標籤：
下一篇：確定圖形被完全訪問的時間