class Solution {
public:
int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
}
};
1879. 两个数组最小的异或值之和
给你两个整数数组 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.lengthn == nums2.length1 <= n <= 140 <= nums1[i], nums2[i] <= 107原站题解
java 解法, 执行用时: 11 ms, 内存消耗: 39.1 MB, 提交时间: 2023-10-10 23:40:06
class Solution {
public int minimumXORSum(int[] nums1, int[] nums2) {
int n=nums1.length;
int[] dp=new int[1<<n];
Arrays.fill(dp,(int)1e9);
dp[0]=0;
for(int i=0;i<1<<n;i++){
int cnt=Integer.bitCount(i);
for(int j=0;j<n;j++){
if((1<<j&i)==0){
dp[1<<j|i]=Math.min(dp[1<<j|i],dp[i]+(nums1[cnt]^nums2[j]));
}
}
}
return dp[(1<<n)-1];
}
}
java 解法, 执行用时: 10 ms, 内存消耗: 39.1 MB, 提交时间: 2023-10-10 23:39:43
class Solution {
public int minimumXORSum(int[] nums1, int[] nums2) {
int max=1<<nums1.length;
int ans[]=new int[max];//ans[i]表示的是利用nums1的0——bitcount(i)-1，并且利用了nums2的相应位置的最小值
Arrays.fill(ans,1<<30);
ans[0]=0;
for(int i=1;i<max;i++){
int bitNum=Integer.bitCount(i);//此时的状态具有bitNum个比特，需要通过bitNum-1个比特的状态转移而得
for(int j=0;j<nums1.length;j++){
int pre=i^(1<<j);//比i少一个bit的可能的组合
if(pre<i){ans[i]=Math.min(ans[i],ans[pre]+(nums1[bitNum-1]^nums2[j]));}
}
}
return ans[max-1];
}
}
python3 解法, 执行用时: 380 ms, 内存消耗: 16.5 MB, 提交时间: 2023-10-10 23:38:09
class Solution:
def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
f = [float("inf")] * (1 << n)
f[0] = 0
for mask in range(1, 1 << n):
c = bin(mask).count("1")
for i in range(n):
if mask & (1 << i):
f[mask] = min(f[mask], f[mask ^ (1 << i)] + (nums1[c - 1] ^ nums2[i]))
return f[(1 << n) - 1]
cpp 解法, 执行用时: 20 ms, 内存消耗: 9.5 MB, 提交时间: 2023-10-10 23:37:59
class Solution {
public:
int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
vector<int> f(1 << n, INT_MAX);
f[0] = 0;
for (int mask = 1; mask < (1 << n); ++mask) {
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
f[mask] = min(f[mask], f[mask ^ (1 << i)] + (nums1[__builtin_popcount(mask) - 1] ^ nums2[i]));
}
}
}
return f[(1 << n) - 1];
}
};
golang 解法, 执行用时: 4 ms, 内存消耗: 2.9 MB, 提交时间: 2023-10-10 23:37:14
func minimumXORSum(x, y []int) int {
m := 1 << len(x)
dp := make([]int, m)
for i := range dp {
dp[i] = 2e9
}
dp[0] = 0
for s, dv := range dp[:m-1] {
v := x[bits.OnesCount(uint(s))]
for t, lb := s^(m-1), 0; t > 0; t ^= lb {
lb = t & -t
w := y[bits.TrailingZeros(uint(lb))]
dp[s|lb] = min(dp[s|lb], v^w+dv)
}
}
return dp[m-1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}