資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學給定範圍內，在兩個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)。
瀏覽量 208
