题目形容

这是 LeetCode 上的 1879. 两个数组最小的异或值之和 ,难度为 艰难

Tag : 「状压 DP」、「动静布局」、「启发式搜寻」

给你两个整数数组 nums1nums2,它们长度都为 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.length$
  • $n == nums2.length$
  • $1 <= n <= 14$
  • $0 <= nums1[i], nums2[i] <= 10^7$

状压 DP

这是一道「状压 DP」模板题。

为了不便,咱们令下标从 $1$ 开始。

定义 $f[i][s]$ 为思考前 $i$ 个元素,且对 nums2 的应用状况为 $s$ 时的最小异或值。其中 $s$ 是一个长度为 $n$ 的二进制数:若 $s$ 中的第 $k$ 位为 $1$,阐明 nums2[k] 已被应用;若 $s$ 中的第 $k$ 位为 $0$,阐明 nums2[k] 未被应用。

起始时,只有 $f[0][0] = 0$,其余均为无穷大 INF。$f[0][0]$ 含意为在不思考任何数,对 nums2 没有任何占用状况时,最小异或值为 $0$。最终 $f[n][2^n - 1]$ 即为答案。

不失一般性思考 $f[i][s]$ 该如何转移,能够以 nums1[i] 是与哪个 nums2[j] 进行配对作为切入点:

  • 因为总共思考了前 $i$ 个成员,因而 $s$ 中 $1$ 的数量必然为 $i$,否则 $f[i][s]$ 就不是一个非法状态,跳过转移
  • 枚举 nums1[i] 是与哪一个 nums2[j] 进行配对的,且枚举的 $j$ 需满足在 $s$ 中的第 $j$ 位值为 $1$,若满足则有

$$f[i][s] = \min(f[i][s], f[i - 1][prev] + nums1[i] ⊕ nums2[j])$$

其中 prev 为将 $s$ 中的第 $j$ 位进行置零后的二进制数,即 prev = s ^ (1 << j),符号 ⊕ 代表异或操作。

Java 代码:

class Solution {    public int minimumXORSum(int[] nums1, int[] nums2) {        int n = nums1.length, mask = 1 << n, INF = 0x3f3f3f3f;        int[][] f = new int[n + 10][mask];        for (int i = 0; i <= n; i++) Arrays.fill(f[i], INF);        f[0][0] = 0;        for (int i = 1; i <= n; i++) {            for (int s = 0; s < mask; s++) {                if (getCnt(s, n) != i) continue;                for (int j = 1; j <= n; j++) {                    if (((s >> (j - 1)) & 1) == 0) continue;                    f[i][s] = Math.min(f[i][s], f[i - 1][s ^ (1 << (j - 1))] + (nums1[i - 1] ^ nums2[j - 1]));                }            }        }        return f[n][mask - 1];    }    int getCnt(int s, int n) {        int ans = 0;        for (int i = 0; i < n; i++) ans += (s >> i) & 1;        return ans;    }}

C++ 代码:

class Solution {public:    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {        int n = nums1.size(), mask = 1 << n, INF = 0x3f3f3f3f;        vector<vector<int>> f(n + 10, vector<int>(mask, INF));        f[0][0] = 0;        auto getCnt = [&](int s, int n) {            int ans = 0;            for (int i = 0; i < n; i++) ans += (s >> i) & 1;            return ans;        };        for (int i = 1; i <= n; i++) {            for (int s = 0; s < mask; s++) {                if (getCnt(s, n) != i) continue;                for (int j = 1; j <= n; j++) {                    if (((s >> (j - 1)) & 1) == 0) continue;                    f[i][s] = min(f[i][s], f[i - 1][s ^ (1 << (j - 1))] + (nums1[i - 1] ^ nums2[j - 1]));                }            }        }        return f[n][mask - 1];    }};

Python 代码:

