给定一个整数n，求出所有长度为n的由1和0组成的二进制串中，包含连续的3个1的个数。

我们可以使用动态规划来解决该问题。定义状态$f[i][0/1]$表示前$i$位二进制串中，以$0$或$1$结尾的连续$1$的个数。显然，$f[1][0]=f[1][1]=0$。

对于第$i$位，如果加上一个$0$，那么$f[i][0]=f[i-1][0]+1$，因为加上一个$0$不会改变以$0$结尾的连续$1$的个数，但是以$1$结尾的连续$1$的个数会被打断。

如果加上一个$1$，那么$f[i][1]=f[i-1][1]+1$，因为加上一个$1$不会改变以$1$结尾的连续$1$的个数，但是以$0$结尾的连续$1$的个数会被打断。此外，如果$f[i-1][1]\geq 2$，那么以第$i$位为结尾的二进制串中包含连续的$3$个$1$，因此需要将$f[i][1]$加上$f[i-1][1]$。

最终答案就是所有长度为$n$的二进制串中，以$1$结尾且包含连续的$3$个$1$的个数之和，即$\sum_{i=1}^{n}f[i][1]$。

时间复杂度：$O(n)$。

参考代码：

相关问题

给定整数n，生成所有n长的二进制集

可以使用递归的方式来生成所有长度为n的二进制集。

首先考虑当n=1的情况，只有两个二进制数：0和1。

当n>1时，可以将问题拆分成两个子问题：

1. 生成所有长度为n-1的二进制集。
2. 在每个生成的长度为n-1的二进制数前面加上0和1，得到所有长度为n的二进制数。

下面是使用Python实现这个算法的代码：

def generate_binary_sets(n):
    # base case
    if n == 1:
        return ["0", "1"]
    # recursive case
    prev_sets = generate_binary_sets(n-1)
    new_sets = []
    for s in prev_sets:
        new_sets.append("0" + s)
        new_sets.append("1" + s)
    return new_sets

# example usage
print(generate_binary_sets(3)) # output: ['000', '001', '010', '011', '100', '101', '110', '111']

这个算法的时间复杂度是O(2^n)，因为需要生成长度为n的所有二进制数。

给定一个长度为 n 的整数数组 a，试判断能否从数组中选取 k 个数，使得选取的数字异或之和为 0

这是一个经典的异或和问题，可以用位运算的性质解决。

异或和的性质是，对于任意两个数 a 和 b，它们的异或和值为 c，那么这两个数可以用二进制表示为 a = c ^ b。换句话说，如果我们已知一组数的异或和值为 c，那么我们可以通过任意选取其中一个数并计算该数与 c 的异或值来得到另一个数，反复操作直到得到所有数。

因此，我们可以先计算出数组 a 的异或和 s，然后从 s 的二进制表示中任意选择 k 个位置，将这些位置上的二进制位设为 1，在得到的二进制表示中计算得到的数即为所选的 k 个数的异或和。如果这个异或和值为 0，则说明可以选出这 k 个数，否则无解。

判断异或和是否为 0 可以通过 s == 0 来实现。时间复杂度为 O(n)，空间复杂度为 O(1)。