最大化給定二進制數組中要翻轉的0的數量，使得兩個1之間至少有K個0

二進位數組是一種特殊類型的數組，只包含數字0和1。在這個問題中，我們給了一個二進位數組和一個整數K。我們的任務是計算在給定的二進制數組中，可以將最大數量的0翻轉為1，使得兩個1之間至少有K個0。

範例範例

Input 1: arr[] = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 },  K = 2

Output 1: yes

Explanation

的中文翻譯為：

解釋

上述數組中的第3個和第6個索引是唯一有效的索引，可以翻轉，以確保兩個1之間至少有2個0。因此，結果數組是{1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0}

Input 2: arr[] = {0, 1, 0, 0, 0, 1}, k = 1

Output 2: 1

Explanation

的中文翻譯為：

解釋

以上數組的第3個索引是唯一有效的翻轉索引。

Approach

我們已經看到了上面給出的陣列和整數k的範例，讓我們繼續討論方法−

這種方法的想法是計算兩個1之間連續的0的個數，並檢查是否適合在它們之間翻轉一些0為1。假設兩個1之間有X個0。根據觀察，可以翻轉的0的個數為(X-K) / (K 1)。因此，遍歷數組並記錄每對1之間有多少個連續的0。然後，將可以翻轉的0的個數加到變數count中，這是所需的回應。

讓我們逐步討論下面的方法-

• 首先，我們將建立一個名為'onesCount'的函數，該函數將以給定的陣列'arr'和整數'K'作為參數，並將所需的整數'count'作為返回值返回。

• 建立變數 count 和 lastIdx。

• 使用0初始化變數count，用來儲存fillip 0s的數數。

• 使用(-(K 1))初始化變數lastIdx，以儲存陣列中值為1的最後一個索引。

• 使用for迴圈遍歷數組，檢查目前元素是否為1，然後驗證兩個連續的1之間是否有足夠的0來增加另一個1。最後，更新最後一個1的索引值。

• 寫出計算數組中最後一段0的條件，並將其加入變數count。

• 最後，返回我們的最終答案數。

Example

的中文翻譯為：

範例

下面是一個用於計算最大化0s轉換為1s的C 程序，以確保在兩個1之間至少存在k個0。

#include <bits/stdc++.h>
using namespace std; 
// Function to find the count of the maximum number of 0s to be filliped 
int onesCount(int arr[], int n, int k){
   int count = 0; // Stores the count of 1's 
   int lastIdx = -(k + 1); // Stores the last index of value 1 
   
   // Traverse the array using for loop
   for (int i = 0; i < n; i++) { 
      // If the current element is 1
      if (arr[i] == 1) { 
      
         // Verify whether there are enough 0s between two consecutive 1s to add another 1 in between them.
         if (i - lastIdx - 1 >= 2 * (k - 1)) {
            count += (i - lastIdx - 1 - k) / (k + 1);
         } 
         lastIdx = i; // Update the last index of the value 1 of the array
      }
   } 
   
   // condition to include the last section of 0s in the array
   count += (n - lastIdx - 1) / (k + 1);
 
   // Return the answer
   return count;
} 
int main(){
   int arr[] = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }; // given array
   int N = sizeof(arr) / sizeof(arr[0]); //getting size of an array
   int K = 2; //given integer 
   
   // Call the function
   int result = onesCount(arr, N, K);    
   cout<< "The count of Maximum filliped of 0's is "<< result ;
   return 0;
}

輸出

The Count of Maximum filliped of 0's is 2

時間與空間複雜度

#以上程式碼的時間複雜度為O(N)，因為我們只遍歷了陣列。其中N是給定數組的大小。

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

結論

在本教程中，我們實作了一個程序，用於找到在給定的二進制數組中要翻轉的最大0的數量，以便在兩個1之間至少有K個0。透過計算兩個1之間的連續零的數量，並檢查是否適合在它們之間翻轉一些零來解決這個問題。時間複雜度為O(N)，空間複雜度為O(1)。其中N是字串的大小。

以上是最大化給定二進制數組中要翻轉的0的數量，使得兩個1之間至少有K個0的詳細內容。更多資訊請關注PHP中文網其他相關文章！