企业官网建设流程全解析

LeetCode 3315 这道题，说它是周赛里的“位运算质检员”一点不过分。题面很短，无非是给你一个 target 数组，让你反推另一个数组 ans，让相邻两个数的按位与恰好等于 target 里对应位置的值，同时还要求 ans 整体尽量小。看起来就是两行约束，可真正动手推的时候，你会发现位运算里“牵一发而动全身”的味道特别浓：某一位在中间断不掉，整个数组都得判死刑；某一根线怎么走，直接决定所有元素的二进制长什么样。

我第一次交的时候栽在无解判定上，后来把每一位单独拉出来当成一条 0/1 的线路来看，才算彻底想明白。这篇文章不打算只贴个代码，我想把从“看到题”到“推出那三行核心逻辑”的全过程写下来，包括为什么答案能写成target[i-1] | target[i]，为什么出现1, 0, 1这种模式就无解，以及怎么用一次位运算同时检查所有位。不管你是第一次接触这种构造题，还是想在周赛里稳定拿下 Q3/Q4，这篇文章应该都能给你一点实在的东西。

1. 题意拆解：两个数组之间的“相邻按位与”契约

1.1 题干到底在说什么

先统一一下题面。假设给定长度为 n 的数组target，需要你构造长度为 n + 1 的数组ans，使得对每一个下标i（从 0 到 n-1），都满足：

ans[i] & ans[i+1] == target[i]

换句话说，target不是普通的目标值，它记录的是ans中相邻两个元素之间按位与的结果。你要做的，是把这个“合同”反向还原出一整条数组来。这个设定和常见的“给一个前缀和让你还原原数组”其实很像，只不过把加法换成了按位与，约束从“全局线段”变成了“相邻单边”。

举个例子。target = [7, 4, 0]，长度为 3，那么ans的长度就是 4。你需要找四个非负整数，让：

• ans[0] & ans[1] = 7
• ans[1] & ans[2] = 4
• ans[2] & ans[3] = 0

如果随便交一个ans = [7, 7, 4, 0]，确实满足三个等式，但它是不是“尽量小”的？不一定。题目里的“最小”往往指按位或的值最小，或者字典序最小。这里我们的构造会让每个元素都处在“它不得不这么大的最小状态”，所以两个目标本质上同时达成。

1.2 “尽量小”到底小在哪

很多人一开始会以为，构造题嘛，能凑出一组满足等式的数组就行。但这类题一定藏着“最小化”的附加条件，否则答案会多到爆炸。比如上面那个例子，ans = [7, 7, 7, 0]同样满足约束，因为7 & 7 = 7、7 & 0 = 0，肉眼可见它比[7, 7, 4, 0]更大。

那“最小”怎么理解？最直观的口径是：把ans所有元素按位或起来，这个值要尽量小；或者直接按数组顺序比较，字典序最小。好消息是，对于这道题，我们推出的构造方法在每一位上都取了“不得不是 1 才设 1”的最小集合，所以两个口径同时满足。你可以把它想象成填格子：每个二进制位像一盏灯，只有被某个约束死死按在 1 的位置才亮，其他位置一律熄灭。

这样处理后，ans中每个元素都变成了“必要最小值”，不可能再往下压。后面所有推导，都会围绕这个“必要最小值”展开。

2. 破题关键：把数组拆成 32 根二进制线

2.1 为什么可以逐位独立看

先复习一个基本功：按位与是逐位运算的，a & b的第 k 位只取决于a和b的第 k 位，跟其他位毫无关系。这意味着我们可以把整个问题按二进制位拆开，想象成 32 根完全独立的“线”，每根线上传输 0 或 1。

把target[i]的第 k 位抽出来，得到一个长度为 n 的 0/1 序列，记作t[i]。再把ans[i]的第 k 位抽出来，得到一个长度为 n + 1 的 0/1 序列，记作a[i]。原来的等式就变成：

a[i] & a[i+1] == t[i]

这就是一根线上的全部约束。只要把这根线上的a构造出来，做完 32 次，再把每一位拼回整数，原题就解决了。这种“先拆位、再合并”的手法，是做位运算构造题的第一板斧。

很多同学看到&就头疼，是因为脑子里总把整个整数揉在一起想。一旦拆成线，约束就从“两个大数做运算”降级成“两个开关之间的关系”。一根线只有 0 和 1 两种状态，枚举起来舒服多了。

2.2 单根线上的三种基本场景

