查詢具有給定範圍內的最大元素和的 N 長度二進位制字串

---

我們將得到一個數組，該陣列將包含表示範圍的數對，其值範圍為 0（包含）到 N（不包含）。這裡，N 是我們必須返回作為答案的二進位制字串的大小。對於所有給定的範圍，我們必須最大化零和一的頻率乘積之和。我們將實現兩種方法，一種是透過查詢所有字串的樸素方法，另一種是高效的解決方案。

示例

輸入 1

給定陣列：{{1,3}, {2,4}, {2,5}}

字串長度：6

輸出 − 101010（可能還有其他輸出，但每個輸出都將給出最大結果 8）。

解釋 − 對於範圍 1 到 3，我們有 1 的頻率為 1，0 的頻率為 2；對於範圍 2 到 4，1 的頻率為 2，0 的頻率為 1；對於範圍 2 到 5，1 和 0 的頻率都為 2。這給了我們 (1*2) + (2*1) + (2*2) 的和，即 8，這是最大值。

輸入 2

給定陣列：{{1,2}}

字串長度：3

輸出 101（最大輸出為 1，可以從 001、010、101、110 中得到）。

解釋 − 所有可能的字串是 000、001、010、100、011、101、110、111。可以達到的最大和是 1。

樸素方法

我們已經看到了示例，現在讓我們來看主要方法。

在這種方法中，我們將生成所有可能的二進位制字串，並在得到它們之後，檢查每個字串哪個產生最佳的和。我們將使用遞迴來生成所有字串，然後對於每個字串，我們將計算頻率乘積的和，然後與最大值進行比較。

示例

#include <iostream>
using namespace std;
int maxSum = 0;
string ansStr = "";
// function to generate all the strings 
void backtracking(string& str, int idx, int arr[][2], int m, int n){
   if(idx == n){
      int curSum = 0;
      for(int i=0;i<m;i++){
         int freqZ = 0, freqO = 0;
         for(int j=arr[i][0]; j <= arr[i][1]; j++){
            if(str[j] == '1'){
               freqO++;
            }
            else{
               freqZ++;
            }
         }
         curSum += freqO*freqZ;
      }
      if(maxSum < curSum){
         maxSum = curSum;
         ansStr = str;
      }
      return;
   }    
   // adding zero at the current index and calling function 
   str.push_back('0');
   backtracking(str,idx+1,arr,m,n);    
   // updating 0 to 1 and calling function 
   str[idx] = '1';
   backtracking(str,idx+1,arr,m,n);    
   str.pop_back(); // poping the last element
}
string findString(int arr[][2], int m, int n){
   // updating the value of maxSum and ansStr 
   ansStr = "";
   maxSum = 0;
   string temp = "";
   // calling to the function 
   backtracking(temp,0,arr,m,n);    
   return ansStr;
}
int main(){
   int arr[][2] = {{1,3}, {2,4}, {2,5}}; // given array 
   int m = 3; // size of array 
   int n = 6; // length of the string     
   // calling the function 
   string str = findString(arr,m,n);    
   cout<<"The string which will produce the maximum result is "<<str<<endl;
   return 0;
}

輸出

The string which will produce the maximum result is 000101

時間和空間複雜度

上述程式碼的時間複雜度非常低效，為 O(2^N*M*N)，其中 N 是字串的大小，M 是給定陣列的大小。

上述程式碼的空間複雜度為 O(N)，其中 N 是字串的大小。

高效方法

在之前的方法中，我們建立每個字串，然後對其進行測試，這需要 O(N) 的空間複雜度和 O(2^N*N) 的時間複雜度，這根本沒有效率。為了簡化這個過程，我們可以透過觀察來思考。

為了獲得最大乘積，我們可以考慮減少 1 和 0 的頻率之間的絕對差值。為此，將元素放在交替的位置是最好的方法，這將使時間複雜度線性化。讓我們看看程式碼 −

示例

#include <iostream>
using namespace std;
string findString(int n){
   // making the alternative ones and zeros string 
   string ans = "";    
   // adding total of n elements in the string 
   for(int i=0; i<n; i++){
      if(i & 1){
         // if the current index is odd add zero to the string 
         ans += '0';
      }
      else{
         // if the current index is even add one to the string 
         ans += '1';
      }
   }
   return ans;
}
int main(){
   int arr[][2] = {{1,3}, {2,4}, {2,5}}; // given array 
   int m = 3; // size of array 
   int n = 6; // length of the string     
   // calling the function 
   string str = findString(n);    
   cout<<"The string which will produce the maximum result is "<<str<<endl;
   return 0;
}

輸出

The string which will produce the maximum result is 101010

時間和空間複雜度

上述程式碼的時間複雜度為 O(N)，其中 N 是字串的長度，這是線性時間複雜度。

上述方法的空間複雜度為 O(1)，因為我們在這裡沒有使用任何額外的空間。

結論

在本教程中，我們實現了兩種方法來建立一個字串，該字串將為陣列提供的給定範圍記憶體在的 1 和 0 的頻率產生最大和。我們使用回溯法實現了第一種方法，但這需要指數級的時間複雜度。之後，我們透過觀察實現了一種高效的方法。