企业官网建设流程全解析

1. 先把题面翻译成人话：构造最小位运算数组到底在还原什么

1.1 位运算数组不是新概念，就是相邻按位或的结果

如果你和我一样，点开 Leetcode 3314 构造最小位运算数组 I 之前以为它是个简单枚举题，那读完题面大概会愣一下：“最小”两个字才是全题的重心。位运算题最怕的不是不会用& | ^，而是不知道在哪里用贪心、在哪里用暴力。这篇文章就把构造最小位运算数组 I 的完整思路拆开，从位独立讲到连续段填充，再给出一版可以直接提交的 Python 代码。适合刚刷完数组基础题、准备进阶位运算的读者；如果你已经被 994 腐烂的橘子这类 BFS 题虐过，换个脑子来做做构造题也挺好。

先明确题目里的“位运算数组”到底是什么意思。设原数组为a，长度为n。位运算数组b是这样得到的：对每个下标i，都有：

b[i] = a[i] | a[i + 1]

也就是说，b是相邻两个元素做按位或之后得到的结果数组，它的长度是n - 1。题目给你b，让你把a还原出来。这本质上是一道“给结果、求原因”的构造题。

举个具体例子。如果n = 3，b = [1, 3]，那么可行解并不唯一：

• a = [0, 1, 3]：0 | 1 = 1，1 | 3 = 3，成立。
• a = [1, 0, 3]：1 | 0 = 1，0 | 3 = 3，也成立。
• a = [1, 1, 2]：1 | 1 = 1，1 | 2 = 3，还是成立。

如果只要求“找一组可行解”，随便填都能过。但题目偏偏要“最小”，于是问题一下子从枚举变成了构造。

1.2 “最小”意味着字典序最小，不是数值最小

数组比大小，莱科德这类题目默认按字典序比。所谓字典序，就是从头开始比较第一个不同的元素：哪个数更小，哪个数组就更小。如果第一个元素相同，再比第二个，依次类推。

所以上面三个候选里，[0, 1, 3]是最小的，因为它的第一个元素是0，而另外两个第一个元素都是1。

这给我们的启发很直接：构造的时候，必须优先让a[0]尽量小，然后让a[1]尽量小，再让a[2]尽量小……也就是一个标准的贪心过程。

但贪心不能瞎贪。你让a[0]变成0，很可能把压力全部甩给a[1]；如果a[1]被逼成了一个大数，后面反而可能无解。所以必须先理解位运算的底层性质，再决定每一步怎么填。

2. 核心原理：为什么每一位可以单独决定

2.1 位独立：把一个大问题拆成 30 个小问题

位运算最容易被忽略、但最好用的性质是：不同二进制位之间完全独立。

a[i] | a[i + 1]的第k位，只由a[i]和a[i + 1]的第k位决定。高位是1还是0，完全不影响低位的结果。所以我们可以把b拆成一层一层的二进制位，每一层单独构造一个“只含 0/1 的数组”，最后再把所有层的构造结果按位或回去。

举个例子。如果b = [2, 3]，二进制分别是10和11。那么第0层（最低位）的bits是[0, 1]，第1层的bits是[1, 1]。两层互不干扰，分别把a的对应位填好，再合并，就是最终答案。

这个拆位思想在很多数组相关题目里都适用，尤其是当题目里出现“按位与”“按位或”“按位异或”这种字眼时，先问自己一句：能不能把每个二进制位单独拎出来看？多半是能的。

2.2 0 是硬约束，1 只是“至少有一个 1”

在某一层里，设bit[i]是b[i]的第k位，a[i]和a[i + 1]的第k位分别记为x[i]、x[i + 1]。那么约束只有两种情况：

• 如果bit[i] == 0，因为按位或的结果是0，说明x[i]和x[i + 1]必须都是 0。这是硬性条件，没有任何商量余地。
• 如果bit[i] == 1，说明x[i]和x[i + 1]至少有一个是1，唯一禁止的情况是“两个都是 0”。

所以整道题可以简化成一句话：有一堆位置因为相邻的bit[i] == 0被强制填成 0，剩下的位置要尽量填 0，但不能出现“相邻两个都是 0”这种非法状态。

这比直接处理整个整数简单太多了。因为每一层只有 0 和 1 两种取值，所有复杂决策都被压缩成“这里能不能填 0”。

2.3 连续 1 段里的填充规则

现在只看某一层。假设这一层的bits是：

bits = [1, 1, 0, 1]

bits[2] == 0会强制x[2] = 0、x[3] = 0。于是整个数组被这个硬性 0 切成了两段：

• 左边一段：bits[0]和bits[1]都是 1，对应位置x[0]、x[1]、x[2]。
• 右边一段：bits[3]是 1，对应位置x[3]、x[4]。

在每一段内部，规则只剩下一个：相邻两个x不能同时为 0。这时候贪心就非常简单了：

• 第一个位置先尝试填 0，因为越靠前越小。
• 如果前一个位置已经是 0，那当前位置必须填 1，否则会出现“00”。
• 如果前一个位置是 1，那当前位置优先填 0。