现在单独看某一根线，设约束序列为t[0..n-1]，需要构造a[0..n]。逐条看t[i]，其实只有三种情况。

第一种，t[i] = 1。这是最硬的要求，因为a[i] & a[i+1] = 1，按位与结果为 1 的唯一前提就是两个数这一位都为 1。于是立刻得到结论：a[i] = a[i+1] = 1。这个位置没有讨价还价的空间，两个节点必须同时点亮。

第二种，t[i] = 0，但它左边t[i-1] = 1或者右边t[i+1] = 1。这种情况下，这一位需要“断掉”，也就是不能让相邻两个节点同时保持 1。如果左边约束为 1，左边那个节点已经被迫是 1 了，那右边节点必须设为 0，才能让a[i] & a[i+1]清零；反之亦然。

第三种，t[i] = 0，而且两边也是 0。这种位置最轻松，所有相关节点都可以放心置 0，不会引发任何冲突，也不会让结果变大。

所以一根线上的构造，本质上就是找“哪些节点被迫亮灯，哪些节点被迫熄灯”，剩下的全部关掉。看起来很简单，但有一个隐藏的坑：被迫亮灯和被迫熄灯的节点可能会撞在同一个位置上，一旦撞上，就无解。

2.3 无解模式：1, 0, 1

最经典的无解模式就是t = [1, 0, 1]。我们拿它走一遍：

• t[0] = 1，强制a[0] = 1，同时因为a[0] & a[1] = 1，所以a[1] = 1。
• t[2] = 1，强制a[2] = 1，同时因为a[2] & a[3] = 1，所以a[2] = 1、a[3] = 1。
• 中间t[1] = 0，要求a[1] & a[2] = 0，可前面已经推出a[1] = 1、a[2] = 1，这两个 1 撞在一起，结果永远是 1，永远不可能等于 0。

问题就出在：一个 0 两侧都是 1。左边那个 1 把a[1]点亮，右边那个 1 把a[2]点亮，而 0 要求这两个节点至少有一个是 0，两边同时施压，于是爆发冲突。

反过来，t = [1, 0, 0, 1]是合法的。因为中间有两个连续的 0 作为“缓冲区”：t[1] = 0左侧是 1，右侧是 0，可以靠右边的 0 来断；t[2] = 0左侧是 0，右侧是 1，可以靠左边的 0 来断。两个 1 段之间隔着至少两个 0，每根线就能从容完成“先熄灯、再点灯”的切换。

你发现规律没有？不合法的情况，本质上就是存在某个中间位置i，满足t[i] = 0而t[i-1] = 1且t[i+1] = 1。这个判定后面我们会压缩成一行位运算。

3. 从约束到公式：答案为什么这么干净

3.1 第一个和最后一个元素是被“钉死”的

先看边界。a[0]只出现在第一个约束a[0] & a[1] = t[0]里。如果t[0] = 1，a[0]必须是 1；如果t[0] = 0，为了让整个数组尽量小，a[0]设 0 准没错。所以a[0] = t[0]，对应到整数数组，就是ans[0] = target[0]。

最后一个元素a[n]同理，它只出现在最后一个约束a[n-1] & a[n] = t[n-1]里。所以a[n] = t[n-1]，对应ans[n] = target[n-1]。

边界是被约束直接钉死的，没有任何自由度，这也是为什么很多题解里第一个和最后一个元素都直接赋值，不需要套中间公式。

3.2 中间元素的每一位，等于左右约束的或

对于中间某个位置i（对应整数数组下标i，这里1 ≤ i ≤ n-1），它的第 k 位a[i]到底该取什么？我们从“必要性”来推。

a[i]同时参与两个约束：左边是a[i-1] & a[i] = t[i-1]，右边是a[i] & a[i+1] = t[i]。如果t[i-1] = 1，那么a[i]必须等于 1，否则左边的按位与不可能出 1。如果t[i] = 1，那么a[i]必须等于 1，否则右边的按位与不可能出 1。所以：

a[i] ≥ t[i-1] | t[i]

也就是说，a[i]这一位至少要是左边约束值和右边约束值的按位或。而如果t[i-1] = 0且t[i] = 0，这一位没有任何必须点亮的理由，设为 0 完全没问题，还能让结果最小。

所以最优构造就是：

a[i] = t[i-1] | t[i]

翻译回整数数组，就是：

ans[i] = target[i-1] | target[i]（对1 ≤ i ≤ n-1）

