文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 回溯
    • 2.2 狀態(tài)壓縮DP

1. 題目

給你兩個(gè)整數(shù)數(shù)組 nums1 和 nums2 ，它們長度都為 n 。

兩個(gè)數(shù)組的 異或值之和 為 (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]) （下標(biāo)從 0 開始）。

比方說，[1,2,3] 和 [3,2,1] 的 異或值之和 等于 (1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4 。
請(qǐng)你將 nums2 中的元素重新排列，使得 異或值之和 最小 。

請(qǐng)你返回重新排列之后的 異或值之和 。

示例 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

https://leetcode-cn.com/contest/biweekly-contest-53/problems/minimum-xor-sum-of-two-arrays/
https://leetcode-cn.com/problems/minimum-xor-sum-of-two-arrays/solution/zhuang-tai-ya-suo-dp-by-kobe24o-1h46/

2. 解題

類似題目： LeetCode 1178. 猜字謎（狀態(tài)壓縮+枚舉二進(jìn)制子集+哈希）
第7次 全部通過🚀

139 / 3069，前 4.53%

416 / 12291，前 3.38%

2.1 回溯

• 比賽時(shí)，寫了個(gè)回溯，用 n = 14 測了下，會(huì)超時(shí)

class Solution {int ans = INT_MAX; public:int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();vector<bool> vis(n, false);sort(nums1.rbegin(), nums1.rend());sort(nums2.rbegin(), nums2.rend());dfs(nums1, nums2, vis, 0, 0);return ans;}void dfs(vector<int>& nums1, vector<int>& nums2, vector<bool>& vis, int idx, int XORsum){if(XORsum >= ans)return;if(idx == nums1.size()){if(XORsum < ans)ans = XORsum;return;}for(int i = 0; i < nums2.size(); ++i){if(vis[i]) continue;vis[i] = true;dfs(nums1, nums2, vis, idx+1, XORsum+(nums1[idx]^nums2[i]));vis[i] = false;}} };

2.2 狀態(tài)壓縮DP

• 用二進(jìn)制1表示 nums2 各個(gè)位置被占用的情況

class Solution { public:int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();vector<int> dp(1<<n, INT_MAX);for(int i = 0; i < n; ++i)dp[1<<i] = nums1[0]^nums2[i]; // 第一個(gè)數(shù)跟 nums2 結(jié)合的情況for(int i = 1; i < n; ++i){ // 剩余的 nums1 的數(shù)for(int state = (1<<n)-1; state > 0; --state){ // 遍歷所有狀態(tài)if(dp[state] == INT_MAX) continue; // 不存在的狀態(tài)，passif(count(state) == i) // 原狀態(tài)的 1 的個(gè)數(shù) 為 i 個(gè)，可以進(jìn)行狀態(tài)轉(zhuǎn)移{for(int j = 0; j < n; ++j){ // 遍歷所有的位，碰到 state 0 的位置可以放一個(gè) 1if(((state>>j)&1)==0)dp[state|(1<<j)] = min(dp[state|(1<<j)], dp[state]+(nums1[i]^nums2[j]));}}}}return dp.back();}int count(int x){ // 計(jì)算 二進(jìn)制 1 的 個(gè)數(shù)int s = 0;while(x){s++;x = x&(x-1);}return s;} };

40 ms 9.1 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1879. 两个数组最小的异或值之和（状态压缩DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。