比如bits = [1, 1, 1]时，a的对应位长度是 4。按照上面的规则，填出来是：

x = [0, 1, 0, 1]

验证一下：0 | 1 = 1，1 | 0 = 1，0 | 1 = 1，完全成立。而且它比[1, 0, 1, 0]小，因为第一个位置是 0。

再看一个带硬性 0 的例子。bits = [1, 0, 1]：

• bits[1] == 0直接让x[1] = 0、x[2] = 0。
• 左侧bits[0] == 1，但x[1]已经是 0，所以x[0]只能填 1。
• 右侧bits[2] == 1，但x[2]已经是 0，所以x[3]只能填 1。

最终结果是：

x = [1, 0, 0, 1]

这个例子特别能说明问题：不要因为“优先填 0”就无脑给首位置填 0，还要看后面有没有被硬性 0 卡住。

3. 代码落地：按位跑连续段，和你想的暴力回溯不一样

3.1 整体流程：先拆位，后填段，最后统一验证

实际写代码的时候，没必要在每一位上都做复杂的可行性判断。我用的流程是固定的四步：

1. 枚举二进制位k，把b拆成这一层的bits。
2. 遍历bits，把所有bit[i] == 0的位置标成“强制填 0”：也就是x[i]和x[i + 1]都必须为 0。
3. 找bits里所有连续的“1 段”，对每一段单独做贪心填充。
4. 所有位都填完后，统一验证一遍(a[i] | a[i + 1]) == b[i]，如果不成立就返回空数组。

最后一步非常重要，因为按位独立构造时，某一层局部可行不代表整体一定可行。比如bits = [0, 1, 0]这一层，bits[0] == 0让x[0]、x[1]都是 0，bits[2] == 0让x[2]、x[3]都是 0，但中间的bits[1] == 1又要求x[1] | x[2] == 1，这显然是矛盾的。所以必须在最后做一次整体校验，把所有层叠加起来再看。

3.2 Python 实现

下面这版代码可以直接提交，核心逻辑都在_build_segment里。

from typing import List class Solution: def minBitwiseArray(self, b: List[int]) -> List[int]: n = len(b) + 1 ans = [0] * n # 按二进制位逐层处理，31 位足够覆盖常见的 int 范围 for k in range(31): bits = [(v >> k) & 1 for v in b] # fixed[i] == True 表示这一层里 a[i] 必须为 0 fixed = [False] * n for i, x in enumerate(bits): if x == 0: fixed[i] = True fixed[i + 1] = True i = 0 while i < n - 1: if bits[i] == 1: l = i while i < n - 1 and bits[i] == 1: i += 1 r = i - 1 length = r - l + 2 start_zero = fixed[l] end_zero = fixed[r + 1] seg = self._build_segment(length, start_zero, end_zero) for j in range(length): if seg[j]: ans[l + j] |= (1 << k) else: i += 1 # 整体校验，不能省 for i in range(n - 1): if (ans[i] | ans[i + 1]) != b[i]: return [] return ans def _build_segment(self, length: int, start_zero: bool, end_zero: bool) -> List[int]: seg = [0] * length for i in range(length): # 边界位置被硬性 0 卡住 if (i == 0 and start_zero) or (i == length - 1 and end_zero): seg[i] = 0 continue # 前一个位置已经是 0，当前位置必须补 1 if i > 0 and seg[i - 1] == 0: seg[i] = 1 continue # 如果右边是强制 0，且再往下填 0 会导致最后两个都是 0 if end_zero and i == length - 2: seg[i] = 1 continue # 其他情况优先填 0 seg[i] = 0 return seg

整个实现的核心其实只有三条填值规则：

• 被硬性 0 卡住的位置，只能填 0。
• 前一个是 0，当前位置为了不出现“00”，只能填 1。
• 当前位置是“强制 0 端点的前一个位置”时，如果填 0，最后的强制的 0 会和它相邻形成“00”，所以必须填 1。

3.3 复杂度与为什么这版可以直接交

时间复杂度是O(n * 31)，因为每一层都要遍历一遍b和ans。空间复杂度是O(n)，主要用来存bits、fixed和ans。

这个复杂度对 I 版本来说绰绰有余。就算n到10^5，31 层循环也不过是三百多万次操作，Python 完全跑得动。II 版本如果只是把n拉大、把数值范围拉高，这版代码的思路依然成立，不需要换算法。

很多人看到“位运算”三个字就想上 DFS、回溯，其实没有必要。这道题真正考的是能不能把位压到单层去理解，能不能在连续段里做贪心。暴力枚举当然也能过小数据，但那样收获不大。

4. 我实际提交时踩过的坑：全零数组、无解判定、位宽

4.1 坑一：无解时返回了半成品

我先说一个最容易犯的错：构造完所有二进制位之后，没有做整体校验，直接返回ans。

问题是，按位独立构造时，每一层看起来都“局部正确”，但合并起来可能无解。最典型的就是某一层出现了bits = [0, 1, 0]这种情况。bits[0] == 0强制a[0]、a[1]的这一位都是 0，bits[2] == 0强制a[2]、a[3]的这一位都是 0，中间的bits[1] == 1又要求a[1]和a[2]至少有一个 1。这根本不可能成立。