这个公式漂亮得不像话。它把两边的约束“或”到一起：哪边要求这一位为 1，这个数就带着这一位。

3.3 验证一遍：为什么这个公式一定满足约束

光推导还不够，得证明它真的满足a[i] & a[i+1] = t[i]。分两种情况。

如果t[i] = 1，那么根据公式，a[i] = t[i-1] | t[i]至少包含 1，a[i+1] = t[i] | t[i+1]也至少包含 1。两个 1 做按位与，这一位必定是 1，约束满足。

如果t[i] = 0，那就要求a[i]和a[i+1]中至少有一个在这一位是 0。这时候要看无解检查。我们前面说过，合法的前提是不存在t[i-1] = 1、t[i] = 0、t[i+1] = 1同时成立。在这个前提下：

• 如果t[i-1] = 1，那么t[i+1]必须为 0，于是a[i] = 1，而a[i+1] = t[i] | t[i+1] = 0，按位与为 0；
• 如果t[i+1] = 1，那么t[i-1]必须为 0，于是a[i] = 0，而a[i+1] = 1，按位与为 0；
• 如果两边都是 0，那a[i] = 0，a[i+1] = 0，按位与自然为 0。

三种子情况全部覆盖，约束一定成立。看到没有，无解判定和构造公式是配套的：先保证中间不会出现1, 0, 1的夹击，再放心大胆地用或运算填数。

3.4 无解判定压缩成一行位运算

前面是逐位分析的，但写成代码可不能真的开 32 层循环。既然每一位独立，那我们可以一次性检查所有位。对每个中间下标i（1 ≤ i ≤ n-2），只要存在某一位同时满足“左侧为 1、中间为 0、右侧为 1”，就说明这一位出现了1, 0, 1模式，直接无解。

把这三个条件翻译成位运算：

• 左侧为 1：target[i-1]中的某些位为 1
• 中间为 0：~target[i]中的某些位为 1
• 右侧为 1：target[i+1]中的某些位为 1

三者按位与，只要结果不为 0，就说明至少有一位同时满足三个条件。所以无解判定只需要一行：

if (target[i - 1] & ~target[i] & target[i + 1]) return {-1};

这行代码一次检查了 32 个位，优雅且高效。如果你还是想逐位理解，可以把它展开成：对每个 bit 判断(t[i-1] == 1 && t[i] == 0 && t[i+1] == 1)。但位运算版本明显更符合这道题的气质。

4. 代码实现：三行核心 + 完整可跑版本

4.1 C++ 实现

核心逻辑就三块：边界赋值、中间或运算、无解检查。完整代码如下：

