数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究最大化给定二进制数组中需要翻转的 0 的数量，使得两个 1 之间至少有 K 个 0
二进制数组是一种特殊的数组，只包含数字 0 和 1。在这个问题中，我们给定一个二进制数组和整数 K。我们的任务是计算在给定二进制数组中可以翻转为 1 的最大 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 个零。因此，结果数组为 {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 之间的连续零的个数，并检查是否适合在它们之间将一些零翻转为一。假设两个 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 的数量的 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 是字符串的大小。
95 次浏览
