前往
大廳
主題

LeetCode - 2527. Find Xor-Beauty of Array 解題心得

Not In My Back Yard | 2023-11-29 12:00:10 | 巴幣 0 | 人氣 57

題目連結:


題目意譯:
你被給定一個索引值從 0 開始的整數陣列 nums。

三個索引值 i 、 j 和 k 的有效值定義為 ((nums[i] | nums[j]) & nums[k])。

一陣列的 定義為當中所有可能的三元組 (i, j, k) 之有效值全部 XOR 在一起之值,其中 0 ≦ i, j, k < n。

回傳 nums 的 xor-beauty 值。

注意到:
val1 | val2 為 val1 和 val2 按位元 OR 之值。
val1 | val2 為 val1 和 val2 按位元 AND 之值。

限制:
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 9



範例測資:
範例 1:
輸入: nums = [1,4]
輸出: 5
解釋:
所有三元組以及它們對應的有效值為下列:
- (0,0,0) 有著有效值 ((1 | 1) & 1) = 1
- (0,0,1) 有著有效值 ((1 | 1) & 4) = 0
- (0,1,0) 有著有效值 ((1 | 4) & 1) = 1
- (0,1,1) 有著有效值 ((1 | 4) & 4) = 4
- (1,0,0) 有著有效值 ((4 | 1) & 1) = 1
- (1,0,1) 有著有效值 ((4 | 1) & 4) = 4
- (1,1,0) 有著有效值 ((4 | 4) & 1) = 0
- (1,1,1) 有著有效值 ((4 | 4) & 4) = 4
該陣列的 xor-beauty 值為以上所有有效值之 XOR 值 = 1 ^ 0 ^ 1 ^ 4 ^ 1 ^ 4 ^ 0 ^ 4 = 5。

範例 2:
輸入: nums = [15,45,20,2,34,35,5,44,32,30]
輸出: 34
解釋: 給定陣列的 xor-beauty 值為 34。


解題思維:
可以看到我們實際上可以把每一個位元分開來觀察(因為所有操作都是按位元,所以各個位元之間彼此獨立)。因此我們先單看一個位元:
    可以看到 nums[k] 是 0 的時候,nums[i] 和 nums[j] 挑什麼都不會影響結果,式子的值都是 0。

    而所有式子值是 0 者,不會影響整體 XOR 之值(根據 XOR 之性質本身)。這代表著 nums[k] 固定是 1,因此可以把外層的「& nums[k]」拿掉(以下固定省略此部分)。

    而因為最後要全部 XOR 在一起的緣故,因此 (nums[i] | nums[j]) 與 (nums[j] | nums[i]) 會彼此抵銷,除了 i == j 的情況以外。因此最後剩下的且具有潛在影響力的式子為 (nums[i] | nums[i]),此即為 nums[i] 本身。

因此對於單一位元而言,所求等價於 nums 中所有數字 XOR 之結果。而因為所有位元彼此獨立,因此整體的所求便是 nums 中所有數字按位元 XOR 之結果。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作