vector<int> constructArray(vector<int>& target) { int n = target.size(); if (n == 0) return {}; vector<int> ans(n + 1, 0); // 边界：第一个和最后一个元素被约束钉死 ans[0] = target[0]; ans[n] = target[n - 1]; // 中间元素：左右约束取或 for (int i = 1; i < n; i++) { // 顺带检查无解：t[i-1]=1, t[i]=0, t[i+1]=1 同时出现 if (i + 1 < n && (target[i - 1] & ~target[i] & target[i + 1])) { return {-1}; // 约定返回 -1 表示无解 } ans[i] = target[i - 1] | target[i]; } return ans; }

注意无解检查的边界：i从 1 到n-2，所以只有i + 1 < n时才需要检查。中间元素赋值从 1 到n-1，最后一个元素已经在开头单独处理。这样写下来，整个数组每个位置只被赋值一次，时间复杂度 O(n)。

4.2 Python 实现

Python 版本更简洁，位运算语法和 C++ 几乎一样：

def constructArray(target): n = len(target) if n == 0: return [] ans = [0] * (n + 1) ans[0] = target[0] ans[n] = target[n - 1] for i in range(1, n): # 中间某个位置出现 1,0,1 模式则无解 if i + 1 < n and (target[i - 1] & ~target[i] & target[i + 1]): return [-1] ans[i] = target[i - 1] | target[i] return ans

如果题目要求返回空数组而非-1，把return [-1]改成return []即可。两种约定我都见过，提交前先看清题目要求，别在这种地方白送一次 WA。

4.3 复杂度与边界情况分析

时间复杂度 O(n)，空间复杂度 O(1) 额外空间（返回值不算）。n 最大到 10^5 甚至更大都无所谓，因为每个人只做几次常数位运算。

边界情况里最容易翻车的是n = 1。此时target只有一个元素，ans长度是 2，只有一个约束ans[0] & ans[1] = target[0]。代码里ans[0] = target[0]，ans[1] = target[0]，中间循环不执行，结果就是[target[0], target[0]]。这个结果是正确的，因为两个数都必须是target[0]，才能保证按位与出target[0]，同时它还满足最小化要求。

另一个边界是target全为 0。此时ans全为 0，无解检查也不会触发，直接返回全 0 数组。这符合直觉，因为所有约束都要求相邻与为 0，全 0 自然是最小解。

5. 现场踩坑与调试心得

5.1 我踩过的三个坑

第一个坑是无解判定的方向写反。我一开始写的是target[i] & ~target[i-1] & target[i+1]，检查的是“中间为 1、左边为 0、右边为 1”的模式，这当然不对。这个式子会放过真正的1, 0, 1，反而把一些合法情况误判。记住，关键角色是中间的 0，被两侧的 1 夹击，所以先写target[i-1]，再写~target[i]，最后写target[i+1]，顺序别搞混。

第二个坑是忘了单独处理边界。一开始我直接把循环写成：

for (int i = 0; i <= n; i++) ans[i] = target[i] | target[i + 1];

数组越界不说，ans[0]也被错误地算成了target[0] | target[1]。实际上ans[0]只需要等于target[0]，多出来的 1 位会让结果变大，直接违背最小化要求。边界位置没有“左边约束”，只能看右边一个约束，要单独拎出来。

第三个坑是返回值约定。有的题要求无解返回空数组，有的要求返回-1，还有的干脆保证一定有解。我用return {-1}还是return {}完全取决于题目。建议写代码前先看示例里无解情况是什么表现，别把力气花在错误的约定上。

5.2 提交前 30 秒的自查方法

这类构造题最容易出现“自我感觉良好，一交就 WA”的情况。我建议提交前花 30 秒做两件事。

第一，用 O(n) 重新验证一遍。构造完成后，再循环检查每一个ans[i] & ans[i+1] == target[i]。虽然理论上公式已经证明了正确性，但代码里边界处理、下标偏移很容易出错，实际验证一遍能拦住大部分低级 bug。

第二，如果时间充裕，写个随机对拍。随机生成一个合法的ans，算出它的相邻按位与得到target，再拿你的构造函数还原，最后比较还原结果是否和原ans一致。注意这里要生成合法的 target，也就是不能出现1, 0, 1模式，否则没有标准答案可比。对拍脚本可以帮你批量发现隐藏的问题，尤其是在n = 1、全 0 数组这类极端数据上。

我自己常用一个 20 行的对拍脚本，随机跑几万组数据，确认无误后才放心提交。对位运算构造题来说，这个投入产出比极高。

5.3 这套思路还能迁移到哪些题

相邻按位与的构造只是冰山一角。把约束换成按位或、按位异或，套路完全一样，都是拆成 32 根线，分别看每根线上哪些节点被“点亮”或“熄灭”，最后合并成整数表达式。

比如约束变成ans[i] | ans[i+1] = target[i]，逻辑就会反过来：某个位为 0 时两个节点都得是 0，某个位为 1 时至少一个节点是 1，构造公式和无解条件都会相应变化，但“逐位拆线”的思考方式完全复用。再比如 LeetCode 3133 这类“构造数组末元素”的题，核心也是把某些数的二进制位当插槽，逐位决定 0 和 1 的摆放。

更本质的心法是：遇到位运算构造题，别一上来就对着整个整数硬推。先抽一根线出来，把它当成一条独立的 0/1 电路，看清楚电流从哪进、从哪断、哪些节点必须亮、哪些节点可以灭。一根线想明白了，剩下 31 根线不过是重复同样的游戏，最后用位运算表达式一次合并。这个流程我反复用了很多次，每次都能把看起来很玄的构造题变成一道道“排线布线”题。

最后再分享一个小技巧。如果你在纸上推公式时卡住了，试着把所有可能的情况列成 0/1 真值表，盯着约束列反推每一行输出。位运算题不怕情况多，就怕你凭感觉猜。把三种基本场景和无解模式写下来，答案自然而然就浮出水面了。这道题我后来复盘时最大的体会是：ans[i] = target[i-1] | target[i]这个公式不是灵光一现，而是把每一位的“被迫点亮”条件彻底盘清楚之后，水到渠成的结果。