大家好，这里是一起打 Leetcode 竞赛系列文章的第 5 篇。
本周有周赛和双周赛，本文是对上午的双周赛 Biweekly Contest 53 的简单讲解和评论。以下会包括每一题的简单讲解，代码，难度分析，以及一些个人对这题的看法等，希望大家喜欢！
注意 ： 题解并不一定都是最优解（代码以 pass 了 LeetCode 的 Oline Judge 为准），文章初衷是给读者们提供一定的想法和问题的解决方案。
前言 : 参加 Contest 的好处
- 每周抽点时间去练习和学习新的题目这对于个人的编程能力与问题解决能力都有很大的帮助。
- 在规定的时间内解决一定的题目，这和真实的OA (Online Assessment) 或者 Onsite 面试是一样的，可以把它当作一个很好的 Mock 练习机会。
- 当你有碰到做不出的题目的时候，你能知道自己的弱项在哪里，然后可以根据这进行加强和练习，比赛是一面给自己的镜子。
对本场比赛的一些看法
本场比赛难度相对比较正常，都是比较常规的题目，第三题稍微有点难度需要一点思考。
1876. 简单的暴力签到题1877. 一道贪心和双指针题目1878. 一道观察型的题目1879. 使用 bit 进行压缩的DP题目
1879 Minimum XOR Sum of Two Arrays
题意：
给你两个数组A 和 B，你可以对B的顺序进行任何的调整。现在你要最小化 (A[0] xor B[0]) + (A[1] xor B[1]) + . . . . . . +(A[n-1] xor B[n-1])
思路：
- 当看到 n < 14 的时候，第一个想法就是NP 暴力穷搜或者是使用Bit 进行压缩的DP
- 这题我们可以使用bit 进行状态压缩 （这里使用 DFS + Memo），我们的state表达的是当前数组 B 还有哪些数是可取的。如果当前的state是 1011，这就表示 B[0]，B[1]，B[3] 是可取的
- 我们遍历数组A的每个index，从0开始，A[0] 可以跟数组B的任何一个index进行匹配。假设 n = 4 以及state一开始是1111，那么B 可取的是 B[0]，B[1]，B[2]，B[3]。如果A[0] 和 B[0] 进行匹配，那么state就变成1110。如果A[0] 和B[1] 进行匹配，那么我们的state就变成了1101。然后我们把index 加1和把新的state递归下去。对于A[1]，他能跟剩余的B里的三个数字其中一个进行匹配，以此类推，当数字都匹配完时 return 0
- 如何 turn off 其中一个 bit ？ state = state ^ (1 << i)
- 如何check ith bit 是否是 1 ？ if ((state & (1 << i)) != 0)
代码：
classSolution {
intdp[][];
publicintminimumXORSum(int[] A, int[] B) {
dp=newint[A.length+1][(1<<B.length) +10];
for (inti=0; i<dp.length; i++) {
Arrays.fill(dp[i], -1);// -1 表示此状态还没打卡
}
intstate= (1<<A.length) -1;
// 如果n=3, 1<<n = 8, (1<<n)-1 的 二进制则是 111
returndfs(A, B, 0, state);
}
publicintdfs(intA[], intB[], intindex, intstate) {
if (index>=A.length) {//终止条件
return0;
}
if (dp[index][state] !=-1) returndp[index][state];//此状态已打卡
intres=Integer.MAX_VALUE;
for (inti=0; i<B.length; i++) {
if ((state& (1<<i)) !=0) {//检查当前第 ith bit是否是1,1 表示可以取当前B这个数字
//匹配 A[index] 和 B[i], 得到分数 A[index] ^ B[i]
// newstate = state^(1<<i)
res=Math.min(res, (A[index] ^B[i]) +dfs(A, B, index+1, state^ (1<<i)));
}
}
dp[index][state] =res;
returnres;
}
}
空间复杂度和时间复杂度：
- 时间复杂度：O(n^2 2^n)
- 空间复杂度：O(n 2^n)
