ในปัญหานี้ เราได้รับอาร์เรย์ 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: บล็อกไม่มี 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