class Solution:    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:        n, mask, INF = len(nums1), 1 << len(nums1), 0x3f3f3f3f        f = [[INF] * mask for _ in range(n + 10)]        f[0][0] = 0        for i in range(1, n + 1):            for s in range(mask):                if sum([1 for i in range(n) if (s >> i) & 1]) != i:                    continue                for j in range(1, n + 1):                    if ((s >> (j - 1)) & 1) == 0:                        continue                    f[i][s] = min(f[i][s], f[i - 1][s ^ (1 << (j - 1))] + (nums1[i - 1] ^ nums2[j - 1]))        return f[n][mask - 1]

TypeScript 代码:

function minimumXORSum(nums1: number[], nums2: number[]): number {    const n = nums1.length, mask = 1 << n, INF = 0x3f3f3f3f;    const f: number[][] = new Array(n + 10).fill([]).map(() => new Array(mask).fill(INF));    f[0][0] = 0;    const getCnt = (s: number, n: number): number => {        let ans = 0;        for (let i = 0; i < n; i++) ans += (s >> i) & 1;        return ans;    };    for (let i = 1; i <= n; i++) {        for (let s = 0; s < mask; s++) {            if (getCnt(s, n) !== i) continue;            for (let j = 1; j <= n; j++) {                if (((s >> (j - 1)) & 1) === 0) continue;                f[i][s] = Math.min(f[i][s], f[i - 1][s ^ (1 << (j - 1))] + (nums1[i - 1] ^ nums2[j - 1]));            }        }    }    return f[n][mask - 1];};
  • 工夫复杂度:$O(n^2 \times 2^n)$
  • 空间复杂度:$O(n \times 2^n)$

模拟退火

事实上,这道题还能应用「模拟退火」进行求解。

因为咱们能够有限次对 nums2 进行打乱调换,先来思考如何掂量一个 nums2 排列的“好坏”。

一个简略的形式:固定计算 (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]) 作为掂量以后 nums2 的得分,得分越小,以后的 nums2 排列越好。

迭代开始前先对 nums2 进行一次随机打乱,随后每个回合随机抉择 nums2 的两个成员进行调换,并比拟调换前后的得分状况,若调换后变好,那么保留该调换操作;若变差,则以肯定概率进行重置(从新换回来)。

反复迭代屡次,应用一个全局变量 ans 保留下最小异或值之和。

即「模拟退火」的单次迭代根本流程:

  1. 随机抉择两个下标,计算「替换下标元素前对应序列的得分」&「替换下标元素后对应序列的得分」
  2. 如果温度降落(替换后的序列更优),进入下一次迭代
  3. 如果温度回升(替换前的序列更优),以「肯定的概率」复原现场(再替换回来)
对于一个可能使用模拟退火求解的问题,最外围的是如何实现 calc 办法(即如何定义一个具体计划的得分),其余均为模板内容。

Java 代码(2023/08/23 可过):

class Solution {    int N = 400;    double hi = 1e5, lo = 1e-5, fa = 0.90;    Random random = new Random(20230823);    void swap(int[] n, int a, int b) {        int c = n[a];        n[a] = n[b];        n[b] = c;    }    int calc() {        int res = 0;        for (int i = 0; i < n; i++) res += n1[i] ^ n2[i];        ans = Math.min(ans, res);        return res;    }    void shuffle(int[] nums) {        for (int i = n; i > 0; i--) swap(nums, random.nextInt(i), i - 1);    }    void sa() {        shuffle(n2);        for (double t = hi; t > lo; t *= fa) {            int a = random.nextInt(n), b = random.nextInt(n);            int prev = calc();            swap(n2, a, b);            int cur = calc();             int diff = cur - prev;             if (Math.log(diff / t) >= random.nextDouble()) swap(n2, a, b);        }    }    int[] n1, n2;    int n;    int ans = Integer.MAX_VALUE;    public int minimumXORSum(int[] nums1, int[] nums2) {        n1 = nums1; n2 = nums2;        n = n1.length;        while (N-- > 0) sa();        return ans;    }}
  • 工夫复杂度:启发式搜寻不探讨时空复杂度
  • 空间复杂度:启发式搜寻不探讨时空复杂度

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.1879 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。

在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地