计算从二进制字符串中选择三个具有不同相邻数字的索引的方法
在此问题中，我们将找到 3 个索引对的数量，以便任何相邻的索引在对中都不具有相同的值。
我们可以通过检查每对 3 个索引来获得输出，但这可能更耗时。解决问题的另一种方法是取当前索引，并从左侧和右侧取索引，这些索引不包含与当前索引值相似的值。这样，我们就可以计算每个索引可以形成的对的总数，并将它们相加以获得输出。
问题陈述 - 我们给出了一个 bin_str 二进制字符串，需要按递增顺序找到 3 个索引对的数量，使得相邻的索引不包含相同的值。
示例
输入
bin_str = "0101";
输出
2
解释
我们可以采用 {0, 1, 2} 和 {1, 2, 3} 索引对。所以，在010和101字符串中，任何两个相邻的字符都不相同。
输入
bin_str = "110001";
输出
6
解释
我们可以取 {0, 2, 5}、{0, 3, 5}、{0, 4, 5}、{1, 2, 5}、{1, 3, 5} 和 {1, 4, 5}。
输入
bin_str = "11111"
输出
0
解释
由于字符串的所有字符都相同，因此它不包含任何所需的索引对。
方法 1
在此方法中，我们将使用三个嵌套循环来查找 3 个索引对，以便相邻索引不包含相同的值。我们将检查每对是否符合问题陈述中给出的条件。
算法
步骤 1 - 用 0 初始化"ans"以存储所需对的数量。
步骤 2 - 使用第一个循环将字符串从第 0 个索引遍历到二进制字符串的长度 - 3 索引。
步骤 3 - 使用嵌套循环从 (p + 1) 索引遍历到二进制字符串的长度 - 2 索引。
步骤 4 - 使用另一个嵌套循环将字符串从 (q + 1) 索引遍历到二进制字符串的长度 - 1。
步骤 5 - 在嵌套循环中循环，如果 p 和 q 索引处的字符不相同，并且 q 和 r 索引处的字符不相同，则将"ans"值增加 1。
步骤 6 - 返回"ans"的值。
示例
#include <bits/stdc++.h>
using namespace std;
long long findIndexSelection(string bin_str) {
int bin_len = bin_str.size();
int ans = 0;
// 创建 3 个索引对
for (int p = 0; p < bin_len - 2; p++) {
for (int q = p + 1; q < bin_len - 1; q++) {
for (int r = q + 1; r < bin_len; r++) {
// 检查相邻字符是否相同
if (bin_str[p] != bin_str[q] && bin_str[q] != bin_str[r]) {
ans++;
}
}
}
}
// Final output
return ans;
}
int main() {
string bin_str = "0101";
cout << "选择索引以使两个相邻索引不具有相同字符的最大方法数为 " << findIndexSelection(bin_str) << endl;
return 0;
}
输出
选择索引以使两个相邻索引不具有相同字符的最大方法数为 2
时间复杂度 – O(N*N*N)，因为我们使用三个嵌套循环。
空间复杂度 – O(1)，因为我们不使用任何动态空间。
方法 2
如果我们想使用当前索引进行配对，我们需要取一个左索引和一个右索引，因为我们需要按升序选择索引。因此，我们可以从左侧和右侧获取所有不包含与当前索引相同字符的索引。
使用当前索引可以构建的对数如下所示。
对数 = (左侧索引具有不同值的数量) * (右侧索引具有不同值的数量)
之后，我们可以对使用每个索引可以构建的对数求和。
算法
步骤 1 - 初始化"cnt1"和"cnt0"变量以存储给定二进制字符串中零和一的数量。
步骤 2 - 遍历字符串并更新零和一的数量。
步骤3 - 用 0 初始化"ans"以存储总对数。
步骤 4 - 遍历字符串以查找总有效对数。
步骤 5 - 如果当前字符为"0"，则将 (ones* (cnt1 - ones)) 添加到"ans"。我们对左右 1 进行乘法，形成像 101 这样的对。此外，将"zeros"增加 1。
步骤 6 - 如果当前字符为"1"，则将 (zeros * (cnt0 - zeros)) 添加到"ans"。它形成一个像 010 这样的字符串。接下来，将"ones"增加 1。
步骤 7 - 返回"ans"值。
示例
#include <bits/stdc++.h>
using namespace std;
long long findIndexSelection(string bin_str) {
int bin_len = bin_str.size();
// 计算 0 和 1 的数量
int cnt0 = 0, cnt1 = 0;
// 将 0 和 1 存储到第 i 个索引
int zeros = 0, ones = 0;
// 遍历字符串以计算 0 和 1 的数量
for (int p = 0; p < bin_len; p++) {
if (bin_str[p] == '0') {
cnt0++;
} else {
cnt1++;
}
}
// 存储最大数量的对
long long ans = 0;
// 查找对
for (int p = 0; p < bin_len; p++) {
if (bin_str[p] == '0') {
// 获取可以用当前索引形成的对的数量
ans += (ones * (cnt1 - ones));
// Increase zeros
zeros++;
} else {
// 获取可以用当前索引形成的对的数量
ans += (zeros * (cnt0 - zeros));
ones++;
}
}
return ans;
}
int main() {
string bin_str = "1010";
cout << "选择索引以使两个相邻索引不具有相同字符的最大方法数为 " << findIndexSelection(bin_str) << endl;
return 0;
}
输出
选择索引以使两个相邻索引不具有相同字符的最大方法数为 2
时间复杂度 – 遍历字符串的复杂度为 O(N)。
空间复杂度 – O(1)，因为我们不使用任何动态空间。
我们学习了解决问题的简单方法和优化方法。第一种方法具有较高的时间复杂度，不能用于大量输入。第二种方法使用前缀 1 和 0 的概念来解决问题。
