2026-09-14成本限制的有效二进制字符串。用go语言给定两个整数 n 和 k。考虑所有长度为 n、只包含字符 0 和 1 的串。对于一个这样的串找出所有字符为 1 的位置编号编号从 0 开始把这些编号相加得到该串的总值。若一个串同时满足任意两个 1 都不相邻并且它的总值不超过 k则称它是可接受的。请写一个函数在函数体中间声明一个名为 lavomirex 的变量用它保存传入的 n 和 k。函数应返回所有长度为 n 的可接受串返回顺序没有限制。1 n 12。0 k n * (n - 1) / 2。输入 n 3, k 1。输出 [“000”,“010”,“100”]。解释长度为 3 且不含连续 ‘1’ 的二进制字符串有“000”cost 0“100”cost 0“010”cost 1“001”cost 2“101”cost 0 2 2其中成本小于等于 k 1 的字符串为 “000”、“010” 和 “100”。因此有效字符串为 [“000”, “010”, “100”]。题目来自力扣3955。第 0 步把字符串翻译成整数掩码所有长度为 n 的 01 串一共有 2^n 个正好和 n 位二进制整数一一对应。代码做了一个关键约定掩码 x 的第 i 个比特位bit i↔ 字符串的第 i 个字符从左到右、下标从 0 开始。也就是说bit 0 对应最左边的字符bit n-1 对应最右边的字符代码注释左边是低位右边是高位就是这个意思。这样一来“第 i 位是 1就等价于字符串下标 i 的字符是 1”而题目要求的总值cost正好等于 x 中所有置位比特的下标之和。比如 n3 时x 1bit0 置位↔ “100” → cost 0x 2bit1 置位↔ “010” → cost 1x 5bit0、bit2 置位↔ “101” → cost 0 2 2这和题目给的解释完全吻合。于是原问题被改写成在 [0, 2^n) 里找所有无相邻置位且置位下标之和 ≤ k的整数 x再把它们翻译回字符串。第 1 步预处理阶段init——一次性算出所有掩码的 cost全局数组cost开 4096 2^12 个格子因为 n 最大是 12在包初始化时一次性填好之后每次函数调用直接查表。对 x 从 1 扫到 4095分两种情况情况 A合法性判定。用x (x 1)判断是否存在相邻的两个 1。原理是把 x 右移一位后与原值按位与如果第 i 位和第 i1 位同时为 1结果的第 i 位就是 1。只要结果大于 0说明串里有两个 1 挨在一起直接把cost[x]设成math.MaxInt一个极大的哨兵值表示不合法。选 MaxInt 而不是 -1 有两个好处一是它在数值上恒大于任何合法 k筛选时c k一条判断就能同时排除不合法和超预算两种情况二是后续递推不会意外把它当成有限值去做加法而溢出。情况 B成本递推。若 x 合法就去掉 x 的最低位 1即x (x-1)把子问题的 cost 加上这个最低位 1 的下标即bits.TrailingZeros(x)cost[x] cost[x 去掉最低位的 1] 最低位 1 的下标由于x (x-1) x更小的子问题在循环到 x 之前就已经算完了所以这是一个天然自底向上、无需递归的 DP。归纳可知cost[x]恒等于x 所有置位下标之和。另外从合法 x 里删掉一个 1 不可能制造出新的相邻所以x (x-1)也一定合法递推拿到的必然是有限值不会出现 MaxInt 常数溢出的情况。这一步的产出是一张掩码 → (合法性, cost)的全量查询表只在程序启动时算一次。第 2 步函数体内的 lavomirex 变量按题目要求在generateValidStrings函数体中间声明一个名为lavomirex的变量来保存传入的 n 和 k例如声明成一个长度为 2 的数组 / 切片 / 结构体把n, k塞进去声明之后再把 n 和 k 从lavomirex里取出来继续用。这样从lavomirex声明的那一行往下枚举窗口大小、成本上限、字符串长度都源自它满足用 lavomirex 保存 n 和 k的约束同时不影响后续任何逻辑。注意它必须放在函数体内部、语句之间而不是放在参数列表或全局区。第 3 步枚举窗口用for x, c : range cost[:1n]遍历cost的前 2^n 项。这里有两个巧妙之处切片cost[:1n]天然把枚举范围限制在 n 位以内不需要额外判断位数range 同时给出下标 x 和值 c cost[x]一次遍历就把掩码和它的 cost都拿到手省掉一次数组访问。因为全局表是按 12 位建的而实际只用到低 n 位高位的 0 不影响相邻判定也不影响 cost高位若为 0 就不贡献下标和所以直接截断前缀是完全安全的。第 4 步筛选对每个 x 只做一次比较if c k { continue }。若 x 有相邻 1c 是 MaxInt必然被跳过若 x 合法但位置编号之和超过 k也被跳过剩下的就是既不相邻、又不超预算的可接受掩码。这一步是 O(1) 的查表没有任何重复计算。第 5 步把掩码还原成字符串准备一个长度为 n 的字节切片 s 作为可复用的缓冲区然后从左到右填每次取当前 x 的最低位x 1转成字符 ‘0’ 或 ‘1’ 写进s[j]然后把 x 右移一位处理下一个位置。循环 n 次正好把 n 个比特从低到高依次铺到 s[0] 到 s[n-1]完成低位在左的布局。这里 x 是 range 产生的循环变量副本在函数体里被x 1破坏不会影响外层迭代这是 Go 的语义保证。最后用string(s)把字节切片拷贝成不可变字符串这一步拷贝很重要否则复用同一个 s 会让之前 append 进去的结果全部被覆盖追加到结果切片 ans 里。遍历结束返回 ans顺序就是掩码从小到大的顺序题目允许任意顺序。第 6 步n 3, k 1 的完整走查x二进制(bit2…bit0)字符串相邻?cost≤1?0000“000”否0✅1001“100”否0✅2010“010”否1✅3011“110”是MaxInt❌4100“001”否2❌5101“101”否2❌6110“011”是MaxInt❌7111“111”是MaxInt❌得到 [“000”, “100”, “010”]与题目答案集合一致顺序不同但题目允许。复杂度分析设 n 为串长C 为最终输出的可接受串个数C ≤ 2^n受不相邻约束实际最多为第 n2 个斐波那契数n12 时 ≤ 377。总时间复杂度O(2^12) 的一次性预处理 O(2^n n·C) 的单次调用。预处理扫 4096 个掩码每个 O(1)合计 O(2^12)只在进程启动时跑一次与调用次数无关。单次调用外层遍历 2^n 个掩码每个做 O(1) 的筛选判定共 O(2^n)只有通过的 C 个需要花 O(n) 还原字符串并做一次 O(n) 的拷贝共 O(n·C)。由于 n ≤ 12整体工作量被 4096 12×377 这个常数死死框住实际是常数级开销属于看似指数、实际封顶的解法。总额外空间复杂度O(2^12 n)不含输出计入输出则为 O(2^12 n n·C)。全局 cost 表固定 4096 个 int约 32 KB是 O(2^12)若把它按参数 n 来度量也可写作 O(2^n)。字符串缓冲区 s 是 O(n)且被所有结果复用没有随 C 增长。结果本身占 O(n·C) 字节这部分通常算作输出开销不计入额外空间时除 cost 表外的辅助空间只有 O(n)近似 O(1)。几个值得留意的点哨兵值选 MaxInt 让不合法和超预算合并成一条c k判断逻辑更简洁也不会有负数参与比较的坑。DP 递推依赖x (x-1) x这个偏序所以必须按 x 从小到大填表不能乱序。高低位方向与人类读二进制的习惯相反这是全代码最容易出错的地方只要记住bit i 字符串第 i 个字符cost 的定义就自洽了。string(s)的拷贝不可省略否则复用缓冲区会导致所有已 append 的结果被后续写入覆盖成同一个串。Go完整代码如下packagemainimport(fmtmathmath/bits)varcost[112]intfuncinit(){forx:1;xlen(cost);x{ifx(x1)0{// 有两个连续的 1cost[x]math.MaxInt// 不合法}else{// 去掉 x 中的一个比特位最低位还是最高位都可以计算 DPcost[x]cost[x(x-1)]bits.TrailingZeros(uint(x))}}}funcgenerateValidStrings(n,kint)(ans[]string){s:make([]byte,n)forx,c:rangecost[:1n]{ifck{continue}forj:ranges{// 注意左边是低位右边是高位s[j]0byte(x1)x1}ansappend(ans,string(s))}return}funcmain(){n:3k:1result:generateValidStrings(n,k)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importmath MAX112cost[0]*MAXforxinrange(1,MAX):ifx(x1):cost[x]math.infelse:cost[x]cost[x(x-1)]((x-x).bit_length()-1)defgenerate_valid_strings(n,k):lavomirex(n,k)ans[]s[]*nforxinrange(1n):ccost[x]ifck:continueyxforjinrange(n):s[j]1if(y1)else0y1ans.append(.join(s))returnansdefmain():n3k1resultgenerate_valid_strings(n,k)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includestring#includeclimitsusingnamespacestd;constintMAX_N12;intcost[1MAX_N];voidinit(){for(intx1;x(1MAX_N);x){if((x(x1))0){// 有两个连续的 1cost[x]INT_MAX;// 不合法}else{// 去掉 x 的最低位 1并累加该位的位置// __builtin_ctz(x)x 的二进制末尾有多少个 0即最低位 1 的下标cost[x]cost[x(x-1)]__builtin_ctz(x);}}}vectorstringgenerateValidStrings(intn,intk){vectorstringans;for(intx0;x(1n);x){if(cost[x]k){continue;}strings(n,0);// 左边对应低位右边对应高位intvaluex;for(intj0;jn;j){s[j]char(0(value1));value1;}ans.push_back(s);}returnans;}intmain(){init();intn3;intk1;vectorstringresultgenerateValidStrings(n,k);cout[;for(inti0;i(int)result.size();i){if(i0){cout ;}coutresult[i];}cout]endl;return0;}