刷题刷到LeetCode 3314的时候我第一反应是“构造最小位运算数组”这名字有点唬人。等把题读明白以后发现它其实是一个标准的“给你一堆异或方程让你反推原始数组”的构造题。而且题目还专门标了个“I”言下之意就是数据范围给得很宽松暴力枚举也能过。这期就把我最先想到、也最直接的暴力解法完整拆开讲一遍包括递推公式怎么来的、枚举范围怎么定、哪些边界坑必须躲开。1. 先读懂题这个“构造”到底在构造什么1.1 从异或方程组的角度理解题目题目要求我们构造一个长度为n的数组arr使得对于每个下标i都有arr[i-1] XOR arr[i] XOR arr[i1] p[i]这里有个细节很容易忽略当i0时arr[-1]视为0当in-1时arr[n]视为0。也就是说首尾两个位置其实只涉及两个数的异或。例如i0时条件化简为arr[0] XOR arr[1] p[0]in-1时条件化简为arr[n-2] XOR arr[n-1] p[n-1]。如果你把p数组看成是已知的“结果”arr数组就是一堆未知数那这道题本质上就是解一个含有n个未知数、n个方程的异或方程组。异或运算有一个特别好的性质a XOR b c时已知任意两个量都可以求出第三个量即a b XOR c。这个性质是整道题一切解法的基石。1.2 为什么“I版本”允许暴力题目名称里的“I”通常意味着这是系列题目的简单版本。LeetCode的套路是简单版本数据范围给得很小让新手也能用最朴素的方法通过后面的“II”才会加大数据范围逼你想更优解法。具体到3314这道题题面里p数组的长度n不大p[i]的取值范围也很有限所以就算我们枚举一下arr[0]的所有可能取值再顺着方程组一个个往后推总计算量也在可控范围内。这就是暴力解存在的合理性不是所有题都需要一开始就上高端解法先保证做对、再考虑做快是刷题落地时最实际的策略。2. 暴力解的核心一维递推与枚举起点2.1 核心公式已知前两个数后面就能一路推出来我们回顾一下方程arr[i-1] XOR arr[i] XOR arr[i1] p[i]如果已经知道了arr[i-1]和arr[i]那么arr[i1]可以直接解出来arr[i1] p[i] XOR arr[i-1] XOR arr[i]这个式子非常关键。它说明只要确定了arr[0]和arr[1]后面的arr[2]、arr[3]一直到arr[n-1]都能逐个递推出来不存在任何不确定的地方。换句话说整个数组arr的自由度其实很小真正需要“猜”的只有前两个数。但仔细看第一条方程arr[0] XOR arr[1] p[0]当arr[0]确定以后arr[1]并不是另外一个独立变量而是直接被p[0] XOR arr[0]锁定。所以真正需要枚举的未知数只有arr[0]一个。这就是暴力解能成立的根本原因一维递推把n个未知数压缩成了单个枚举变量。2.2 枚举arr[0]的范围怎么定暴力解自然要问arr[0]到底枚举到多大才算够题目里p[i]如果不超过某个上界那么arr[0]理论上也不会太大。这里可以用位运算的直观理解来解释异或运算不会产生进位所以结果的二进制位数不会超过参与运算的数里最大的那个位数。假如p[i]的最大值小于2^15也就是二进制不超过15位那么从低位往高位看只要arr[0]枚举的范围覆盖到2^15-1理论上已经足够找到可行解。我在题解里见过有人取1 15也有人直接枚举0到1023因为有的版本p[i]只有0到100左右枚举到1024绰绰有余。为了稳妥又不至于太慢我一般直接设枚举上界为1 15。反正I版本n很小就算n 100枚举32768次每次递推100步也才300多万次操作放在任何评测环境里都是秒过。你要是不放心甚至可以枚举到1 16依然不会超时。这个选择在实战里不需要纠结范围大一点不影响暴力解的通过率。2.3 字典序最小要从第一个元素开始贪心题目要求返回字典序最小的arr。字典序比较数组时首先比较arr[0]arr[0]相同再比较arr[1]以此类推。所以要让最终数组字典序最小最重要的就是arr[0]尽可能小。这给了我们一个很直接的贪心策略从小到大枚举arr[0]的取值。从0开始依次试1、2、3……一旦某个arr[0]能够推出一组满足所有方程的arr就直接返回这组结果。因为arr[0]已经是能取到的最小值所以这个解必然是字典序最小的解。不要担心后面arr[1]、arr[2]会不会不够小字典序的比较顺序决定了arr[0]的优先级最高arr[0]更小就意味着整个数组字典序更小。后面的元素再大也无法反过来影响arr[0]的优先级。3. 代码落地边界处理与细节陷阱3.1 先看一份能跑的Java核心代码我把核心逻辑写成下面这段Java代码重点看递推和边界判断public int[] solve(int[] p) { int n p.length; // 从小到大枚举arr[0]保证字典序最小 for (int first 0; first (1 15); first) { int[] arr new int[n]; arr[0] first; // n 1时p[0] arr[-1] ^ arr[0] ^ arr[1] 0 ^ arr[0] ^ 0 arr[0] if (n 1) { if (arr[0] p[0]) { return arr; } continue; } // 利用第一条方程arr[0] ^ arr[1] p[0]直接解出arr[1] arr[1] p[0] ^ arr[0]; // 从i1到in-2利用arr[i1] p[i] ^ arr[i-1] ^ arr[i]递推 for (int i 1; i n - 1; i) { arr[i 1] p[i] ^ arr[i - 1] ^ arr[i]; } // 最后验证 n-1 这条边界方程 // p[n-1] arr[n-2] ^ arr[n-1] ^ 0 arr[n-2] ^ arr[n-1] if ((arr[n - 2] ^ arr[n - 1]) p[n - 1]) { return arr; } } // 所有arr[0]都试过仍然无解返回空数组 return new int[0]; }如果你用的是Python逻辑完全一样代码还能更短def construct_min_bitwise_array(p): n len(p) for first in range(1 15): arr [0] * n arr[0] first if n 1: if arr[0] p[0]: return arr continue arr[1] p[0] ^ arr[0] for i in range(1, n - 1): arr[i 1] p[i] ^ arr[i - 1] ^ arr[i] if (arr[n - 2] ^ arr[n - 1]) p[n - 1]: return arr return []这两份代码的核心逻辑完全一致。LeetCode上的方法名可能要求是minBitwiseArray之类的你只需要把函数签名改成题目要求的样子内部实现可以直接用这份代码。3.2 边界情况一n1的时候最容易踩坑很多第一次写这道题的人容易忽略n1的情况。这时候根本没有arr[1]这个位置如果代码里直接写arr[1] p[0] ^ arr[0]立刻就会数组越界。但n1的情况其实非常简单。代入原始方程p[0] arr[-1] XOR arr[0] XOR arr[1] 0 XOR arr[0] XOR 0 arr[0]也就是说只有一个元素时arr[0]必须等于p[0]而且只能是这个值所以答案就是[p[0]]。比如p [5]答案就是[5]。如果题目要求字典序最小那也没有别的选项因为只有一个合法值。我在代码里专门用if (n 1)分支处理了这点宁可多写几行也不要在边界上翻车。3.3 边界情况二n2时为什么可以无解n2时方程组是arr[0] XOR arr[1] p[0] arr[0] XOR arr[1] p[1]因为第二条方程里arr[-1]和arr[2]都不存在都视为0所以p[0]和p[1]必须相等否则方程无解。暴力枚举会自动处理这种情况。比如p [1, 2]枚举arr[0] 0算出arr[1] 1 ^ 0 1最后验证arr[0] ^ arr[1] 1不等于p[1] 2失败。继续枚举arr[0] 1算出arr[1] 0验证arr[0] ^ arr[1] 1仍然不等于2失败。所有枚举都失败最终返回空数组符合预期。如果p [1, 1]枚举arr[0] 0arr[1] 1验证arr[0] ^ arr[1] 1和p[1]相等返回[0, 1]。这个结果也是字典序最小的因为arr[0]取0已经最小了。3.4 位运算的细节为什么可以直接用异或解未知数这个解法里反复用到一个操作已知p[i]、arr[i-1]、arr[i]求arr[i1]。公式是arr[i1] p[i] XOR arr[i-1] XOR arr[i]。很多刚接触位运算的朋友会迟疑异或又不是加减法怎么能移项呢这里可以简单证明一下。假设原方程是a XOR b XOR c d我们对等式两边同时异或a和b得到a XOR b XOR c XOR a XOR b d XOR a XOR b左边利用a XOR a 0、b XOR b 0以及异或的结合律可以消成c。所以c d XOR a XOR b。这种“两边同时异或同一个数等式仍然成立”的性质和“等式两边同时加减同一个数”是一样的道理。理解了这个点整个递推过程就没有任何神秘感了。3.5 循环里的i到底从哪里开始到哪里结束再看递推循环for (int i 1; i n - 1; i) { arr[i 1] p[i] ^ arr[i - 1] ^ arr[i]; }i从1开始是因为i0的方程已经被我们用来求arr[1]了。i最大到n-2是因为当in-1时原方程里需要arr[n]也就是越界位置它被固定为0所以不能直接套用递推公式而要放到最后单独验证。这个循环边界是整段代码里最需要仔细检查的地方。你可以自己拿一个小例子推一遍比如n3时循环只执行一次i1求出arr[2]然后验证i2的方程刚好覆盖全部三个方程。4. 实测与分析这题为什么值得用暴力解4.1 时间复杂度与空间复杂度暴力解的时间复杂度由两部分组成枚举arr[0]的次数乘上每次递推的长度。设枚举上界为E数组长度为n则总时间复杂度为O(E * n)。E通常取2^15左右n在I版本里很小所以整体开销非常低。空间复杂度方面我们额外开了一个长度为n的数组arr所以是O(n)。除此之外没有使用额外数据结构是标准的线性空间。如果n 100E 32768那最多大概3276800次循环操作。现代CPU处理这个量级几乎是瞬间完成提交到LeetCode上运行时间通常在几毫秒到十几毫秒之间非常轻松。4.2 为什么E取1 15而不是其他值这背后的逻辑不复杂。题面里p[i]如果被限制在0到100左右那p[i]的二进制最多用到7位理论上枚举到128就应该够了。但为什么我建议直接取1 15原因有两个。第一异或运算虽然不会让二进制位数变长但在递推过程中中间值arr[i]可能因为异或组合出现比p[i]更大的数字。如果枚举范围取小了有可能错过本来存在的解。比如p[i]最大值是100但arr[0]取128时arr[1] p[0] ^ 128可能超过255而这种组合有可能在后续的异或中恰好消回去。为了不让自己纠结“枚举范围到底够不够”直接取一个比较大的上界更省心。第二1 15这个值不是随便拍的。很多位运算题里int型正数最多到2^31-1但实际构造类题目中涉及的数字往往控制在2^15或2^16以内。取1 15既保证了覆盖范围足够广又不会让暴力解变成超时解。如果你想更稳妥取1 16也没问题I版本的n很小多一倍的枚举量微不足道。4.3 用样例手推一遍p [1, 2, 3]光说理论容易飘我拿一个具体的例子推一遍。假设p [1, 2, 3]我们用暴力枚举来走一遍过程。枚举arr[0] 0arr[1] p[0] ^ arr[0] 1 ^ 0 1i1时arr[2] p[1] ^ arr[0] ^ arr[1] 2 ^ 0 ^ 1 3验证最后一条arr[1] ^ arr[2] 1 ^ 3 2但p[2] 3不相等失败。枚举arr[0] 1arr[1] 1 ^ 1 0arr[2] 2 ^ 1 ^ 0 3验证arr[1] ^ arr[2] 0 ^ 3 3和p[2]相等成功。所以返回[1, 0, 3]。我们代回原方程验证一下i0arr[-1] ^ arr[0] ^ arr[1] 0 ^ 1 ^ 0 1 p[0]i1arr[0] ^ arr[1] ^ arr[2] 1 ^ 0 ^ 3 2 p[1]i2arr[1] ^ arr[2] ^ arr[3] 0 ^ 3 ^ 0 3 p[2]完全正确。这个例子也说明不是arr[0]越小越好arr[0] 0时虽然更小但无法满足全部约束第二个候选值arr[0] 1就通过了所以它就是字典序最小的解。4.4 暴力和“聪明解法”的边界在哪里暴力解虽然在这道I版本里很香但它有一个明显的弱点枚举上界E是和数据范围强相关的。如果p[i]可以大到2^30那枚举1 30是完全不可行的这时候就必须换思路。这就是为什么LeetCode接着出了II版本。II版本大概率是把n和p[i]的值域同时放大逼你用更精细的位运算构造法。但做II之前先把I版本的暴力解吃透理解递推的本质再去看位构造会顺畅得多。很多人一上来就看II的最优解代码背下来了但对为什么这样构造毫无感觉换个题型又不会了。我个人的建议是先暴力拿下一题再逐步优化这个过程本身比AC本身更有价值。5. 常见问题与从I到II的进阶方向5.1 常见问题速查表我在写这段代码的时候第一次提交并没有直接通过主要是栽在细节上。下面这张表是典型的报错场景和处理方式基本覆盖了新手会踩的坑。问题表现可能原因解决方法数组越界没有处理n1的情况直接访问arr[1]单独判断n1直接返回[p[0]]答案错误最后一条边界方程判断条件写错确认arr[n]0所以条件是arr[n-2] ^ arr[n-1] p[n-1]返回空数组但实际有解枚举范围太小错过了可行的arr[0]把枚举上界调大到1 15或1 16超时I版本理论上不会但如果你枚举到1 31就会根据p[i]值域合理设置枚举上界字典序不是最小从大到小枚举arr[0]或者枚举顺序乱了必须从0开始递增枚举arr[0]第一个可行解就是答案5.2 为什么确认最后一个方程用“验证”而非“递推”有朋友可能会问既然递推公式这么好用为什么最后一条不也直接用arr[n] p[n-1] ^ arr[n-2] ^ arr[n-1]来求arr[n]问题在于arr[n]是不存在的它被题目固定为0。所以最后一条方程已经不是一个常规递推方程而是一个约束条件用来检查前面推出来的arr[n-2]和arr[n-1]是否满足这个边界约束。满足就说明整组解成立不满足就说明当前枚举的arr[0]不可行需要继续枚举。这里也体现了构造题和模拟题的一个区别模拟题往往每一步都是确定的构造题则要在某些位置停下来做合法性校验。写代码时一定要分清楚哪些位置是“算出下一个数”哪些位置是“检查当前数是否合法”。5.3 从暴力解到II版本的位构造思路预告如果你做完I版本还想挑战II可以先思考一个问题当n和p[i]都变大时枚举arr[0]的方法为什么失效根源在于E和值域挂钩。那有没有办法不用枚举直接确定arr[0]观察一下递推公式arr[i1] p[i] ^ arr[i-1] ^ arr[i]把arr[0]记为x那么arr[1] p[0] ^ xarr[2] p[1] ^ x ^ (p[0] ^ x)。注意这里面的x其实在异或中可以互相抵消所以arr[2]可能根本不含x或者只含x的某几位。继续往后推你会发现arr数组中关于x的依赖关系呈现出某种规律。II版本的常见做法就是把x的每一位单独拿出来分析把数组划分成若干段或者直接寻找x必须满足的位级约束关系。这样就不再需要枚举x而是直接通过位运算把x构造出来。这个过程很有意思等你有空可以继续研究。5.4 我自己的刷题心得构造题先想“未知量能不能减少”做构造题最忌讳一上来就盯着整个数组发呆。正确的打开方式是问自己如果我已经知道了数组的一部分剩余部分能不能被唯一确定这道题的答案是可以只要知道arr[0]整个数组就被所有方程唯一锁定了。这个观察直接决定了暴力枚举是有效的。类似的构造题还有很多比如“给你一个数组经过某些操作后的结果让你反推原数组”很多都可以通过枚举第一个元素或者最后一个元素把问题变成规则的递推或模拟。哪怕不是最优解至少能快速建立对题目的感性认识。先暴力解出来再分析哪些地方是性能瓶颈最后想办法去掉瓶颈这是我刷构造题最常用的三步走。最后说一句实际体验暴力解这道题时代码写起来很快调试也不痛苦因为每一步都能拿小样例验证。不像某些DP题写半天还不知道状态转移对不对。如果你是刚接触位运算或者构造题用3314的I版本练手是很舒服的既能感受异或方程的魅力又能建立起“枚举 递推 验证”的解题框架这套框架后面会反复用到。