在進行所有可能的K次操作後，給定二進位字串中設定位元計數的平均值

在這個問題中，我們需要對給定的字串進行所有選取的 K 次運算後，求設定位元數的平均值。

可以使用暴力方法來解決問題，但我們將使用機率原理來克服暴力方法的時間複雜度。

問題陳述 - 我們給定一個整數 N，包含 K 個正整數的陣列 arr[]，以及一個長度為 N 的二進位字串，其中只包含設定位。我們需要找出在執行所有可能的 K 次操作後，設定位元計數的平均值。在第 i 次操作中，我們可以翻轉給定字串中的任何 arr[i] 位元。

範例

輸入– N = 2, arr[] = {1, 2}

輸出– 1

說明 – 初始二進位字串為 11。

• 第一步，我們可以翻轉第一個字符，字串將是01。

• 在第二次操作中，我們需要翻轉任兩個位元。所以字串將變成10。

• 第二個選擇可以從翻轉第一步中的第二個字元開始，字串將為 10。

• 在目前操作的第二步驟中，我們需要翻轉任意2個位，字串可以是01。

所以，我們有兩個選擇，最終的字串可以是01或10。

總選擇 = 2，最終字串中的總設定位 = 2，ans = 2/2 = 1。

輸入– N = 3, arr[] = {2, 2}

輸出– 1.6667

Explanation – 我們有一個初始字串是111。

• 在第一個操作中，我們可以翻轉任意 2 個字元。因此，字串可以是 001、100、010。

• 在第二個操作中，我們可以翻轉第一個操作所得到的結果字串中的2個位元。

• 當我們翻轉001的任兩個位元時，我們得到111、010和100。

• 當我們翻轉 100 的任 2 位元時，我們可以得到 010、111 和 001。

• 當我們翻轉010的任兩個位元時，我們可以得到100、001和111。

所以，在上一次操作中，我們得到了總共9個不同的字串。

9個字串中的總設定位數=15，總運算次數=9，答案=15/9=1.6667

方法一

在這裡，我們將使用機率原理來解決這個問題。假設在執行了 i-1 次操作後，設定位的平均值為 p，非設定位的平均值為 q。我們需要計算第 i 次操作中設定位和非設定位的平均值。

所以，p的更新值可以是p 新設定位的平均數 - 新關閉位的平均數。

演算法

• 將P初始化為N，因為我們原本有N個設定位，將Q初始化為0，因為我們原本有0個設定位。

• 遍歷操作數組。

• 使用 P 和 Q 值初始化 prev_p 和 prev_q。

• 使用prev_p - prev_p * arr[i] / N prev_q * arr[i] / N更新P值，這將平均將反轉的位元加到設定的位元中，並將平均設定的位反轉為未設定的位元

• 更新 Q 值。

• 傳回 P 值。

Example

的中文翻譯為：

範例

#include <bits/stdc++.h>
using namespace std;

double getAverageBits(int len, int K, int array[]) {
   // to store the average '1's in the binary string
   double P = len;
   // to store the average '0's in the binary string
   double Q = 0;
   // Traverse the array array[]
   for (int i = 0; i < K; i++) {
      // Initialize the prev_p and prev_q with P and Q, which we got from the previous iteration
      double prev_p = P, prev_q = Q;
      // Update the average '1's
      P = prev_p - prev_p * array[i] / len + prev_q * array[i] / len;
      // Update the average '0's
      Q = prev_q - prev_q * array[i] / len + prev_p * array[i] / len;
   }
   return P;
}
int main() {
   int N = 2;
   int array[] = {1};
   int K = sizeof(array) / sizeof(array[0]);
   cout << "The average number of set bits after performing the operations is " << getAverageBits(N, K, array);
   return 0;
}

輸出

The average number of set bits after performing the operations is 1

時間複雜度 - O(K)，其中K是陣列的長度。

空間複雜度 - O(1)，因為我們沒有使用任何額外的空間。

在本教程中，我們學習了在執行 K 操作的所有可能選擇後找到平均設定位。在單選中，我們需要執行數組中給出的所有操作。

以上是在進行所有可能的K次操作後，給定二進位字串中設定位元計數的平均值的詳細內容。更多資訊請關注PHP中文網其他相關文章！