DeepSeek LeetCode 1879.两个数组最小的异或值之和 Go实现
这道题是经典的状压 DP,因为数据范围 n <= 14,我们可以用一个二进制掩码表示 nums2 的使用情况。
思路
1. 定义 dp[mask]:表示已经为 nums1 的前 k 个元素(k = bits.OnesCount(mask))匹配了 nums2 中对应 mask 集合的元素,此时的最小异或和。
2. 转移时,枚举 mask 中每一个被使用的位 j(即 nums2[j] 已配对),它一定是和 nums1[k-1] 配对,所以:
```
dp[mask] = min_{j ∈ mask} ( dp[mask ^ (1<<j)] + (nums1[k-1] ^ nums2[j]) )
```
3. 初始化 dp[0] = 0,其余为无穷大。最终答案为 dp[(1<<n) - 1]。
时间复杂度 O(n * 2^n),空间 O(2^n),对于 n=14 完全可行。
Go 实现
```go
func minimumXORSum(nums1 []int, nums2 []int) int {
n := len(nums1)
total := 1 << n
dp := make([]int, total)
for i := 1; i < total; i++ {
dp[i] = 1 << 30 // 初始化为一个大数
}
// dp[0] 已为 0
for mask := 1; mask < total; mask++ {
// 已经匹配的 nums1 的数量
k := bits.OnesCount(uint(mask))
// 当前要匹配的是 nums1[k-1]
x := nums1[k-1]
// 尝试 mask 中每一个被选中的 nums2 元素
for j := 0; j < n; j++ {
if mask>>j&1 == 1 {
prev := mask ^ (1 << j)
val := dp[prev] + (x ^ nums2[j])
if val < dp[mask] {
dp[mask] = val
}
}
}
}
return dp[total-1]
}
```
复杂度
· 时间复杂度:O(n * 2^n)
· 空间复杂度:O(2^n)
如果想让代码在 LeetCode 上直接运行,别忘了加上 import "math/bits"。
更多推荐




所有评论(0)