数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学在C++中查找需要翻转的零，以最大化连续1的个数
在本教程中，我们将找到需要翻转的零的个数，以在数组中获得最大数量的连续1。
我们将使用滑动窗口方法来解决这个问题。让我们看看解决问题的步骤。
初始化数组和要翻转的最大零的个数。
初始化窗口的起始索引、结束索引以及长度。
存储最大连续1子数组的长度和起始索引。
迭代数组，直到结束索引超过数组长度。
如果零的个数小于最大零的个数，则如果当前值为零，则递增结束索引和零的个数。
如果零的个数大于最大零的个数，则如果当前值为零，则递增起始索引并减少零的个数。
如果当前窗口长度大于之前的窗口长度，则更新最大窗口。
迭代数组并使用窗口起始索引打印零的索引。
示例
让我们看看代码。
#include <bits/stdc++.h>
using namespace std;
void zeroesIndexes(int arr[], int maxZeroes, int n) {
int start = 0, end = 0;
int zeroesCount = 0;
int bestWindowCount = 0, bestWindowStartIndex = 0;
while (end < n) {
if (zeroesCount <= maxZeroes) {
if (arr[end] == 0) {
zeroesCount++;
}
end++;
}
if (zeroesCount > maxZeroes) {
if (arr[start] == 0) {
zeroesCount--;
}
start++;
}
if ((end - start > bestWindowCount) && (zeroesCount <= maxZeroes)) {
bestWindowCount = end - start;
bestWindowStartIndex = start;
}
}
cout << "The indexes are ";
for (int i = 0; i < bestWindowCount; ++i) {
if(arr[bestWindowStartIndex + i] == 0)
cout << bestWindowStartIndex + i << " ";
}
}
int main() {
int arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1};
int maxZeroes= 2;
zeroesIndexes(arr, maxZeroes, 10);
return 0;
}输出
如果运行上面的代码，则会得到以下结果。
The indexes are 5 7
结论
如果您在本教程中遇到任何问题，请在评论区提出。
更新于：2020-12-29
73 次查看
广告