题目
题目链接,https://leetcode.com/problems/minimum-xor-sum-of-two-arrays/
You are given two integer arrays nums1
and nums2
of length n
.
The XOR sum of the two integer arrays is (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1])
(0-indexed).
- For example, the XOR sum of
[1,2,3]
and[3,2,1]
is equal to(1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4
.
Rearrange the elements of nums2
such that the resulting XOR sum is minimized.
Return the XOR sum after the rearrangement.
Example 1:
Input: nums1 = [1,2], nums2 = [2,3] Output: 2 Explanation: Rearrangenums2
so that it becomes[3,2]
. The XOR sum is (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.
Example 2:
Input: nums1 = [1,0,3], nums2 = [5,3,4] Output: 8 Explanation: Rearrangenums2
so that it becomes[5,4,3]
. The XOR sum is (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8.
Constraints:
n == nums1.length
n == nums2.length
1 <= n <= 14
0 <= nums1[i], nums2[i] <= 107
思路
题目大意是给定等长数组nums1和nums2,重新排列nums2,使得sum(nums1[0] ^ nums2[0] + nums1[1] ^ nums2[1] + ….. + nums1[-1] ^ nums2[-1])最小。
题目里的运算方式是xor,我们知道,xor运算的性质和大小其实没有太大关系;这道题的数量级又略大(n<=14),基本排除了暴力搜索的可能,所以这道题只能记忆化搜索或者动归。
题目提示了可以使用bitmask,我们就顺着这个思路推导下动规的递推方程。
dp[mask] = num2中下标在mask为1的元素与num1的异或值之和的最小值。
于是我们有如下的递推关系
dp[0] = 0
dp[mask] = min(nums1[mask_1_cnt – 1] ^ nums2[i] + dp(mask & ~(1 << i))) , 其中mask_1_cnt为mask中1的个数,i为mask中1的位数。
这里稍微展开一下,为什么num1的下标要取mask_1_cnt – 1,而不是遍历range(1, len(nums))呢——当然可以,但是如果遍历1~len(nums) – 1,我们就需要另外一个状态来记录nums1使用过哪些元素了,时间空间复杂度都会大上几个数量级(n*2n->n2*22n)。
——递推关系是否足够简洁很重要,直接决定了代码会不会TLE或者MLE。
代码
我比较喜欢自顶向下的写法,这里贴一下。
需要注意的是,python里的位运算优先级比四则运算低(详情见链接),所以做位运算的时候一定注意加括号。
时间复杂度为O(n * 2n)
class Solution(object):
def minimumXORSum(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: int
"""
N = len(nums1)
def count_bit(bits):
s = bin(bits)
return len([i for i in s if i == '1'])
l = [None] * (1 << len(nums1))
l[0] = 0
def dp(bits):
if l[bits] is not None:
return l[bits]
ret = None
idx = count_bit(bits) - 1
for i in range(len(nums1)):
if (1 << i) & bits == 0:
continue
cur_ans = (nums1[idx] ^ nums2[i]) + dp(bits & ~(1 << i))
ret = cur_ans if ret is None else min(cur_ans, ret)
l[bits] = ret
return ret
return dp((1 << len(nums1)) - 1)
提交上去,AC。收工!
等等,还没完。
神仙代码
翻了翻这道题的提交记录,发现python2的第一名居然只有三行,这是什么鬼?必须要贴一下这个代码。
from scipy.optimize import linear_sum_assignment as LSA
class Solution(object):
def minimumXORSum(self, nums1, nums2):
cost = [[x^y for y in nums2] for x in nums1]
return sum(cost[x][y] for x,y in zip(*LSA(cost)))
翻了翻文档,才搞明白,linear_sum_assignment是scipy里的指派问题api,使用的算法为匈牙利算法,时间复杂度O(n3)。参考链接见文末。
本地跑一下,简直快的不像话。
当然weekly contest想必不能这么搞就是了……
姿势水平提高了!
参考链接
1.scipy中的linear_sum_assignment,https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html#scipy.optimize.linear_sum_assignment
2.匈牙利算法,维基百科,https://zh.m.wikipedia.org/zh-hans/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95。
3.任务分配问题,维基百科,https://zh.m.wikipedia.org/zh-hans/%E4%BB%BB%E5%8A%A1%E5%88%86%E9%85%8D%E9%97%AE%E9%A2%98
——此处是内容的分割线——
除非注明,否则均为广陌原创文章,转载必须以链接形式标明本文链接
本文链接:https://www.utopiafar.com/2022/07/07/leetcode-1879-minimum-xor-sum-of-two-arrays/
码字不易,如果觉得内容有帮助,欢迎留言or点赞!