主題
題目連結：
題目意譯：
你被給定一個大小為 n 的整數陣列 pref。請找到一個大小為 n 的陣列 arr，使得：
pref[i] = arr[0] ^ arr[1] ^ … ^ arr[i].
注意到 ^ 代表著按位元（Bitwise）XOR 之操作。
可以證明答案唯一。
限制：
1 ≦ pref.length ≦ 10 ^ 5
0 ≦ pref[i] ≦ 10 ^ 6
範例測資：
範例 1：
輸入： pref = [5,2,0,3,1]
輸出： [5,7,2,3,2]
解釋： 從陣列 [5,7,2,3,2] 我們可以得到以下：
- pref[0] = 5。
- pref[1] = 5 ^ 7 = 2。
- pref[2] = 5 ^ 7 ^ 2 = 0。
- pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3。
- pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1。
範例 2：
輸入： pref = [13]
輸出： [13]
解釋： 我們有 pref[0] = arr[0] = 13。
解題思維：
可以看到 arr[0] 即為 pref[0]（根據條件）。而剩下的 arr[i] 即為 pref[i] ^ pref[i - 1]，以下為其原因：
因為 XOR 運算有結合律且 X ^ X = 0，其中 X 為任意整數。所以 pref[i] ^ pref[i - 1] 根據定義為
(arr[0] ^ arr[1] ^ … ^ arr[i - 1] ^ arr[i]) ^ (arr[0] ^ arr[1] ^ … ^ arr[i - 1])
移動一下項次可得
(arr[0] ^ arr[0]) ^ (arr[1] ^ arr[1]) ^ … ^ (arr[i - 1] ^ arr[i - 1]) ^ arr[i]
兩兩抵銷，最終只剩下 arr[i]。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
