C++ 最大化给定二进制数组中可以翻转的0的数量，以确保两个1之间至少有K个0

二进制数组是一种只包含0和1的特殊类型数组。在这个问题中，我们给定了一个二进制数组和一个整数K。我们的任务是计算在给定二进制数组中可以翻转的最大数量的0，使得两个1之间至少有K个0。

示例

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

Output 1: yes

解释

上述数组中的第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

解释

上述数组的第3个索引是唯一一个可以翻转的有效索引。

方法

我们已经看到了上面给定的数组和整数k的示例，现在让我们来看看这种方法的步骤：

这种方法的思路是计算两个1之间连续的0的个数，并检查是否适合在它们之间翻转一些0成为1。假设在两个1之间有X个0，根据观察可以计算出可以翻转的0的个数为(X-K) / (K+1)。因此，遍历数组并记录每对1之间有多少连续的0。然后，将可以翻转的0的个数添加到变量count中，这是需要的结果。

让我们逐步讨论这种方法：

• 首先，我们将创建一个函数’onesCount’，它将接受给定的数组’arr’和整数’K’作为参数，并将返回所需的整数’count’作为返回值。

• 创建变量count和lastIdx。

• 将变量count初始化为0，用于存储翻转的0的个数。

• 将变量lastIdx初始化为(-(K+1))，用于存储数组中值为1的最后一个索引。

• 使用for循环遍历数组，如果当前元素为1，则验证两个连续1之间是否有足够的0来在它们之间添加另一个1。最后，更新值为1的最后一个索引。

• 编写计算数组最后一个0部分的条件，并将其添加到变量count中。

• 最后，返回我们的最终答案count。

示例

下面是一个用于计算将0最大化翻转为1的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)，因为我们没有使用任何额外的空间。

结论

在本教程中，我们实现了一个程序，用于在给定的二进制数组中找到最大化翻转的0s，使得两个1之间至少有K个0s。通过计算两个1之间的连续0s的数量，并检查是否适合在它们之间翻转一些0s来解决此问题。时间复杂度为O(N)，空间复杂度为O(1)。其中N是字符串的大小。