class Solution {
public:
long long fixedRatio(string s, int num1, int num2) {
}
};
2489. 固定比率的子字符串数
给定一个二进制字符串 s 和两个整数 num1 和 num2。num1 和 num2 为互质。
比率子串 是 s 的子串，其中子串中 0 的数量与 1 的数量之比正好是 num1 : num2。
num1 = 2 和 num2 = 3，那么 "01011" 和 "1110000111" 是比率子串，而 "11000" 不是。返回 s 的 非空 比率子串的个数。
注意:
gcd(x, y) == 1，则 x 和 y 为 互质，其中 gcd(x, y) 为 x 和 y 的最大公约数。
示例 1:
输入: s = "0110011", num1 = 1, num2 = 2 输出: 4 解释: 有 4 个非空的比率子串。 - 子字符串 s[0..2]: "0110011"。它包含一个 0 和两个 1。比例是 1:2。 - 子字符串 s[1..4]: "0110011"。它包含一个 0 和两个 1。比例是 1:2。 - 子字符串 s[4..6]: "0110011"。它包含一个 0 和两个 1。比例是 1:2。 - 子字符串 s[1..6]: "0110011"。它包含两个 0 和四个 1。比例是 2:4 == 1:2。 它可以显示没有更多的比率子串。
示例 2:
输入: s = "10101", num1 = 3, num2 = 1 输出: 0 解释: s 没有比率子串，返回 0。
提示:
1 <= s.length <= 1051 <= num1, num2 <= s.lengthnum1 和 num2 互质。原站题解
cpp 解法, 执行用时: 236 ms, 内存消耗: 85 MB, 提交时间: 2023-10-21 23:15:50
class Solution {
public:
long long fixedRatio(string s, int num1, int num2) {
long long ans = 0, a = 0, b = 0;
unordered_map<long long, long long> mp;
mp[0]++;
for(auto c : s) {
if(c == '0') a++;
else b++;
ans += mp[a * num2 - b * num1]++;
}
return ans;
}
};
python3 解法, 执行用时: 316 ms, 内存消耗: 29.4 MB, 提交时间: 2023-10-21 23:15:34
class Solution:
def fixedRatio(self, s: str, num1: int, num2: int) -> int:
dc = defaultdict(int)
dc[0], one, zero, res = 1, 0, 0, 0
for i in s:
if i == '1': one += 1
else: zero += 1
tep = num1 * one - num2 * zero
res += dc[tep]
dc[tep] += 1
return res
def fixedRatio2(self, s: str, num1: int, num2: int) -> int:
pre = defaultdict(int)
pre[0] = 1
one,zero = 0,0
ans = 0
for c in s:
if c == '1':
one += 1
else:
zero += 1
ans += pre[num1 * one - num2 * zero]
pre[num1 * one - num2 * zero] += 1
return ans