class Solution {
public:
int goodBinaryStrings(int minLength, int maxLength, int oneGroup, int zeroGroup) {
}
};
2533. 好二进制字符串的数量
给你四个整数 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 <= 1051 <= oneGroup, zeroGroup <= maxLength原站题解
python3 解法, 执行用时: 336 ms, 内存消耗: 20.5 MB, 提交时间: 2023-10-22 00:04:49
class Solution(object):
def goodBinaryStrings(self, minLength, maxLength, oneGroup, zeroGroup):
dp = [0] * (maxLength + 1)
dp[0] = 1
mod = 10 ** 9 + 7
for i in range(1, maxLength + 1) :
if i - zeroGroup >= 0 :
dp[i] += dp[i - zeroGroup]
if i - oneGroup >= 0 :
dp[i] += dp[i - oneGroup]
dp[i] %= mod
return sum(dp[minLength : maxLength + 1]) % mod
def goodBinaryStrings2(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:
dp = [0 for _ in range(maxLength + 1)]
dp[0] = 1
for i in range(1,maxLength + 1):
dp[i] = dp[i] + (dp[i - oneGroup] if i - oneGroup >= 0 else 0)
dp[i] = dp[i] + (dp[i - zeroGroup] if i - zeroGroup >= 0 else 0)
dp[i] %= (10 ** 9 + 7)
return sum(dp[minLength:]) % (10 ** 9 + 7)
cpp 解法, 执行用时: 24 ms, 内存消耗: 12.4 MB, 提交时间: 2023-10-22 00:04:05
class Solution {
public:
int goodBinaryStrings(int minLength, int maxLength, int oneGroup, int zeroGroup) {
vector<int> dp(maxLength + 1, 0);
dp[0] = 1;
int mod = 1e9 + 7;
for (int i = 1; i <= maxLength; i++) {
if (i >= oneGroup) {
dp[i] += dp[i - oneGroup];
}
if (i >= zeroGroup) {
dp[i] += dp[i - zeroGroup];
}
dp[i] %= mod;
}
int ans = 0;
for (int i = minLength; i <= maxLength; i++) {
ans += dp[i];
ans %= mod;
}
return ans;
}
};
java 解法, 执行用时: 10 ms, 内存消耗: 41.5 MB, 提交时间: 2023-10-22 00:03:51
class Solution {
public int goodBinaryStrings(int minLength, int maxLength, int oneGroup, int zeroGroup) {
int MOD = 1000000007;
int[] dp = new int[maxLength+1];
dp[0] = 1;
int ans = 0;
for (int i = 1; i <= maxLength ; i++) {
if (i - oneGroup >= 0) dp[i] = (dp[i] + dp[i-oneGroup])%MOD;
if (i - zeroGroup >= 0) dp[i] = (dp[i] + dp[i-zeroGroup])%MOD;
if (i >= minLength) ans = (ans + dp[i]) % MOD;
}
return ans;
}
}