给你四个整数 minLenght
、maxLength
、oneGroup
和 zeroGroup
。
好 二进制字符串满足下述条件:
- 字符串的长度在
[minLength, maxLength]
之间。 - 每块连续
1
的个数是oneGroup
的整数倍- 例如在二进制字符串
00110111100
中,每块连续1
的个数分别是[2,4]
。
- 例如在二进制字符串
- 每块连续
0
的个数是zeroGroup
的整数倍- 例如在二进制字符串
00110111100
中,每块连续0
的个数分别是[2,1,2]
。
- 例如在二进制字符串
请返回好二进制字符串的个数。答案可能很大,请返回对 109 + 7
取余后的结果。
注意:0
可以被认为是所有数字的倍数。
示例 1:
输入:minLength = 2, maxLength = 3, oneGroup = 1, zeroGroup = 2 输出:5 解释:在本示例中有 5 个好二进制字符串: "00", "11", "001", "100", 和 "111" 。 可以证明只有 5 个好二进制字符串满足所有的条件。
示例 2:
输入:minLength = 4, maxLength = 4, oneGroup = 4, zeroGroup = 3 输出:1 解释:在本示例中有 1 个好二进制字符串: "1111" 。 可以证明只有 1 个好字符串满足所有的条件。
提示:
1 <= minLength <= maxLength <= 105
1 <= oneGroup, zeroGroup <= maxLength
方法一:动态规划
我们定义
最终答案为
时间复杂度
class Solution:
def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:
mod = 10**9 + 7
f = [1] + [0] * maxLength
for i in range(1, len(f)):
if i - oneGroup >= 0:
f[i] += f[i - oneGroup]
if i - zeroGroup >= 0:
f[i] += f[i - zeroGroup]
f[i] %= mod
return sum(f[minLength:]) % mod
class Solution {
public int goodBinaryStrings(int minLength, int maxLength, int oneGroup, int zeroGroup) {
final int mod = (int) 1e9 + 7;
int[] f = new int[maxLength + 1];
f[0] = 1;
for (int i = 1; i <= maxLength; ++i) {
if (i - oneGroup >= 0) {
f[i] = (f[i] + f[i - oneGroup]) % mod;
}
if (i - zeroGroup >= 0) {
f[i] = (f[i] + f[i - zeroGroup]) % mod;
}
}
int ans = 0;
for (int i = minLength; i <= maxLength; ++i) {
ans = (ans + f[i]) % mod;
}
return ans;
}
}
class Solution {
public:
int goodBinaryStrings(int minLength, int maxLength, int oneGroup, int zeroGroup) {
const int mod = 1e9 + 7;
int f[maxLength + 1];
memset(f, 0, sizeof f);
f[0] = 1;
for (int i = 1; i <= maxLength; ++i) {
if (i - oneGroup >= 0) {
f[i] = (f[i] + f[i - oneGroup]) % mod;
}
if (i - zeroGroup >= 0) {
f[i] = (f[i] + f[i - zeroGroup]) % mod;
}
}
int ans = 0;
for (int i = minLength; i <= maxLength; ++i) {
ans = (ans + f[i]) % mod;
}
return ans;
}
};
func goodBinaryStrings(minLength int, maxLength int, oneGroup int, zeroGroup int) (ans int) {
const mod int = 1e9 + 7
f := make([]int, maxLength+1)
f[0] = 1
for i := 1; i <= maxLength; i++ {
if i-oneGroup >= 0 {
f[i] += f[i-oneGroup]
}
if i-zeroGroup >= 0 {
f[i] += f[i-zeroGroup]
}
f[i] %= mod
}
for _, v := range f[minLength:] {
ans = (ans + v) % mod
}
return
}