把“LeetCode 3314 构造最小位运算数组 I”拿出来重新刷的时候我其实有点意外——它在标签里写着“简单”但评论区里不少人和我第一遍一样上来就想枚举、想回溯结果绕了不少弯路。我后来把约束一句一句翻译成人话才发现这题的骨架特别清晰位运算只是外衣真正考的是“怎么在约束下贪心地构造一个字典序最小的数组”。这篇文章就把我完整复盘的过程写出来从约束拆解、贪心证明到代码实现和易错边界一步步讲到能直接照着做。先说清楚我按自己复盘时整理的等价题面来展开——给定两个非负整数 n 和 k构造一个长度为 n 的数组 arr要求所有元素的按位与AND结果等于 k数组内元素两两不同在满足前两条的前提下数组的字典序最小。不同平台对“最小”二字的定义有时会写成“元素和最小”但考察的贪心逻辑是同一套后面我会专门聊这个变体。1. 题面吃透三个词拆出真正的约束“构造最小位运算数组”这句话里有三个词构造、最小、位运算。我第一遍做的时候注意力全放在“位运算”上满脑子都是各种位运算技巧结果把题想复杂了。实际上把三个词拆开看真正决定解题方向的只有两个约束。第一个约束是“所有元素的按位与等于 k”。这句话翻译成人话就是数组里每个元素都必须“包含” k 的所有二进制 1 位。怎么理解按位与的规则是某一位只要有一个元素是 0整个结果这一位就是 0。要让最终结果的第 i 位等于 1就必须保证数组里每一个元素在第 i 位上都是 1。换句话说k 的二进制里哪些位是 1arr 的每一个元素在这些位上就都得是 1缺一不可。第二个约束是“元素两两不同”。这个约束才是这题真正的分水岭。如果允许重复元素答案会无聊得可怕直接构造一个全是 k 的数组AND 结果自然是 k字典序也惬意。可一旦要求互不相同我们就必须在 k 这个“地基”之上给每个元素加上不同的“装饰位”这就把一道无脑题变成了有推理空间的构造题。第三个约束“字典序最小”其实是给贪心定了一个明确的目标函数。数组字典序比较和字符串比较一样先比第一个元素再比第二个依次往后。所以要让整个数组字典序最小策略非常简单粗暴让第一个元素尽可能小在这个前提下让第二个元素尽可能小再在这个前提下让第三个元素尽可能小依此类推。这就是经典的前缀贪心框架。我第一遍错就错在没做这个拆解。我试图用回溯去枚举行不行当然“可行”n 稍微大一点状态空间就爆了。后来我把三个约束重新写了一遍发现事情比想象中简单得多第一个约束保证了每个元素的“必含位”第二个约束让我们只能在“空闲位”上做文章第三个约束则直接告诉我们应该从低位往高位去选。三句话合在一起解题路径就自己长出来了。2. 从 AND 约束反推每个元素的地基和装饰位2.1 为什么每个元素都必须是“包含 k”的数先定义一个基础条件对于任意元素 x它必须满足 x k k。展开来就是k 中所有为 1 的位在 x 中都必须为 1而 k 中为 0 的位x 里可以随意。这个条件还隐含了一个数值大小关系x 一定大于等于 k。因为 x 的二进制完整覆盖了 k 的所有 1 位即使 x 在 k 为 0 的位上全是 0x 的数值也顶多和 k 相等只要 x 在任何一个空闲位上填了 1x 就一定严格大于 k。这个观察非常关键。它告诉我们一个事实无论怎么构造数组的第一个元素最小也只能是 k不可能再小了。因为比 k 小的数必然在 k 的某个 1 位上丢了分数那样整个数组的 AND 结果就凑不出 k 了。所以第一个元素直接锁定为 k没有讨价还价的余地。我一开始特别想当然地认为可以先放一个小一点的数然后用后面的“大家伙”把缺的位补回来。但按位与不是求和它没有“补”这个概念一位为 0 就是全局为 0。你前面的数缺了一位 1后面所有数这一位拼成 1 也救不回来。这个认知误区是我踩过最大的坑写出来提醒一下。2.2 把 k 看成地基空闲位看成装饰层既然每个元素都必须完整携带 k 的所有 1 位那我们可以把 k 想象成一块所有人共用的“地基”它固定不可变。每个元素之间的差异只能体现 k 之外那些自由位上。举个例子假设 k 5二进制是 101。那么每个元素必须以“101”为基底但可以在第 1 位从低位数的第 1 位对应数值 2上选择 0 或 1。于是可行的元素包括 5101、7111等等。注意第 1 位是 k 的 0 位它就是我们说的“空闲位”。如果 k 4二进制是 100。地基是第 2 位为 1空闲位是第 0 位和第 1 位也就是数值 1 和 2。那么合法元素可以是 4100、5101、6110、7111。这个概念一旦建立构造问题就变成了一个更直观的形式每一个元素等于「固定的地基」加上「从空闲位集合里挑几个位置点亮」。而“元素互不相同”进一步变成每个元素所点亮的空闲位组合不能重复。这其实有点像拼贴画所有人都用同一块底板区别只是各自往底板上贴了不同位置的小亮片。我们接下来要做的就是按字典序最小的规则设计出一串“贴亮片”的方式。2.3 最小合法元素为什么一定是 k 相邻的那个数在动手构造之前我还做了一件小事把“当前已经用过的元素集合”和“可行的下一个元素”放到一起比较它们的数值大小。这帮我验证了贪心的直觉。当数组第一个元素已经确定为 k 时第二个元素必须是一个不等于 k、且包含 k 所有 1 位的数。在所有这样的数里最小的显然是从低位开始找 k 的第一个空闲位把它点亮其他空闲位全部保持 0。这个数的值就是 k 2^bit其中 bit 是最低空闲位的下标。为什么要选最低空闲位而不是随便选一个因为往越高的位上加 1数字增加得越多。比如 k4最低空闲位是第 0 位点亮的数是 5如果点亮第 1 位得到 6比 5 大。所以“最低”和“最小”在这里是等价的。这个等价关系是整个贪心算法的地基。3. “字典序最小”的贪心构造从最低空闲位点亮3.1 前缀贪心每个位置都取当前可取的最小值字典序最小是一种“前缀式”的最优性要求第一位能取多小就取多小第一位定死之后第二位才能取多小就取多小以此类推。这天然适合用贪心处理因为每一步都只需关注当前状态下的局部最小选择不必为了后续元素做全局牺牲。更妙的是在这个问题里局部最小选择不会影响后续的可行性。原因是我们每点亮一个空闲位只是把这个空闲位从“可用集合”里划掉而不改变地基也不改变其他空闲位的可用性。用一个不太严谨但很好记的说法就是空闲位的数量是固定的你早用晚用总数都一样而数值小的空闲位越早用数组的前缀就越小。所以贪心在这里不仅直观而且是严格正确的。3.2 一遍手动模拟看贪心是怎么一步步长的我们来完整跑一个例子。设 n 4k 4二进制 100。第一步答案数组先放 4。此时已经点亮的空闲位集合为空。第二步当前值是 4。从低位往高位找 k 的空闲位第 0 位是 0所以点亮它当前值变成 5101。数组变成 [4, 5]。第三步当前值是 5。第 0 位已经被点亮了不能再使用继续往高找第 1 位是 k 的空闲位且还没被点亮于是点亮它当前值变成 7111。数组变成 [4, 5, 7]。第四步当前值是 7。第 0 位、第 1 位都被点亮了第 2 位是 k 的必含位不能动第 3 位是空闲位点亮它当前值变成 151111。数组变成 [4, 5, 7, 15]。验证一下最终结果4 5 7 15。4 是 01005 是 01017 是 011115 是 1111。按位与的结果是 0100也就是 4等于 k符合条件元素各不相同也满足。至于它是不是字典序最小你可以尝试把第二个元素换成 6数组变成 [4, 6, ...]第一个元素同样是 4但第二个元素 6 大于 5字典序已经输了。所以贪心得到的确实是唯一且最小。3.3 为什么“最低空闲位”这个选择能一直成立这里有个容易让人怀疑的点每次点亮“当前值的最低空闲位”但当前值的空闲位集合是随着构造过程动态变化的。我怎么保证这样一个看似只盯着眼前数字的贪心不会在某个时刻把后续元素带进死胡同答案在于我们对空闲位只会做减法不会做加法。每构造一个元素只会点亮一个新的空闲位已经点亮的位不会再变回 0。所以整个过程可以看成把 k 的可用空闲位按从小到大的顺序一个接一个地“消耗”掉。第 i 个构造出来的元素其实就是 k 加上“前 i 个最小空闲位”的累加和。这也能解释为什么不能跳过小空闲位去用大的一旦某个元素跳过了小空闲位那么为了保持元素互异后面某个元素势必要多点亮一个位才能区分开结果是字典序更大。而如果现在就把小空闲位用掉后面的元素只会更大前缀却不会更坏。这就是贪心的“无后效性”当前选择的代价不会对未来产生额外负担。3.4 一个反直觉的边界k 的每一位都是 1 怎么办如果 k 在掩码范围内所有位都是 1比如 k 7 且只考虑三位那么空闲位为零。这时候若 n 1答案就是 [7]若 n 1我们压根找不到第二个不同的合法元素——每个元素都必须保留这三位全是 1而可变换的自由位又不存在。此时无解。这类“全 1 边界”最容易在实现里翻车。有人会在循环里一直找(~cur ~k)如果没注意掩码可能取到一个超出题目数值范围的空闲位导致构造出超大的数。我自己的做法是先把掩码范围定死统一用mask截断位运算结果同时在循环开头判断free 0直接返回空数组或题目要求的特殊值避免死循环。4. 代码实现、边界测试和两个溢出细节4.1 C 实现为什么我坚持用掩码截断核心代码不长但两个细节值得单独立起来说。先给完整实现class Solution { public: vectorint constructMinimumBitwiseArray(int n, int k) { vectorint ans; ans.push_back(k); int cur k; // 题目通常保证答案在 30 位以内这里用 31 位掩码做安全截断 int mask (1 30) - 1; // 只允许使用第 0 ~ 29 位 for (int i 1; i n; i) { // 找到当前值中k 为 0 且 cur 为 0 的最低位 int free (~cur ~k) mask; if (free 0) { return {}; // 空闲位用完了无解 } int lowbit free -free; // 取出最低的 1 位 cur | lowbit; ans.push_back(cur); } return ans; } };第一个细节为什么是(~cur ~k) mask而不是简单地~k mask。因为 cur 会记录我们一路上已经点亮过的空闲位。如果一个位在 k 中是 0但已经被之前的某个元素点亮了那么当前元素就不能再用它了否则当前元素会等于之前的某个元素。所以我们需要同时排除 cur 中已经为 1 的位。这个 ~cur过滤条件是“元素互异”约束在实现层面的直接体现漏掉它会让程序在高位空闲位耗尽后出错。第二个细节掩码截断。C 里~cur会把符号位一起取反得到的是负数补码。如果不加掩码free的高位会莫名其妙出现一堆 1然后free -free可能取到一个非常高的位导致 cur 瞬间变成一个超过题目范围的天文数字。用(1 30) - 1把计算限制在一个安全的位宽里既避免溢出也符合大多数这类题目的数值范围。如果题目给的 k 和 n 范围更大记得把这个掩码的位数同步调大或者直接改用long long。4.2 从 C 到 Python位运算的符号陷阱不一样用 Python 刷题的同学要注意Python 整数是任意精度的~cur的结果永远带负号所以掩码这一步同样不能省。我顺手写了一个等价的 Python 版本def construct(n: int, k: int) - list[int]: ans [k] cur k mask (1 30) - 1 for _ in range(n - 1): free (~cur ~k) mask if free 0: return [] low free -free cur | low ans.append(cur) return ansPython 版本的好处是无需担心整数溢出坏处是如果你忘了掩码那free -free取到的低位依然是正确的最低位但free里那些高位的 1 会影响你对“是否还有空闲位”的判断代码行为会变得很隐晦。所以我的建议是不管什么语言都把“掩码”这个习惯焊在脑子里位运算题里留一手截断能省掉十次 debug。4.3 边界情况一览k0、n1、位宽不足我把踩过的边界整理成了一张表方便大家对照自测场景输入示例期望输出说明数组只有一个元素n1, k6[6]无需构造第二个元素直接返回k0需要多个元素n3, k0[0, 1, 2]地基为 0元素就是从 0 开始逐位点亮空闲位恰好够用n3, k4[4, 5, 7]第 0、1 位依次点亮空闲位不够n3, k7只考虑 3 位无解没有可变换的自由位大范围数值n2, k1e9见下方说明注意掩码位宽是否覆盖k0这个 case 特别有意思。地基是 0意味着每个元素没有任何必含位AND 结果恒为 0条件 1 永远成立元素互异的要求等价于让我们输出 n 个互不相同的非负整数。贪心给出的序列正好是 0、1、2、3……因为在当前值为 0 时最低空闲位是第 0 位点亮后变成 1当前值为 1 时第 0 位已被占用下一个空闲位是第 1 位点亮后变成 3等一下这里要仔细算当前值 101k0空闲位是所有位。第 0 位已经为 1下一个最低空闲位是第 1 位点亮后当前值变成 311而不是 210。但我们已经输出过 0、1接下来按字典序最小的合法元素应该是 2 还是 3这里就触及了一个我最初没想清楚的细节。答案是如果按我上面的贪心实现输出是 [0, 1, 3, 7, ...]因为我们需要从当前值出发找“还没用过的空闲位”。2 的二进制是 10它确实不等于 0 和 1AND 结果也是 0但我们的贪心跳过了第 0 位去点亮第 1 位得到 3而 3 在字典序上大于 2。这不是最优解。这说明当k0这种特殊情况下“从当前值找最低空闲位”并不是完整的贪心策略正确做法应该维护一个“全局已使用的空闲位集合”每次从集合外选最低的一位来点亮而不是只看当前值的空闲位。对于 k0全局策略得到的就是 [0, 1, 2, 4, ...]即每次从最低的空闲位点亮不要求基于当前值。回归到一般情况怎么修正实现应该维护两个东西地基 k以及一个used或等价信息记录哪些空闲位已经被点亮。每次构造新元素时在所有“未使用且 k 为 0”的位中选最低的点亮它。vectorint ans; ans.push_back(k); int cur k; // 当前值 int used 0; // 记录已经用过的空闲位 int mask (1 30) - 1; for (int i 1; i n; i) { int available (~k ~used) mask; if (available 0) return {}; int lowbit available -available; used | lowbit; cur k | used; ans.push_back(cur); }这里的关键差别在于cur k | used不是每次在当前值上加一个 bit而是重新用“地基 已用空闲位集合”来合成当前元素。used记录了所有曾经点亮过的空闲位第 i 个元素就是 k 与「前 i 个最小空闲位」的并集。用这个修正实现跑 k0, n4得到 [0, 1, 2, 4]第 1 个空闲位是第 0 位值为 1点亮后第 2 个元素 1第 2 个空闲位是第 1 位值为 2点亮后第 3 个元素 2第 3 个空闲位是第 2 位值为 4点亮后第 4 个元素 4。结果完全符合“字典序最小且互不相同”的要求。跑 k4, n4得到 [4, 5, 6, 12] 还是 [4, 5, 6, 8]我们来算地基是第 2 位值为 4空闲位按数值从小到大是第 0 位1、第 1 位2、第 3 位8、第 4 位16……按全局已用集合逐个点亮第一个元素 [4] 只含地基点亮第 0 位得 [4, 5]点亮第 1 位得 [4, 5, 6]点亮第 3 位得 [4, 5, 6, 12]。因为 412815不对4 | 1 | 2 | 8 15所以第三个点亮后值是 15不是 12。我口算错了更正4|1|2 74|1|2|8 15。所以数组是 [4, 5, 7, 15]。但这个和前面模拟一致因为中间的空闲位没有被跳过。全局策略和“从当前值找最低空闲位”在大多数情况下结果一样区别只在跳过位的场景下会出现。因此我建议实现统一用used集合版思路更干净也不容易踩 k0 这种特例。4.4 溢出、符号位和掩码的选择建议掩码选择取决于题目数值范围。如果 k 最高可能到 10^9约 2^30那么掩码至少要到第 30 位。如果题目没有明确说明我一般会留一点余量比如(1LL 31) - 1然后强转成需要的类型避免 C 中1 31的未定义行为。这条建议同样适用于未来做位运算相关的任何题目先看数据范围再定掩码是常规操作不是过度设计。5. 从 I 到 II位运算构造题的通用套路5.1 变体“元素和最小”和“字典序最小”其实同源LeetCode 题号带 I / II 的系列II 通常会在 I 的基础上加条件或放大范围。这个系列常见的 II 版本是把“字典序最小”改成“数组元素之和最小”甚至加上“数组严格递增”之类的新约束。其实“元素和最小”和“字典序最小”在大多数情况下指向同一种构造优先点亮低位的空闲位。因为无论是字典序比较还是累加和比较低位都比高位“便宜”。二者的差异只在具体比较规则上略有不同但核心思想一致先画好地基再把空闲位按从小到大依次点亮。做这一类题养成把目标函数翻译成“位的优先级”的习惯比死记结论有用得多。5.2 构造题的通用三步拆解法复盘这道题后我给自己总结了一个做位运算构造题的三步流程在这里分享一下首先识别硬约束。所谓硬约束就是所有构造出的元素都必须满足的条件。本题中“每个元素包含 k 的所有 1 位”就是硬约束。把硬约束写成位运算表达式通常能直接得到每个元素的“骨架”。然后识别自由变量。在硬约束之外哪些位是可以自由切换的哪些位一旦使用就不能再用。本题的自由变量是“k 中为 0 且尚未被任何元素占用的位”。自由变量决定了我们能在多大范围内展开构造也是无解判定的依据。最后按字典序或求和目标排序。把自由变量按位权从小到大排列逐个点亮直到元素个数达到要求或自由变量耗尽。这一步其实就是在做贪心而贪心的正确性往往由“低位先用的代价不高于高位先用”来保证。5.3 无解判定什么时候必须停手有一个细节我是在写代码之后才想明白的无解条件不仅发生在“自由位完全不存在”也发生在“自由位存在但数量不够”。只要空闲位总数小于 n-1就无法构造出 n 个互不相同的合法元素。因为合法元素的个数恰好等于 1 空闲位数其中那个 1 就是地基本身 k。如果 K 在给定掩码范围内所有可能空闲位都被占满你还在继续循环那就该返回错误或特殊值。测试时我习惯用n100, k2^29-1这种极端值去压一下确保程序不会因为空转而死循环也不会因为构造出超范围值而出错。这个习惯让我在几道位运算题里都提前发现了 bug。5.4 从这题延伸出去还能怎么考想明白 3314 之后再去看同类的构造题会有一种“打怪升级”的顺畅感。一个常见的进阶方向是把 k 也变成一个数组每个查询单独给出 n_i 和 k_i要求返回所有答案。这种多查询版本本质上没有任何新东西只是把单次构造的复杂度控制住预处理或者原地构造即可属于“换汤不换药”。另一个进阶方向是把 AND 换成 XOR 或 OR。按位 OR 的情况下硬约束从“每个元素必须包含 k 的 1 位”变成“至少一个元素包含 k 的 1 位”自由变量更多构造策略也随之改变但分析问题的顺序还是那三步。我在复盘时顺手把 OR 版本也推了一遍体会是只要先把约束写成位运算表达式后面大概率都能迎刃而解。写在折腾完这题之后最后分享两个我实际踩过的坑。第一个是千万别小看“简单”标签尤其是位运算构造题它考的不是位运算技巧本身而是把自然语言约束翻译成位运算表达式的熟练度。我第一遍用回溯写写了半天删掉重来第二遍先把约束写在纸上一页纸都没写完就有了解法。第二个是掩码问题无论 C 还是 Python做位运算题时随手定义一个mask是好习惯它能挡住补码的符号位陷阱也能防止构造出超范围的数。这题之后的几周我每次做位运算题都会先把数据范围瞄一眼再定掩码手感稳了很多。建议你也试试这个流程。
把“LeetCode 3314 构造最小位运算数组 I”拿出来重新刷的时候我其实有点意外——它在标签里写着“简单”但评论区里不少人和我第一遍一样上来就想枚举、想回溯结果绕了不少弯路。我后来把约束一句一句翻译成人话才发现这题的骨架特别清晰位运算只是外衣真正考的是“怎么在约束下贪心地构造一个字典序最小的数组”。这篇文章就把我完整复盘的过程写出来从约束拆解、贪心证明到代码实现和易错边界一步步讲到能直接照着做。先说清楚我按自己复盘时整理的等价题面来展开——给定两个非负整数 n 和 k构造一个长度为 n 的数组 arr要求所有元素的按位与AND结果等于 k数组内元素两两不同在满足前两条的前提下数组的字典序最小。不同平台对“最小”二字的定义有时会写成“元素和最小”但考察的贪心逻辑是同一套后面我会专门聊这个变体。1. 题面吃透三个词拆出真正的约束“构造最小位运算数组”这句话里有三个词构造、最小、位运算。我第一遍做的时候注意力全放在“位运算”上满脑子都是各种位运算技巧结果把题想复杂了。实际上把三个词拆开看真正决定解题方向的只有两个约束。第一个约束是“所有元素的按位与等于 k”。这句话翻译成人话就是数组里每个元素都必须“包含” k 的所有二进制 1 位。怎么理解按位与的规则是某一位只要有一个元素是 0整个结果这一位就是 0。要让最终结果的第 i 位等于 1就必须保证数组里每一个元素在第 i 位上都是 1。换句话说k 的二进制里哪些位是 1arr 的每一个元素在这些位上就都得是 1缺一不可。第二个约束是“元素两两不同”。这个约束才是这题真正的分水岭。如果允许重复元素答案会无聊得可怕直接构造一个全是 k 的数组AND 结果自然是 k字典序也惬意。可一旦要求互不相同我们就必须在 k 这个“地基”之上给每个元素加上不同的“装饰位”这就把一道无脑题变成了有推理空间的构造题。第三个约束“字典序最小”其实是给贪心定了一个明确的目标函数。数组字典序比较和字符串比较一样先比第一个元素再比第二个依次往后。所以要让整个数组字典序最小策略非常简单粗暴让第一个元素尽可能小在这个前提下让第二个元素尽可能小再在这个前提下让第三个元素尽可能小依此类推。这就是经典的前缀贪心框架。我第一遍错就错在没做这个拆解。我试图用回溯去枚举行不行当然“可行”n 稍微大一点状态空间就爆了。后来我把三个约束重新写了一遍发现事情比想象中简单得多第一个约束保证了每个元素的“必含位”第二个约束让我们只能在“空闲位”上做文章第三个约束则直接告诉我们应该从低位往高位去选。三句话合在一起解题路径就自己长出来了。2. 从 AND 约束反推每个元素的地基和装饰位2.1 为什么每个元素都必须是“包含 k”的数先定义一个基础条件对于任意元素 x它必须满足 x k k。展开来就是k 中所有为 1 的位在 x 中都必须为 1而 k 中为 0 的位x 里可以随意。这个条件还隐含了一个数值大小关系x 一定大于等于 k。因为 x 的二进制完整覆盖了 k 的所有 1 位即使 x 在 k 为 0 的位上全是 0x 的数值也顶多和 k 相等只要 x 在任何一个空闲位上填了 1x 就一定严格大于 k。这个观察非常关键。它告诉我们一个事实无论怎么构造数组的第一个元素最小也只能是 k不可能再小了。因为比 k 小的数必然在 k 的某个 1 位上丢了分数那样整个数组的 AND 结果就凑不出 k 了。所以第一个元素直接锁定为 k没有讨价还价的余地。我一开始特别想当然地认为可以先放一个小一点的数然后用后面的“大家伙”把缺的位补回来。但按位与不是求和它没有“补”这个概念一位为 0 就是全局为 0。你前面的数缺了一位 1后面所有数这一位拼成 1 也救不回来。这个认知误区是我踩过最大的坑写出来提醒一下。2.2 把 k 看成地基空闲位看成装饰层既然每个元素都必须完整携带 k 的所有 1 位那我们可以把 k 想象成一块所有人共用的“地基”它固定不可变。每个元素之间的差异只能体现 k 之外那些自由位上。举个例子假设 k 5二进制是 101。那么每个元素必须以“101”为基底但可以在第 1 位从低位数的第 1 位对应数值 2上选择 0 或 1。于是可行的元素包括 5101、7111等等。注意第 1 位是 k 的 0 位它就是我们说的“空闲位”。如果 k 4二进制是 100。地基是第 2 位为 1空闲位是第 0 位和第 1 位也就是数值 1 和 2。那么合法元素可以是 4100、5101、6110、7111。这个概念一旦建立构造问题就变成了一个更直观的形式每一个元素等于「固定的地基」加上「从空闲位集合里挑几个位置点亮」。而“元素互不相同”进一步变成每个元素所点亮的空闲位组合不能重复。这其实有点像拼贴画所有人都用同一块底板区别只是各自往底板上贴了不同位置的小亮片。我们接下来要做的就是按字典序最小的规则设计出一串“贴亮片”的方式。2.3 最小合法元素为什么一定是 k 相邻的那个数在动手构造之前我还做了一件小事把“当前已经用过的元素集合”和“可行的下一个元素”放到一起比较它们的数值大小。这帮我验证了贪心的直觉。当数组第一个元素已经确定为 k 时第二个元素必须是一个不等于 k、且包含 k 所有 1 位的数。在所有这样的数里最小的显然是从低位开始找 k 的第一个空闲位把它点亮其他空闲位全部保持 0。这个数的值就是 k 2^bit其中 bit 是最低空闲位的下标。为什么要选最低空闲位而不是随便选一个因为往越高的位上加 1数字增加得越多。比如 k4最低空闲位是第 0 位点亮的数是 5如果点亮第 1 位得到 6比 5 大。所以“最低”和“最小”在这里是等价的。这个等价关系是整个贪心算法的地基。3. “字典序最小”的贪心构造从最低空闲位点亮3.1 前缀贪心每个位置都取当前可取的最小值字典序最小是一种“前缀式”的最优性要求第一位能取多小就取多小第一位定死之后第二位才能取多小就取多小以此类推。这天然适合用贪心处理因为每一步都只需关注当前状态下的局部最小选择不必为了后续元素做全局牺牲。更妙的是在这个问题里局部最小选择不会影响后续的可行性。原因是我们每点亮一个空闲位只是把这个空闲位从“可用集合”里划掉而不改变地基也不改变其他空闲位的可用性。用一个不太严谨但很好记的说法就是空闲位的数量是固定的你早用晚用总数都一样而数值小的空闲位越早用数组的前缀就越小。所以贪心在这里不仅直观而且是严格正确的。3.2 一遍手动模拟看贪心是怎么一步步长的我们来完整跑一个例子。设 n 4k 4二进制 100。第一步答案数组先放 4。此时已经点亮的空闲位集合为空。第二步当前值是 4。从低位往高位找 k 的空闲位第 0 位是 0所以点亮它当前值变成 5101。数组变成 [4, 5]。第三步当前值是 5。第 0 位已经被点亮了不能再使用继续往高找第 1 位是 k 的空闲位且还没被点亮于是点亮它当前值变成 7111。数组变成 [4, 5, 7]。第四步当前值是 7。第 0 位、第 1 位都被点亮了第 2 位是 k 的必含位不能动第 3 位是空闲位点亮它当前值变成 151111。数组变成 [4, 5, 7, 15]。验证一下最终结果4 5 7 15。4 是 01005 是 01017 是 011115 是 1111。按位与的结果是 0100也就是 4等于 k符合条件元素各不相同也满足。至于它是不是字典序最小你可以尝试把第二个元素换成 6数组变成 [4, 6, ...]第一个元素同样是 4但第二个元素 6 大于 5字典序已经输了。所以贪心得到的确实是唯一且最小。3.3 为什么“最低空闲位”这个选择能一直成立这里有个容易让人怀疑的点每次点亮“当前值的最低空闲位”但当前值的空闲位集合是随着构造过程动态变化的。我怎么保证这样一个看似只盯着眼前数字的贪心不会在某个时刻把后续元素带进死胡同答案在于我们对空闲位只会做减法不会做加法。每构造一个元素只会点亮一个新的空闲位已经点亮的位不会再变回 0。所以整个过程可以看成把 k 的可用空闲位按从小到大的顺序一个接一个地“消耗”掉。第 i 个构造出来的元素其实就是 k 加上“前 i 个最小空闲位”的累加和。这也能解释为什么不能跳过小空闲位去用大的一旦某个元素跳过了小空闲位那么为了保持元素互异后面某个元素势必要多点亮一个位才能区分开结果是字典序更大。而如果现在就把小空闲位用掉后面的元素只会更大前缀却不会更坏。这就是贪心的“无后效性”当前选择的代价不会对未来产生额外负担。3.4 一个反直觉的边界k 的每一位都是 1 怎么办如果 k 在掩码范围内所有位都是 1比如 k 7 且只考虑三位那么空闲位为零。这时候若 n 1答案就是 [7]若 n 1我们压根找不到第二个不同的合法元素——每个元素都必须保留这三位全是 1而可变换的自由位又不存在。此时无解。这类“全 1 边界”最容易在实现里翻车。有人会在循环里一直找(~cur ~k)如果没注意掩码可能取到一个超出题目数值范围的空闲位导致构造出超大的数。我自己的做法是先把掩码范围定死统一用mask截断位运算结果同时在循环开头判断free 0直接返回空数组或题目要求的特殊值避免死循环。4. 代码实现、边界测试和两个溢出细节4.1 C 实现为什么我坚持用掩码截断核心代码不长但两个细节值得单独立起来说。先给完整实现class Solution { public: vectorint constructMinimumBitwiseArray(int n, int k) { vectorint ans; ans.push_back(k); int cur k; // 题目通常保证答案在 30 位以内这里用 31 位掩码做安全截断 int mask (1 30) - 1; // 只允许使用第 0 ~ 29 位 for (int i 1; i n; i) { // 找到当前值中k 为 0 且 cur 为 0 的最低位 int free (~cur ~k) mask; if (free 0) { return {}; // 空闲位用完了无解 } int lowbit free -free; // 取出最低的 1 位 cur | lowbit; ans.push_back(cur); } return ans; } };第一个细节为什么是(~cur ~k) mask而不是简单地~k mask。因为 cur 会记录我们一路上已经点亮过的空闲位。如果一个位在 k 中是 0但已经被之前的某个元素点亮了那么当前元素就不能再用它了否则当前元素会等于之前的某个元素。所以我们需要同时排除 cur 中已经为 1 的位。这个 ~cur过滤条件是“元素互异”约束在实现层面的直接体现漏掉它会让程序在高位空闲位耗尽后出错。第二个细节掩码截断。C 里~cur会把符号位一起取反得到的是负数补码。如果不加掩码free的高位会莫名其妙出现一堆 1然后free -free可能取到一个非常高的位导致 cur 瞬间变成一个超过题目范围的天文数字。用(1 30) - 1把计算限制在一个安全的位宽里既避免溢出也符合大多数这类题目的数值范围。如果题目给的 k 和 n 范围更大记得把这个掩码的位数同步调大或者直接改用long long。4.2 从 C 到 Python位运算的符号陷阱不一样用 Python 刷题的同学要注意Python 整数是任意精度的~cur的结果永远带负号所以掩码这一步同样不能省。我顺手写了一个等价的 Python 版本def construct(n: int, k: int) - list[int]: ans [k] cur k mask (1 30) - 1 for _ in range(n - 1): free (~cur ~k) mask if free 0: return [] low free -free cur | low ans.append(cur) return ansPython 版本的好处是无需担心整数溢出坏处是如果你忘了掩码那free -free取到的低位依然是正确的最低位但free里那些高位的 1 会影响你对“是否还有空闲位”的判断代码行为会变得很隐晦。所以我的建议是不管什么语言都把“掩码”这个习惯焊在脑子里位运算题里留一手截断能省掉十次 debug。4.3 边界情况一览k0、n1、位宽不足我把踩过的边界整理成了一张表方便大家对照自测场景输入示例期望输出说明数组只有一个元素n1, k6[6]无需构造第二个元素直接返回k0需要多个元素n3, k0[0, 1, 2]地基为 0元素就是从 0 开始逐位点亮空闲位恰好够用n3, k4[4, 5, 7]第 0、1 位依次点亮空闲位不够n3, k7只考虑 3 位无解没有可变换的自由位大范围数值n2, k1e9见下方说明注意掩码位宽是否覆盖k0这个 case 特别有意思。地基是 0意味着每个元素没有任何必含位AND 结果恒为 0条件 1 永远成立元素互异的要求等价于让我们输出 n 个互不相同的非负整数。贪心给出的序列正好是 0、1、2、3……因为在当前值为 0 时最低空闲位是第 0 位点亮后变成 1当前值为 1 时第 0 位已被占用下一个空闲位是第 1 位点亮后变成 3等一下这里要仔细算当前值 101k0空闲位是所有位。第 0 位已经为 1下一个最低空闲位是第 1 位点亮后当前值变成 311而不是 210。但我们已经输出过 0、1接下来按字典序最小的合法元素应该是 2 还是 3这里就触及了一个我最初没想清楚的细节。答案是如果按我上面的贪心实现输出是 [0, 1, 3, 7, ...]因为我们需要从当前值出发找“还没用过的空闲位”。2 的二进制是 10它确实不等于 0 和 1AND 结果也是 0但我们的贪心跳过了第 0 位去点亮第 1 位得到 3而 3 在字典序上大于 2。这不是最优解。这说明当k0这种特殊情况下“从当前值找最低空闲位”并不是完整的贪心策略正确做法应该维护一个“全局已使用的空闲位集合”每次从集合外选最低的一位来点亮而不是只看当前值的空闲位。对于 k0全局策略得到的就是 [0, 1, 2, 4, ...]即每次从最低的空闲位点亮不要求基于当前值。回归到一般情况怎么修正实现应该维护两个东西地基 k以及一个used或等价信息记录哪些空闲位已经被点亮。每次构造新元素时在所有“未使用且 k 为 0”的位中选最低的点亮它。vectorint ans; ans.push_back(k); int cur k; // 当前值 int used 0; // 记录已经用过的空闲位 int mask (1 30) - 1; for (int i 1; i n; i) { int available (~k ~used) mask; if (available 0) return {}; int lowbit available -available; used | lowbit; cur k | used; ans.push_back(cur); }这里的关键差别在于cur k | used不是每次在当前值上加一个 bit而是重新用“地基 已用空闲位集合”来合成当前元素。used记录了所有曾经点亮过的空闲位第 i 个元素就是 k 与「前 i 个最小空闲位」的并集。用这个修正实现跑 k0, n4得到 [0, 1, 2, 4]第 1 个空闲位是第 0 位值为 1点亮后第 2 个元素 1第 2 个空闲位是第 1 位值为 2点亮后第 3 个元素 2第 3 个空闲位是第 2 位值为 4点亮后第 4 个元素 4。结果完全符合“字典序最小且互不相同”的要求。跑 k4, n4得到 [4, 5, 6, 12] 还是 [4, 5, 6, 8]我们来算地基是第 2 位值为 4空闲位按数值从小到大是第 0 位1、第 1 位2、第 3 位8、第 4 位16……按全局已用集合逐个点亮第一个元素 [4] 只含地基点亮第 0 位得 [4, 5]点亮第 1 位得 [4, 5, 6]点亮第 3 位得 [4, 5, 6, 12]。因为 412815不对4 | 1 | 2 | 8 15所以第三个点亮后值是 15不是 12。我口算错了更正4|1|2 74|1|2|8 15。所以数组是 [4, 5, 7, 15]。但这个和前面模拟一致因为中间的空闲位没有被跳过。全局策略和“从当前值找最低空闲位”在大多数情况下结果一样区别只在跳过位的场景下会出现。因此我建议实现统一用used集合版思路更干净也不容易踩 k0 这种特例。4.4 溢出、符号位和掩码的选择建议掩码选择取决于题目数值范围。如果 k 最高可能到 10^9约 2^30那么掩码至少要到第 30 位。如果题目没有明确说明我一般会留一点余量比如(1LL 31) - 1然后强转成需要的类型避免 C 中1 31的未定义行为。这条建议同样适用于未来做位运算相关的任何题目先看数据范围再定掩码是常规操作不是过度设计。5. 从 I 到 II位运算构造题的通用套路5.1 变体“元素和最小”和“字典序最小”其实同源LeetCode 题号带 I / II 的系列II 通常会在 I 的基础上加条件或放大范围。这个系列常见的 II 版本是把“字典序最小”改成“数组元素之和最小”甚至加上“数组严格递增”之类的新约束。其实“元素和最小”和“字典序最小”在大多数情况下指向同一种构造优先点亮低位的空闲位。因为无论是字典序比较还是累加和比较低位都比高位“便宜”。二者的差异只在具体比较规则上略有不同但核心思想一致先画好地基再把空闲位按从小到大依次点亮。做这一类题养成把目标函数翻译成“位的优先级”的习惯比死记结论有用得多。5.2 构造题的通用三步拆解法复盘这道题后我给自己总结了一个做位运算构造题的三步流程在这里分享一下首先识别硬约束。所谓硬约束就是所有构造出的元素都必须满足的条件。本题中“每个元素包含 k 的所有 1 位”就是硬约束。把硬约束写成位运算表达式通常能直接得到每个元素的“骨架”。然后识别自由变量。在硬约束之外哪些位是可以自由切换的哪些位一旦使用就不能再用。本题的自由变量是“k 中为 0 且尚未被任何元素占用的位”。自由变量决定了我们能在多大范围内展开构造也是无解判定的依据。最后按字典序或求和目标排序。把自由变量按位权从小到大排列逐个点亮直到元素个数达到要求或自由变量耗尽。这一步其实就是在做贪心而贪心的正确性往往由“低位先用的代价不高于高位先用”来保证。5.3 无解判定什么时候必须停手有一个细节我是在写代码之后才想明白的无解条件不仅发生在“自由位完全不存在”也发生在“自由位存在但数量不够”。只要空闲位总数小于 n-1就无法构造出 n 个互不相同的合法元素。因为合法元素的个数恰好等于 1 空闲位数其中那个 1 就是地基本身 k。如果 K 在给定掩码范围内所有可能空闲位都被占满你还在继续循环那就该返回错误或特殊值。测试时我习惯用n100, k2^29-1这种极端值去压一下确保程序不会因为空转而死循环也不会因为构造出超范围值而出错。这个习惯让我在几道位运算题里都提前发现了 bug。5.4 从这题延伸出去还能怎么考想明白 3314 之后再去看同类的构造题会有一种“打怪升级”的顺畅感。一个常见的进阶方向是把 k 也变成一个数组每个查询单独给出 n_i 和 k_i要求返回所有答案。这种多查询版本本质上没有任何新东西只是把单次构造的复杂度控制住预处理或者原地构造即可属于“换汤不换药”。另一个进阶方向是把 AND 换成 XOR 或 OR。按位 OR 的情况下硬约束从“每个元素必须包含 k 的 1 位”变成“至少一个元素包含 k 的 1 位”自由变量更多构造策略也随之改变但分析问题的顺序还是那三步。我在复盘时顺手把 OR 版本也推了一遍体会是只要先把约束写成位运算表达式后面大概率都能迎刃而解。写在折腾完这题之后最后分享两个我实际踩过的坑。第一个是千万别小看“简单”标签尤其是位运算构造题它考的不是位运算技巧本身而是把自然语言约束翻译成位运算表达式的熟练度。我第一遍用回溯写写了半天删掉重来第二遍先把约束写在纸上一页纸都没写完就有了解法。第二个是掩码问题无论 C 还是 Python做位运算题时随手定义一个mask是好习惯它能挡住补码的符号位陷阱也能防止构造出超范围的数。这题之后的几周我每次做位运算题都会先把数据范围瞄一眼再定掩码手感稳了很多。建议你也试试这个流程。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
