字符串问题---0左边必有1的二进制字符串数量

科技前沿 • 2025-02-08 23:57 • 阅读 68

大家好，我是讯享网，很高兴认识大家。

【问题】

　　给定一个整数N，求由‘0’字符和‘1’字符组成的长度为N的所有字符串中，满足‘0’字符的左边必有‘1’字符的字符串数量。

【举例】

　　N = 1。只由‘0’和‘1’组成，长度为1的所有字符串：“0”、“1”。只有字符串“1”满足要求，返回1。
　　N = 2。只由‘0’和‘1’组成，长度为2的所有字符串：“00”，“01”，“10”，“11”。只有字符串“10”，“11”满足，返回2。
　　N = 3。只由‘0’和‘1’组成，长度为3的所有字符串：“000”，“001”，“010”，“011”，“100”，“101”,“110”，“111”。只有字符串“101”，“110”，“111”满足，返回3。

【基本思路】

　　本题可以从字符串的末尾倒着遍历来考虑。举例来说，设str 的长度N，f(n)表示有n个字符的情况下，满足条件的字符串个数。首先需要明白，如果要满足“0”左边必定有“1”，那么字符串的开头一定不能为“0”。

str[N-1…N-1]，只包含一个字符，满足要求的只有“1”，所以f(1) = 1。

讯享网
str[N-2…N-1]，包含两个字符，满足要求的只有“10”，“11”，所以f(2) = 2。
str[N-3…N-2]，包含三个字符，应该满足str[N-3]必须是“1”，此时，str[N-2]可以是“1”也可以是“0”。如果是“1”，那么可以组成个数就是f(2)；如果是“0”，那么可以组成的个数就是f(1)，所以f(3) = f(2) + f(1)。
str[N-4…N-1]，包含四个字符，应该满足str[N-4]必须是“1”，此时，str[N-3]可以是“1”也可以是“0”。如果是“1”，那么可以组成个数就是f(3)；如果是“0”，那么可以组成的个数就是f(2)，所以f(4) = f(3) + f(2)。
同理，str[0…N-1]，包含N个字符，应该满足str[0]必须是“1”，此时，str[1]可以是“1”也可以是“0”。如果是“1”，那么可以组成个数就是f(N-1)；如果是“0”，那么可以组成的个数就是f(N-2)，所以f(n) = f(n-1) + f(n-2)。

可以发现这就是一个典型的斐波那契问题，只不过斐波那契的初始项是1,1，该问题的初始项是1,2，接下来的求解步骤就斐波那契问题如出一辙。可以用递归，动态规划以及矩阵乘法的方式解决。

斐波那契的递归、动态规划和矩阵乘法的求解方法可以参考我的另一篇博客。点次链接

下面是使用python3.5实现的代码。

#0左边必定有1的二进制字符串数量 def getNum1(n): if n < 1: return 0 if n == 1 or n == 2: return n return getNum1(n-1) + getNum1(n-2) def getNum2(n): if n < 1: return 0 if n == 1 or n == 2: return n pre = 1 cur = 2 for i in range(3, n+1): pre, cur = cur, pre+cur return cur def getNum3(n): def matrixPower(m, p): res = [[0 if i != j else 1 for i in range(len(m[0]))] for j in range(len(m))] tmp = m while p > 0: if p & 1 != 0: res = muliMatrix(res, tmp) tmp = muliMatrix(tmp, tmp) p >>= 1 return res def muliMatrix(m1, m2): res = [[0 for i in range(len(m2[0]))] for j in range(len(m1))] for i in range(len(m1)): for j in range(len(m2[0])): for k in range(len(m1[0])): res[i][j] += m1[i][k] * m2[k][j] return res if n < 1: return 0 if n == 1 or n == 2: return n base = [[1,1], [1,0]] res = matrixPower(base, n-2) return 2 * res[0][0] + res[1][0]

讯享网

字符串问题---0左边必有1的二进制字符串数量

相关推荐