数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究计算X:Y比例的0和1子字符串
在这个问题中，我们将统计给定二进制字符串的子字符串，这些子字符串包含“0”和“1”字符的数量，且比例为X:Y。
朴素的方法是找到给定二进制字符串的所有子字符串，统计“0”和“1”的数量，并检查这些数量是否为X:Y比例。有效的方法使用前缀和技术来解决问题。
问题陈述 - 我们给定一个长度为bin_len的二进制字符串。我们需要统计具有0和1的数量之比为X:Y的子字符串。
示例
输入
bin_str = "00111001100"; X = 2; Y = 3;
输出
5
解释 - 具有“1”和“0”之比为2:3的子字符串为00111、01110、10011、11001和11100。
输入
bin_str = "11111"; X = 2; Y = 3;
输出
0
解释 - 二进制字符串仅包含“1”。因此，无法找到包含“0”和“1”之比为2:3的子字符串。
输入
bin_str = "00100"; X = 2; Y = 1;
输出
3
解释 - 我们可以取001、010和100子字符串。
方法1
在这种方法中，我们将使用两个嵌套循环来找到二进制字符串的所有子字符串。之后，我们将统计二进制字符串中“1”和“0”的数量。
如果以下条件对任何子字符串都成立，则我们可以将该子字符串考虑在答案中。
zeroCnt * Y == oneCnt * X
算法
步骤1 - 将“ans”初始化为0，以存储子字符串的数量。
步骤2 - 使用for循环遍历二进制字符串。另外，使用另一个循环获取从当前索引开始的每个子字符串。
步骤3 - 使用substr()方法获取特定长度的子字符串。
步骤4 - 将“zeroCnt”和“oneCnt”初始化为0，以存储子字符串中“1”和“0”的数量。
步骤5 - 使用第三个嵌套循环来统计“1”和“0”。如果当前字符为“1”，则递增“oneCnt”。否则，递增“ZeroCnt”。
步骤6 - 在第二个嵌套循环中，如果zeroCnt * Y == oneCnt * X为真，则将“ans”的值递增1。
步骤7 - 最后，从函数返回“ans”值。
示例
#include <bits/stdc++.h>
using namespace std;
int subStrCnt(string &bin_str, int X, int Y) {
int ans = 0;
// Get all substrings of the binary string
for (int p = 0; p < bin_str.length(); p++) {
for (int q = 1; q <= bin_str.length() - p; q++) {
string sub_str = bin_str.substr(p, q);
// Counting the number of zeros and ones in the substring
int zeroCnt = 0, oneCnt = 0;
for (int p = 0; p < sub_str.length(); p++) {
if (sub_str[p] == '0')
zeroCnt++;
else
oneCnt++;
}
// Checking whether the count of zeros and ones in the X:Y ratio
if (zeroCnt * Y == oneCnt * X)
ans++;
}
}
return ans;
}
int main() {
string bin_str = "00111001100";
int X = 2;
int Y = 3;
cout << "The total substrings having 0's and 1's in the ratio X:Y is " << subStrCnt(bin_str, X, Y);
return 0;
}
输出
The total substrings having 0's and 1's in the ratio X:Y is 5
时间复杂度 - O(N*N*N)，其中O(N*N)用于获取所有子字符串，O(N)用于统计子字符串中的“1”和“0”。
空间复杂度 - O(N)用于存储子字符串。
方法2
在这种方法中，我们将“0”视为-Y，“1”视为-X。我们将根据“0”和“1”的数量找到-Y和X的和。如果和等于0，我们可以说我们找到了有效的子字符串。
此外，我们将使用map数据结构来存储前缀和。每当我们第二次找到任何前缀和值时，我们就可以获取和为0的索引之间的子字符串。
例如，二进制字符串为“00111001100”。我们在第0个和第5个索引处找到了相同的前缀和。因此，我们可以获取从第1个索引到第5个索引的子字符串。
算法
步骤1 - 初始化“binary”列表，以将二进制字符串转换为-Y和X格式。
步骤2 - 遍历字符串。如果当前字符为“0”，则在列表中插入“-Y”。否则，在列表中插入“X”。
步骤3 - 定义“pref”map以存储前缀和作为键，以及其值的出现次数。
步骤4 - 另外，初始化“ans”以存储子字符串的数量，并将“sum”初始化为0以存储前缀和。
步骤5 - 开始遍历字符串。将binary[p]添加到sum中。
步骤6 - 如果“sum”为0，则将“ans”递增1。
步骤7 - 如果sum键存在于map中，则将其值添加到“ans”中。
步骤8 - 将pref[sum]递增1。
步骤9 - 返回“ans”值。
示例
#include <bits/stdc++.h>
using namespace std;
int subStrCnt(string &bin_str, int X, int Y) {
vector<int> binary;
for (auto ch : bin_str) {
if (ch == '0') {
// Change '0' to -Y
binary.push_back(-Y);
} else {
// Change '1' to X
binary.push_back(X);
}
}
// To store prefix sum
unordered_map<int, int> pref;
int ans = 0;
int sum = 0;
// Traverse string
for (int p = 0; p < binary.size(); p++) {
// Add a current element to sum
sum += binary[p];
// When aX - bY = 0, we found the substring
if (sum == 0)
ans += 1;
// When prefix sum exists, we add the value to ans
if (pref.find(sum) != pref.end())
ans += pref[sum];
// Increment the count of prefix sum
pref[sum] += 1;
}
return ans;
}
int main() {
string bin_str = "00111001100";
int X = 2;
int Y = 3;
cout << "The total substrings having 0's and 1's in the ratio X:Y is " << subStrCnt(bin_str, X, Y);
return 0;
}
输出
The total substrings having 0's and 1's in the ratio X:Y is 5
时间复杂度 - O(N)用于查找前缀和。
空间复杂度 - O(N)用于在map中存储前缀和。
优化后的方法有效地解决了问题，只需花费O(N)时间。但是，对于大型二进制字符串，它可能需要更多的空间。程序员可以尝试解决问题，以找到在二进制字符串中具有相同数量的“0”和“1”的子字符串。
470 次查看
