題目
給你兩個整數數組?nums1 和?nums2?，它們長度都為?n?。
兩個數組的 異或值之和?為?(nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + … + (nums1[n - 1] XOR nums2[n - 1])?（下標從 0 開始）。
比方說，[1,2,3] 和?[3,2,1]?的 異或值之和?等于?(1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4?。
請你將?nums2?中的元素重新排列，使得 異或值之和?最小?。
請你返回重新排列之后的 異或值之和?。
示例 1：
輸入：nums1 = [1,2], nums2 = [2,3]
輸出：2
解釋：將 nums2 重新排列得到 [3,2] 。
異或值之和為 (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2 。
示例 2：
輸入：nums1 = [1,0,3], nums2 = [5,3,4]
輸出：8
解釋：將 nums2 重新排列得到 [5,4,3] 。
異或值之和為 (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8 。
解題思路
假設n是數組的長度，這題可以看成nums1的前c個數字，在nums2中找出c個數字，一一對應，從而使得異或和最小，因此我們可以使用n位的二進制數即可表示nums2的不同取值狀態，第j位為1代表該情況下，nums2[j]已經被選擇了.
- 例如對于nums1 = [1,2], nums2 = [2,3]
- 01表示nums2[1]=3已經被選擇用于與nums1的前一個數字組成異或和了，dp[01]就是代表這種情況的最小異或和
- 10表示nums2[0]=2已經被選擇用于與nums1的前一個數字組成異或和了
所以dp[11]應該從dp[01]或者dp[10]轉移而來，并且需要加上新產生的異或值
狀態轉移
找出當前狀態的上一步狀態，進行轉移
- 遍歷nums2的每一個元素
(1<<j)&i>0代表nums2[j]在當前狀態下已經被選擇，所以我們將這個選擇取消（將這一位置零），就是上一步的其中一種狀態dp[(1<<j)^i]
for j := 0; j < n; j++ {if (1<<j)&i>0{val:=dp[(1<<j)^i]+(nums1[cnt(i)-1]^nums2[j])if val<dp[i]{dp[i]=val}}}
代碼
func minimumXORSum(nums1 []int, nums2 []int) (res int){n:=len(nums1)cnt := func(cur int) (res int) {for k := 0; k < 31; k++ {res+=1&curcur>>=1}return}mask:=1<<ndp := make([]int, mask)for i := 1; i < mask; i++{dp[i]=2e9}for i := 1; i < mask; i++ {for j := 0; j < n; j++ {if (1<<j)&i>0{val:=dp[(1<<j)^i]+(nums1[cnt(i)-1]^nums2[j])if val<dp[i]{dp[i]=val}}}}return dp[mask-1]
}
