免费 网站 如何做,重庆龙华网站建设公司,安丘网站建设制作,深圳建网站seo题目描述 这是 LeetCode 上的 「1879. 两个数组最小的异或值之和」 #xff0c;难度为 「困难」。 Tag : 「状压 DP」、「动态规划」、「启发式搜索」 给你两个整数数组 nums1 和 nums2#xff0c;它们长度都为 n。 两个数组的 异或值之和 为 (nums1[0] XOR nums2[0]) (nums… 题目描述 这是 LeetCode 上的 「1879. 两个数组最小的异或值之和」 难度为 「困难」。 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 。 提示 状压 DP 这是一道「状压 DP」模板题。 为了方便我们令下标从 开始。 「定义 为考虑前 个元素且对 nums2 的使用情况为 时的最小异或值」。其中 是一个长度为 的二进制数若 中的第 位为 说明 nums2[k] 已被使用若 中的第 位为 说明 nums2[k] 未被使用。 起始时只有 其余均为无穷大 INF。 含义为在不考虑任何数对 nums2 没有任何占用情况时最小异或值为 。最终 即为答案。 不失一般性考虑 该如何转移可以以 nums1[i] 是与哪个 nums2[j] 进行配对作为切入点 由于总共考虑了前 个成员因此 中 的数量必然为 否则 就不是一个合法状态跳过转移 枚举 nums1[i] 是与哪一个 nums2[j] 进行配对的且枚举的 需满足在 中的第 位值为 若满足则有 其中 prev 为将 中的第 位进行置零后的二进制数即 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(vectorint nums1, vectorint nums2) { int n nums1.size(), mask 1 n, INF 0x3f3f3f3f; vectorvectorint f(n 10, vectorint(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];}; 时间复杂度 空间复杂度 模拟退火 事实上这道题还能使用「模拟退火」进行求解。 由于我们可以无限次对 nums2 进行打乱互换先来思考如何衡量一个 nums2 排列的“好坏”。 一个简单的方式固定计算 (nums1[0] XOR nums2[0]) (nums1[1] XOR nums2[1]) ... (nums1[n - 1] XOR nums2[n - 1]) 作为衡量当前 nums2 的得分得分越小当前的 nums2 排列越好。 迭代开始前先对 nums2 进行一次随机打乱随后每个回合随机选择 nums2 的两个成员进行互换并比较互换前后的得分情况若互换后变好那么保留该互换操作若变差则以一定概率进行重置重新换回来。 重复迭代多次使用一个全局变量 ans 保存下最小异或值之和。 即「模拟退火」的单次迭代基本流程 随机选择两个下标计算「交换下标元素前对应序列的得分」「交换下标元素后对应序列的得分」 如果温度下降交换后的序列更优进入下一次迭代 如果温度上升交换前的序列更优以「一定的概率」恢复现场再交换回来 ❝ 对于一个能够运用模拟退火求解的问题最核心的是如何实现 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 原题链接和其他优选题解。 更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地
