給定範圍內，在兩個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)。