数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究统计可以通过替换“01”或“10”为1或0得到长度为1的子字符串的数量
在这个问题中，我们将统计可以由替换‘10’和‘01’子字符串为‘1’或‘0’字符得到的长度为1的子字符串的数量。
当任何二进制字符串包含相同数量的‘0’和‘1’时，我们总是可以通过执行替换操作将其长度变为1。因此，问题可以通过查找具有相同数量的‘0’和‘1’的子字符串来解决。
问题陈述 − 我们给定一个名为 bin_str 的二进制字符串，长度为 bin_len。我们需要计算可以通过将‘10’或‘01’更改为‘1’或‘0’来得到长度为1的子字符串的总数。
示例
输入
bin_str = "01010";
输出
6
解释 − 子字符串为 01、01、0101、10、10 和 1010。
输入
bin_str = "01";
输出
1
解释 − 我们可以将 01 替换为 ‘1’ 或 ‘0’ 以使其长度为 1。
输入
bin_str = "00000";
输出
0
解释 − 不存在任何子字符串，经过替换后可以使其长度为 1。
方法 1
该问题可以通过统计具有相同数量的‘1’和‘0’的子字符串的数量来解决。我们将找到字符串的所有子字符串，并统计字符串中的‘1’和‘0’。如果‘1’和‘0’的计数相同，我们将把‘ans’加 1。
算法
步骤 1 − 初始化 ‘cnt’ 为 0，以存储有效子字符串的数量。
步骤 2 − 同时，初始化 ‘cnt0’ 和 ‘cnt1’ 为 0，以存储‘1’和‘0’的计数。
步骤 3 − 开始遍历二进制字符串。
步骤 4 − 使用嵌套循环从索引 p 遍历到最后一个索引。
步骤 5 − 如果当前字符是‘0’，则将 ‘cnt0’ 加 1。否则，将 ‘cnt1’ 加 1。
步骤 6 − 如果 cnt0 和 cnt1 相等，则将 ‘cnt’ 值加 1。
步骤 7 − 返回 ‘cnt’ 值。
示例
#include <bits/stdc++.h>
using namespace std;
int totalSubstrs(string &bin_str, int &bin_len) {
// To store a number of valid substrings
int cnt = 0;
// Couting number of substrings having equal 1's and 0's
for (int p = 0; p < bin_len; p++) {
// To store count of 1's and 0's in substring
int cnt0 = 0, cnt1 = 0;
for (int q = p; q < bin_len; q++) {
if (bin_str[q] == '0') {
cnt0++;
} else {
cnt1++;
}
// When the substring has an equal number of 0's and 1's
if (cnt0 == cnt1) {
cnt++;
}
}
}
return cnt;
}
int main() {
string bin_str = "01010";
int bin_len = bin_str.length();
cout << "The number of substrings according to the given problem statement is " << totalSubstrs(bin_str, bin_len);
return 0;
}
输出
The number of substrings according to the given problem statement is 6
时间复杂度 − O(N*N)，遍历二进制字符串的所有子字符串。
空间复杂度 − O(1)，因为我们没有使用任何额外的空间。
方法 2
在这种方法中，我们将使用前缀和技术来统计具有相同数量的‘1’和‘0’的子字符串的数量。我们将跟踪每个索引处‘1’和‘0’计数的差值。
如果任何两个索引处‘1’和‘0’计数的差值相同，我们可以取这两个索引之间的子字符串。
算法
步骤 1 − 初始化 ‘cnt’ 和 ‘diff’ 为 0，以存储有效子字符串的数量和‘1’和‘0’计数的差值。
步骤 2 − 同时，初始化 ‘prefixSum’ 列表为 0，以存储差值。
步骤 3 − 开始遍历字符串。如果当前字符是‘0’，则将 ‘diff’ 值加 1。否则，将 ‘diff’ 值减 1。
步骤 4 − 如果 ‘diff’ 为 ‘0’，则将 ‘cnt’ 加 1。
步骤 5 − 如果 ‘prefixSum’ 数组中 ‘diff’ 索引处的值为大于 0，则将 prefixSum[diff] 加到 ‘cnt’ 中。
步骤 6 − 将 ‘prefixSum’ 列表中 ‘diff’ 索引处的值加 1。
步骤 7 − 返回 ‘cnt’ 值。
示例
#include <iostream>
#include <vector>
using namespace std;
int totalSubstrs(string bin_str, int bin_len) {
int cnt = 0;
int diff = 0; // To store the difference of count of 1's and 0's
vector<int> prefixSum(bin_len, 0);
for (char ch : bin_str) {
// For the '0' character
if (ch == '0') {
diff++;
} else if (ch == '1') {
// For '1' character
diff--;
}
if (diff == 0) {
// When the number of '0' and '1' are equal
cnt++;
}
if (prefixSum[diff] > 0) {
cnt += prefixSum[diff];
}
prefixSum[diff]++;
}
return cnt;
}
int main() {
string bin_str = "01010";
int bin_len = bin_str.length();
cout << "The number of substrings according to the given problem statement is - " << totalSubstrs(bin_str, bin_len);
return 0;
}
输出
The number of substrings according to the given problem statement is 6
时间复杂度 − O(N)，获取‘1’和‘0’计数差值的前缀和。
空间复杂度 − O(N)，在 prefixSum 列表中存储差值。
该问题类似于查找具有相同数量的‘1’和‘0’的子字符串。我们还使用了前缀和技术通过在 prefix 数组中存储‘1’和‘0’计数的差值来解决问题。第二种方法是时间优化的，但对于较大的二进制字符串，它可能会占用更多内存。
72 次浏览
