資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告