数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究给定二进制字符串中唯一索引 10 或 01 子字符串的最大数量
在这个问题中，我们将计算使用给定二进制字符串可以形成的 10 和 01 对的最大数量。
为了解决这个问题，我们可以检查使用相邻字符可以形成多少个 10 和 01 对，并且两个对不能共享任何字符。
问题陈述
我们给定一个二进制字符串 bin_str。我们需要计算仅使用相邻字符可以形成的 10 和 01 对的最大数量。此外，我们可以将一个字符用于任何单个对。两个对不能共享同一个字符。
示例
Input – bin_str = "1100101" Output – 3
解释
我们可以在第 1 个（基于 0 的索引）索引处形成一个“10”对，并在第 3 个和第 5 个索引处形成 01 对。
Input – bin_str = "111111"; Output – 0
解释
该字符串包含全部“1”。因此，我们无法形成任何 10 或 01 对。
Input – bin_str = "101"; Output – 1
解释
我们不能在两个对中共享同一个字符。因此，我们只能形成 10 或 01 对。
方法 1
在这种方法中，我们将使用布尔变量来跟踪前一个字符是否与前一个对一起使用。因此，我们可以形成唯一的 10 和 01 对，而不会共享相邻的字符。
此外，我们将计算不同相邻字符的数量以获得 01 和 10 对的数量。
算法
步骤 1 - 初始化“cnt”为 0 以存储对的数量，并将“isPrev”初始化为 true 以跟踪前一个字符是否可用以形成对。
步骤 2 - 从第 1 个索引开始遍历二进制字符串。
步骤 3 - 如果索引 p 和 p – 1 处的字符不同且“isPrev”为 true，则将“cnt”值加 1，因为我们找到了 01 或 10 的对。此外，将“isPrev”更新为 false，因为当前字符不可用于与下一个字符形成对。
步骤 4 - 否则，将“isPrev”更新为 true。
步骤 5 - 最后，返回“cnt”值。
示例
#include <bits/stdc++.h>
using namespace std;
int countPairs(string bin_str) {
// To store the count of pairs
int cnt = 0;
// To track whether we can use the previous character in the pair
bool isPrev = true;
// Iterate the string
for (int p = 1; p < bin_str.size(); p++) {
// Check whether adjacent characters are different and previous characters available to make a pair
if (bin_str[p] != bin_str[p - 1] && isPrev) {
// Current character gets used
isPrev = false;
cnt++;
} else {
// Make the current character free for the next pair
isPrev = true;
}
}
return cnt;
}
int main() {
string bin_str = "1100101";
cout << "The maximum number of 01 and 10 cnt is " << countPairs(bin_str);
return 0;
}
输出
The maximum number of 01 and 10 cnt is 3
时间复杂度 - 遍历字符串需要 O(N)。
空间复杂度 - O(1)
我们已经计算了可以使用二进制字符串的相邻字符形成的 10 和 01 对的数量。程序员可能会计算在给定二进制字符串中可以形成的 100 和 001 对的最大数量。在这种情况下，我们需要使用整型变量来检查前两个字符是否可用，而不是使用单个布尔值。
95 次查看
