二进制数组是一种特殊类型的数组，只包含数字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 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 = 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 2
登录后复制
时间和空间复杂度
以上代码的时间复杂度为O(N)，因为我们只遍历了数组。其中N是给定数组的大小。
以上代码的空间复杂度为O(1)，因为我们没有使用任何额外的空间。
结论
在本教程中，我们实现了一个程序，用于找到在给定的二进制数组中要翻转的最大0的数量，以便在两个1之间至少有K个0。通过计算两个1之间的连续零的数量，并检查是否适合在它们之间翻转一些零来解决这个问题。时间复杂度为O(N)，空间复杂度为O(1)。其中N是字符串的大小。
以上就是最大化给定二进制数组中要翻转的0的数量，使得两个1之间至少有K个0的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2586781.html
