2026-09-14：成本限制的有效二进制字符串。用go语言，给定两个整数 n 和 k。考虑所有长度为 n、只包含字符 0 和 1 的串。对于一个这样的

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 中所有置位比特的下标之和。比如 n=3 时：

• • x = 1（bit0 置位）↔ "100" → cost = 0

• • x = 2（bit1 置位）↔ "010" → cost = 1

• • x = 5（bit0、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 位和第 i+1 位同时为 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[:1< 遍历cost的前 2^n 项。这里有两个巧妙之处：

• • 切片cost[:1< 天然把枚举范围限制在 n 位以内，不需要额外判断位数；

• • range 同时给出下标 x 和值 c = cost[x]，一次遍历就把"掩码"和"它的 cost"都拿到手，省掉一次数组访问。

因为全局表是按 12 位建的，而实际只用到低 n 位，高位的 0 不影响相邻判定，也不影响 cost（高位若为 0 就不贡献下标和），所以直接截断前缀是完全安全的。

第 4 步：筛选

对每个 x 只做一次比较：if c > k { continue }。

• • 若 x 有相邻 1，c 是 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 的完整走查

二进制(bit2…bit0)

字符串

相邻?

cost

≤1?

0

000

"000"

0

1

001

"100"

0

2

010

"010"

1

3

011

"110"

MaxInt

4

100

"001"

2

5

101

"101"

2

6

110

"011"

MaxInt

7

111

"111"

MaxInt

得到 ["000", "100", "010"]，与题目答案集合一致（顺序不同但题目允许）。

复杂度分析

设 n 为串长，C 为最终输出的可接受串个数（C ≤ 2^n，受"不相邻"约束实际最多为第 n+2 个斐波那契数，n=12 时 ≤ 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 的结果被后续写入覆盖成同一个串。

package main

 import (
    "fmt"
    "math"
    "math/bits"
)

 var cost [1 << 12]int

 func init() {
    for x := 1; x < len(cost); x++ {
        if x&(x>>1) > 0 { // 有两个连续的 1
            cost[x] = math.MaxInt // 不合法
        } else {
            // 去掉 x 中的一个比特位（最低位还是最高位都可以），计算 DP
            cost[x] = cost[x&(x-1)] + bits.TrailingZeros(uint(x))
        }
    }
}

 func generateValidStrings(n, k int) (ans []string) {
    s := make([]byte, n)
    for x, c := range cost[:1< 
 
 
 
          
 if 
  c > k { 
 
 
              
 continue 
 
 
         } 
 
 
          
 for 
  j :=  
 range 
  s {  
 // 注意左边是低位，右边是高位 
 
 
             s[j] =  
 '0' 
  +  
 byte 
 (x& 
 1 
 ) 
 
 
             x >>=  
 1 
 
 
         } 
 
 
         ans =  
 append 
 (ans,  
 string 
 (s)) 
 
 
     } 
 
 
      
 return 
 
 
 } 
 
 
 
 
 func main() 
  { 
 
 
     n :=  
 3 
 
 
     k :=  
 1 
 
 
     result := generateValidStrings(n, k) 
 
 
     fmt.Println(result) 
 
 
 } 
 
 
 

Python完整代码如下：

# -*-coding:utf-8-*-

 import math

 MAX = 1 << 12
cost = [0] * MAX

 for x in range(1, MAX):
    if x & (x >> 1):
        cost[x] = math.inf
    else:
        cost[x] = cost[x & (x - 1)] + ((x & -x).bit_length() - 1)

 def generate_valid_strings(n, k):
    lavomirex = (n, k)
    ans = []
    s = [''] * n

     for x in range(1 << n):
        c = cost[x]
        if c > k:
            continue

         y = x
        for j in range(n):
            s[j] = '1' if (y & 1) else '0'
            y >>= 1

         ans.append(''.join(s))

     return ans

 def main():
    n = 3
    k = 1
    result = generate_valid_strings(n, k)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

#include  

#include  

#include  

#include  


 using namespace std;

 const int MAX_N = 12;
int cost[1 << MAX_N];

 void init() {
    for (int x = 1; x < (1 << MAX_N); ++x) {
        if ((x & (x >> 1)) > 0) {  // 有两个连续的 1
            cost[x] = INT_MAX;     // 不合法
        } else {
            // 去掉 x 的最低位 1，并累加该位的位置
            // __builtin_ctz(x)：x 的二进制末尾有多少个 0，即最低位 1 的下标
            cost[x] = cost[x & (x - 1)] + __builtin_ctz(x);
        }
    }
}

 vector 
 
   
 generateValidStrings(int n, int k) {
    vector 
 
 ans; 
 

     for (int x = 0; x < (1 << n); ++x) {
        if (cost[x] > k) {
            continue;
        }

         string s(n, '0');

         // 左边对应低位，右边对应高位
        int value = x;
        for (int j = 0; j < n; ++j) {
            s[j] = char('0' + (value & 1));
            value >>= 1;
        }

         ans.push_back(s);
    }

     return ans;
}

 int main() {
    init();

     int n = 3;
    int k = 1;

     vector 
 
 result =  
 generateValidStrings(n, k);

     cout << "[";
    for (int i = 0; i < (int)result.size(); ++i) {
        if (i > 0) {
            cout << " ";
        }
        cout << result[i];
    }
    cout << "]" << endl;

     return 0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。