如果不做最后校验，ans里这一层全是 0，表面上也能返回一个数组，但放到(ans[i] | ans[i + 1]) == b[i]里一验就露馅。所以我在代码里专门加了一步：全部位填完后，再跑一遍原约束，一旦发现不相等，立刻返回空数组。

4.2 坑二：把首位贪心理解得太死

另一个坑是只记住了“优先填 0”，结果在连续 1 段里填错。

比如某一层的bits = [1, 1, 1]，正确的最小结果是[0, 1, 0, 1]。但有人会想：第一个位置优先填 0，第二个位置也优先填 0，结果变成[0, 0, ?]，直接违反约束。还有人会把第一个位置填成 1，得到[1, 0, 1, 0]，虽然可行，但不是最小。

正确的理解是：优先填 0 的前提是后面还能接得住。一旦前一个位置是 0，当前位置就必须填 1，否则就会出现两个连续的 0。这比“所有位置都尽量填 0”更准确。遇到右端点是强制 0 的情况，还要额外往前推一步，让倒数第二个位置填 1，否则末尾也会出现“00”。

4.3 坑三：位宽不够，最高位被吞掉

还有一次我图省事，只循环到range(30)，结果某个用例里b[i]的最高位是第 30 位，直接被我漏掉了。构造出来的ans在最后校验时全部对不上，排查半天才发现是位宽问题。

建议不要凭感觉写死一个位数，可以直接取所有b[i]的最大二进制位长度：

max_bit = max(b).bit_length() if b else 1 for k in range(max_bit): ...

这样既不会漏位，也不会多做无用的高位循环。如果题目里数值可能到2^31级别，那就用 31 位；如果按位与/异或题里可能出现负数，更要格外小心，Python 的负数和 C++ 的补码表示不太一样，刷题时最好先确认数据范围。

4.4 坑四：数组初始化带来的额外心理负担

这道题涉及的数组不多，但数组初始化的习惯还是值得说一下。ans = [0] * n和fixed = [False] * n都是一维数组，直接乘号初始化就好。有些朋友刚从二维数组、指针数组那边转过来，喜欢顺手写[[0] * n]，结果发现多了一层括号，后面索引经常错位。

其实构造题里的“累加位”操作很常见：先初始化成全 0，再根据每一层的贪心结果往对应位置用|= (1 << k)累加。不要试图直接算出一个完整整数，那样反而容易在位上出错。

5. 从 I 到 II：同一套思路如何迁移

5.1 I 和 II 的差异本质是数据规模

很多时候，LeetCode 的题目分成 I 和 II 两个版本，I 版本数据范围小，可以用更暴力的方法；II 版本数据范围大，必须上更优的做法。但构造最小位运算数组这题有点特别，核心思路本身已经是线性复杂度，所以 I 和 II 的差距不大。

真正需要注意的是：I 版本可能允许你直接对每个位置做一次小范围枚举，比如从 0 试到当前b里的最大值，再验证相邻或的结果。II 版本如果把n拉到10^5、把数值范围拉到2^31，暴力枚举就完全不可行了。这时候按位拆解 + 连续段贪心的优势就出来了。

从做题策略上讲，我的建议是：哪怕 I 版本能暴力过，也最好用位独立的方法写一遍。因为这样到了 II 版本你几乎不用改代码，只需要把位数上限调一调。

5.2 迁移到 AND 或 XOR 版本的镜像思路

如果你在周赛里碰到这道题的变体，发现题目里的位运算不是按位或，而是按位与或者按位异或，思路依然可以迁移，只是要调整“硬约束”的方向。

• 如果是按位与：bit[i] == 1变成硬约束，它强制a[i]和a[i + 1]的那一位都是 1；而bit[i] == 0只要求至少有一个 0。
• 如果是按位异或：bit[i] == 1表示两个位置这一位不同，bit[i] == 0表示两个位置这一位相同。这时候连续段的贪心规则会变成“交替填”，和 OR 版本完全相反。

但不管是 AND、OR 还是 XOR，底层的思考路径是一样的：先按位拆开，弄清楚每一位上什么情况是硬约束，什么情况只是“二选一”，然后用从左到右的贪心去填。最后再做一次整体校验，防止某一位在局部可行、合起来却矛盾的情况。

5.3 一点个人建议

最后分享一个我自己的习惯：遇到这种“构造最小数组”的题，我不会先去写代码，而是先在纸上把某一层bits的所有可能形态列出来。比如[1]填[0, 1]，[1, 1, 1]填[0, 1, 0, 1]，[1, 0, 1]填[1, 0, 0, 1]，[0, 1, 0]无解。把这些小样例搞清楚，代码里的每个 if 分支就都有依据了，而不是靠试错凑答案。

构造题的难点从来不是某个 API 不会用，而是“什么时候填 0、什么时候填 1”的决策没有想清楚。把位独立和连续段填充这两个点吃透，Leetcode 3314 构造最小位运算数组 I 对你来说就不再是简单题里的拦路虎，而是一个可以顺手秒掉的常规题。