给定范围内，在两个1之间0的最大数量（针对Q个查询）

---

二进制字符串只包含0和1两种字符。给定一个二进制字符串和一个包含若干对的数组。每对定义一个范围，在这个范围内，我们需要返回两个1之间0的最大数量。我们将实现两种方法，一种是朴素方法，另一种是高效方法。

让我们通过例子来理解

输入

字符串 str = ‘1011010110’

数组 Q[][] = {{0,2}, {2,5}, {0,9}}

输出: 1 1 3

解释 − 对于范围0到2，在第0位和第2位之间只有一个0。对于范围2到5，在第2位和第5位（或第3位和第5位）之间也只有一个0。

对于最后一个查询，在第0位和第7位、第8位之间有三个0。

朴素方法

在这种方法中，我们将遍历每个查询，并计算从范围内遇到的第一个1到最后一个1之间的0的个数。如果任一侧的1不存在，则答案为零。

我们将遍历每个查询的字符串，并检查给定范围内0的数量。

我们将使用一个标志来标记范围内是否存在至少一个1。如果存在1，则设置标志并从那里开始计数0，如果再次出现字符1，我们将0的个数存储在标志变量中，因为它将始终是该范围内的最大值。

此外，为了标记0的数量，我们将维护一个变量。

让我们看看代码 −

示例

#include <bits/stdc++.h>
using namespace std;
// function to find the zeroes in the range 
int zeroesInRange(int l, int r, string str){    
   // checking for the current range 
   int flag = -1; // flag to indicate the whether one is present on first side or not  
   int count = 0;
   for(int i = l; i <= r; i++){
      if(str[i] == '1'){
         if(flag == -1){
            flag = 0;
            count = 0;
         }
         else{
            flag = count;
         }
      }
      else{
         count++;
      }
   }    
   if(flag == -1){
      return 0;
   }
   else{
      return flag;
   }
}
int main(){
   string str = "1010110110";
   int Q[][2] = {{0,2}, {2,5}, {0,9}};
   int m = 3; // size of the queries     
   // traversing over the array 
   for(int i=0; i<m; i++){
      // calling the function 
      cout<<zeroesInRange(Q[i][0], Q[i][1], str)<<" ";
   }
   cout<<endl;    
   return 0;
}

输出

1 1 3 

时间和空间复杂度

上述代码的时间复杂度为O(Q*N)，其中Q是查询数组的大小，N是字符串的大小。

上述代码的空间复杂度为O(1)，因为我们在这里没有使用任何额外的空间。

高效方法

在先前的方法中，我们针对每个查询遍历数组，使得时间复杂度是非线性的。我们将使用前缀数组的概念，并首先存储结果，以便对每个查询获得O(1)而不是O(N)的答案。

我们将存储当前索引左侧和右侧存在的1的索引，以及0的数量的前缀和。

对于当前范围，我们将找到左侧范围元素的右侧1和右侧范围元素的最右侧1，然后我们将找到它们之间0的数量。让我们看看代码 −

示例

#include <bits/stdc++.h>
using namespace std;
// function to solve the queries 
void findQueries(int Q[][2], string str, int m){
   int n = str.length(); // getting the length of the string     
   // defining the vectors to store the find the one present 
   // nearest on the both left and the right side 
   // also, to store the prefix zeroes 
   vector<int> leftOne(n), rightOne(n), preZero(n);    
   int lastOne = -1; // variable to store the last one     
   // traversing over the array to get the left One 
   for(int i=0; i<n; i++){
      if(str[i] == '1'){
         lastOne = i;   
      }
      leftOne[i] = lastOne;
   }    
   lastOne = n;
   // traversing over the array to get the right One 
   for(int i=n-1; i>=0 ;i--){
      if(str[i] == '1'){
         lastOne = i;   
      }
      rightOne[i] = lastOne;
   }    
   // traversing over the array to get the prefix value of zeros 
   for(int i=0; i<n; i++){
      if(str[i] == '0'){
         preZero[i]++;
      }
      if(i != 0){
         preZero[i] += preZero[i-1];
      }
   }    
   // traversing over the queries array 
   for(int i=0; i<m; i++){
      int l = rightOne[Q[i][0]];
      int r = leftOne[Q[i][1]];        
      if(l >= r){
         cout<<0<<" ";
      }
      else{
         if(l == 0){
            cout<<preZero[r]<<" ";
         }
         else{
            cout<<preZero[r]-preZero[l]<<" ";
         }
      }
   }
   cout<<endl;
}
int main(){
   string str = "1010110110";
   int Q[][2] = {{0,2}, {2,5}, {0,9}};
   int m = 3; // size of the queries 
   // calling to the function 
   findQueries(Q, str, m);    
   return 0;
}

输出

1 1 3 

时间和空间复杂度

上述代码的时间复杂度为O(max(Q,N))，其中Q是查询的数量，N是字符串的长度。

上述代码的空间复杂度为O(N)，因为我们将元素存储在向量中。

结论

在本教程中，我们实现了一个代码来查找查询的解决方案，以查找给定二进制字符串中两个1之间存在的0的数量。我们实现了两个代码，一个是时间复杂度为O(N*Q)，空间复杂度为常数；另一个是时间复杂度为O(N)，空间复杂度为O(N)。