数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 最少次数的填充相邻元素来填充数组为 1
在这个问题中，我们得到一个包含 n 个元素的数组 arr，这些元素要么是 0 要么是 1。我们的任务是使用最少的填充相邻元素的迭代次数来填充数组为 1。
让我们举个例子来理解这个问题，
输入：arr[] = {0, 1, 1, 0, 0, 1}
输出：1
解决方案方法 -
为了解决这个问题，我们需要知道这样一个事实：如果某个位置存在 1，它可以将两个相邻的 0 转换为 1。
如果， arr[i] 是 1。
那么， arr[i-1] 和 arr[i+1] 将被转换为 1。
使用此方法，可以使用以下情况之一找到解决方案 -
情况 1：块在块的开头和结尾处有 1。其余所有值均为 0。计算零的数量。
迭代次数 = zeroCount / 2，如果计数为偶数
迭代次数 = (zeroCount -1)/2，如果计数为奇数
情况 2：块在块的开头或结尾处只有一个 1，其余所有值均为 0。
迭代次数 = zeroCount
情况 3：块中没有 1。打印 -1 表示无法填充 1。
程序说明我们解决方案的工作原理，
示例
#include<iostream>
using namespace std;
int countIterationFill1(int arr[], int n) {
bool oneFound = false;
int iterationCount = 0;
for (int i=0; i<n; ) {
if (arr[i] == 1)
oneFound = true;
while (i<n && arr[i]==1)
i++;
int zeroCount = 0;
while (i<n && arr[i]==0) {
zeroCount++;
i++;
}
if (oneFound == false && i == n)
return -1;
int itrCount;
if (i < n && oneFound == true) {
if (zeroCount & 1 == 0)
itrCount = zeroCount/2;
else
itrCount = (zeroCount+1)/2;
zeroCount = 0;
}
else{
itrCount = zeroCount;
zeroCount = 0;
}
iterationCount = max(iterationCount, itrCount);
}
return iterationCount;
}
int main() {
int arr[] = {0, 1, 1, 0, 0, 1, 0, 0, 0, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The number of iterations to fill 1's is "<<countIterationFill1(arr, n);
return 0;
}输出 -
The number of iterations to fill 1's is 2
更新于： 2021年1月22日
141 次查看
广告