【月度刷题计划同款】常规状压 DP & 启发式搜索

## 题目描述 这是 LeetCode 上的 **[1879. 两个数组最小的异或值之和](https://leetcode.cn/problems/minimum-xor-sum-of-two-arrays/solutions/2402125/gong-shui-san-xie-yi-ti-shuang-jie-zhuan-iusv/)** ，难度为 **困难**。 Tag : 「状压 DP」、「动态规划」、「启发式搜索」 给你两个整数数组 `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.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 代码： ```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++ 代码： ```C++ class Solution { public: int minimumXORSum(vector& nums1, vector& nums2) { int n = nums1.size(), mask = 1 << n, INF = 0x3f3f3f3f; vector> f(n + 10, vector(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 代码： ```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 代码： ```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 可过）： ```Java 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 原题链接和其他优选题解。 更多更全更热门的「笔试/面试」相关资料可访问排版精美的 [合集新基地](https://www.acoier.com/archives/) 🎉🎉
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,454评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,553评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 157,921评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,648评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,770评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,950评论 1赞 291
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,090评论 3赞 410
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,817评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,275评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,592评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,724评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,409评论 4赞 333
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,052评论 3赞 316
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,815评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,043评论 1赞 266
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,503评论 2赞 361
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,627评论 2赞 350

推荐阅读更多精彩内容