查找要翻转的零，以便在C ++中最大化连续1的数目

  • Z时代
  • 2024-01-10
  • 分类：综合

在本教程中，我们将找到需要翻转的零计数，以获取数组中连续的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 << "索引是 ";
   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;
}
输出结果

如果运行上面的代码，则将得到以下结果。

索引是 5 7

结论

以上是 查找要翻转的零，以便在C ++中最大化连续1的数目 的全部内容， 来源链接： utcz.com/z/330632.html

回到顶部