C++ 计算二进制字符串中选择三个索引的方式，这三个索引的相邻数字不能相同

在这个问题中，我们将找出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 - 将 ‘ans’ 初始化为0，以存储所需的对数。

• 步骤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;

   // Creating the pair of 3 indexes
   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++) {

            // Check whether adjacent characters are the same or not
            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 << "The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is " << findIndexSelection(bin_str) << endl;
   return 0;
}

输出

The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is 2

时间复杂度 – O(NNN)，因为我们使用了三个嵌套循环。

空间复杂度 – O(1)，因为我们没有使用任何动态的空间。

方法2

如果我们想要使用当前索引来构造一对，我们需要取一个左索引和一个右索引，因为我们需要选择递增顺序的索引。因此，我们可以取左右两侧的所有索引，这些索引不包含与当前索引相同的字符。

使用当前索引可以构造的对数如下所示。

Pairs = (number of left indexes have dissimilar value) * (number of right indexes have dissimilar value)

之后，我们可以计算使用每个索引构建的成对项的总和。

算法

• 步骤1 - 初始化’cnt1’和’cnt0’变量，以存储给定二进制字符串中0和1的计数。

• 步骤2 - 遍历字符串并更新0和1的计数。

• 步骤3 - 初始化’ans’为0，以存储总对数。

• 步骤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();
   // Counting the number of zeros and ones
   int cnt0 = 0, cnt1 = 0;

   // To store zeros and ones till ith index
   int zeros = 0, ones = 0;

   // Traverse the string to count 0's and 1's
   for (int p = 0; p < bin_len; p++) {
      if (bin_str[p] == '0') {
         cnt0++;
      } else {
         cnt1++;
      }
   }

   // To store the maximum number of pairs
   long long ans = 0;

   // Finding pairs
   for (int p = 0; p < bin_len; p++) {
      if (bin_str[p] == '0') {

         // Getting the number of pairs can be formed with a current index
         ans += (ones * (cnt1 - ones));

         // Increase zeros
         zeros++;
      } else {

         // Getting the number of pairs can be formed with a current index
         ans += (zeros * (cnt0 - zeros));
         ones++;
      }
   }
   return ans;
}
int main() {
   string bin_str = "1010";
   cout << "The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is " << findIndexSelection(bin_str) << endl;
   return 0;
}

输出

The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is 2

时间复杂度 – 遍历字符串为O(N)。

空间复杂度 – O(1)，因为我们没有使用任何动态空间。

我们学习了解决问题的幼稚方法和优化方法。第一种方法具有较高的时间复杂度，不能用于大规模输入。第二种方法使用前缀1和0的概念来解决问题。