企业官网建设流程全解析

刷题刷到LeetCode 3314的时候，我第一反应是“构造最小位运算数组”这名字有点唬人。等把题读明白以后发现，它其实是一个标准的“给你一堆异或方程，让你反推原始数组”的构造题。而且题目还专门标了个“I”，言下之意就是数据范围给得很宽松，暴力枚举也能过。这期就把我最先想到、也最直接的暴力解法完整拆开讲一遍，包括递推公式怎么来的、枚举范围怎么定、哪些边界坑必须躲开。

1. 先读懂题：这个“构造”到底在构造什么

1.1 从异或方程组的角度理解题目

题目要求我们构造一个长度为n的数组arr，使得对于每个下标i，都有：

arr[i-1] XOR arr[i] XOR arr[i+1] = p[i]

这里有个细节很容易忽略：当i=0时，arr[-1]视为0；当i=n-1时，arr[n]视为0。也就是说，首尾两个位置其实只涉及两个数的异或。例如i=0时条件化简为arr[0] XOR arr[1] = p[0]，i=n-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[i+1] = p[i]

如果已经知道了arr[i-1]和arr[i]，那么arr[i+1]可以直接解出来：

arr[i+1] = 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]; // 从i=1到i=n-2，利用arr[i+1] = 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 边界情况一：n==1的时候最容易踩坑

很多第一次写这道题的人，容易忽略n==1的情况。这时候根本没有arr[1]这个位置，如果代码里直接写arr[1] = p[0] ^ arr[0]，立刻就会数组越界。

但n==1的情况其实非常简单。代入原始方程：

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 边界情况二：n==2时为什么可以无解

n==2时，方程组是：

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] = 0，arr[1] = 1，验证arr[0] ^ arr[1] = 1，和p[1]相等，返回[0, 1]。这个结果也是字典序最小的，因为arr[0]取0已经最小了。

3.4 位运算的细节：为什么可以直接用异或解未知数

这个解法里反复用到一个操作：已知p[i]、arr[i-1]、arr[i]求arr[i+1]。公式是arr[i+1] = 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开始，是因为i=0的方程已经被我们用来求arr[1]了。i最大到n-2，是因为当i=n-1时，原方程里需要arr[n]，也就是越界位置，它被固定为0，所以不能直接套用递推公式，而要放到最后单独验证。

这个循环边界是整段代码里最需要仔细检查的地方。你可以自己拿一个小例子推一遍，比如n=3时，循环只执行一次，i=1，求出arr[2]，然后验证i=2的方程，刚好覆盖全部三个方程。

4. 实测与分析：这题为什么值得用暴力解

4.1 时间复杂度与空间复杂度

暴力解的时间复杂度由两部分组成：枚举arr[0]的次数乘上每次递推的长度。设枚举上界为E，数组长度为n，则总时间复杂度为O(E * n)。E通常取2^15左右，n在I版本里很小，所以整体开销非常低。

空间复杂度方面，我们额外开了一个长度为n的数组arr，所以是O(n)。除此之外没有使用额外数据结构，是标准的线性空间。

如果n = 100，E = 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] = 0：

• arr[1] = p[0] ^ arr[0] = 1 ^ 0 = 1
• i=1时，arr[2] = p[1] ^ arr[0] ^ arr[1] = 2 ^ 0 ^ 1 = 3
• 验证最后一条：arr[1] ^ arr[2] = 1 ^ 3 = 2，但p[2] = 3，不相等，失败。

枚举arr[0] = 1：

• arr[1] = 1 ^ 1 = 0
• arr[2] = 2 ^ 1 ^ 0 = 3
• 验证：arr[1] ^ arr[2] = 0 ^ 3 = 3，和p[2]相等，成功。

所以返回[1, 0, 3]。我们代回原方程验证一下：

• i=0：arr[-1] ^ arr[0] ^ arr[1] = 0 ^ 1 ^ 0 = 1 = p[0]
• i=1：arr[0] ^ arr[1] ^ arr[2] = 1 ^ 0 ^ 3 = 2 = p[1]
• i=2：arr[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 常见问题速查表

我在写这段代码的时候，第一次提交并没有直接通过，主要是栽在细节上。下面这张表是典型的报错场景和处理方式，基本覆盖了新手会踩的坑。

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[i+1] = p[i] ^ arr[i-1] ^ arr[i]

把arr[0]记为x，那么arr[1] = p[0] ^ x，arr[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版本练手是很舒服的，既能感受异或方程的魅力，又能建立起“枚举 + 递推 + 验证”的解题框架，这套框架后面会反复用到。