在这个问题中,我们给了一个数组arr,该数组arr由n个元素组成,它们分别为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: Block没有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