Maksimumkan bilangan 0s untuk membalikkan dalam tatasusunan binari yang diberikan supaya terdapat sekurang-kurangnya K 0s antara dua 1s

Tatasusunan binari ialah jenis tatasusunan khas yang hanya mengandungi nombor 0 dan 1. Dalam masalah ini, kita diberi tatasusunan binari dan integer K. Tugas kami adalah untuk mengira bilangan maksimum 0 yang boleh diubah menjadi 1 dalam tatasusunan binari yang diberikan supaya terdapat sekurang-kurangnya K 0 antara dua 1.

Contoh Contoh

Input 1: arr[] = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 },  K = 2

Output 1: yes

Penjelasan

Penjelasan

Indeks ke-3 dan ke-6 dalam tatasusunan di atas ialah satu-satunya indeks yang sah dan boleh dibalikkan untuk memastikan terdapat sekurang-kurangnya 2 0s antara dua 1s. Oleh itu, tatasusunan yang terhasil ialah {1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0}

Input 2: arr[] = {0, 1, 0, 0, 0, 1}, k = 1

Output 2: 1

Penjelasan

Penjelasan

Indeks ke-3 tatasusunan di atas ialah satu-satunya indeks terbalik yang sah.

Pendekatan

Kita telah melihat contoh yang diberikan di atas dengan tatasusunan dan integer k, mari kita beralih kepada kaedah −

Idea kaedah ini adalah untuk mengira bilangan 0 berturut-turut antara dua 1 dan semak sama ada ia sesuai untuk membalikkan beberapa 0 hingga 1 di antara mereka. Katakan terdapat sifar X antara dua sifar. Mengikut pemerhatian, bilangan 0s yang boleh diterbalikkan ialah (X-K) / (K+1). Jadi, gelung melalui tatasusunan dan rekodkan bilangan 0 berturut-turut yang terdapat di antara setiap pasangan 1. Kemudian, tambahkan nombor 0s yang boleh diterbalikkan kepada kiraan pembolehubah, iaitu tindak balas yang diingini.

Jom bincang kaedah di bawah langkah demi langkah-

• Pertama, kami akan mencipta fungsi yang dipanggil 'onesCount' yang akan mengambil tatasusunan 'arr' dan integer 'K' sebagai parameter dan mengembalikan 'count' integer yang diperlukan sebagai nilai pulangan.

• Buat kiraan pembolehubah dan lastIdx.

• Mulakan kiraan pembolehubah dengan 0 untuk menyimpan kiraan fillip 0s.

• Mulakan pembolehubah lastIdx menggunakan (-(K+1)) untuk menyimpan indeks terakhir dalam tatasusunan dengan nilai 1.

• Gunakan gelung for untuk lelaran melalui tatasusunan, semak sama ada elemen semasa ialah 1, dan kemudian sahkan jika terdapat cukup 0s antara dua 1 berturut-turut untuk menambah 1 lagi. Akhir sekali, kemas kini nilai indeks 1 terakhir.

• Tulis syarat yang mengira segmen terakhir 0 dalam tatasusunan dan tambahkannya pada kiraan pembolehubah.

• Akhirnya, kiraan jawapan akhir kami dikembalikan.

Contoh

Contoh

Di bawah ialah program C++ untuk mengira penukaran maksimum 0s kepada 1s untuk memastikan terdapat sekurang-kurangnya k 0s antara dua 1s.

#include <bits/stdc++.h>
using namespace std; 
// Function to find the count of the maximum number of 0s to be filliped 
int onesCount(int arr[], int n, int k){
   int count = 0; // Stores the count of 1's 
   int lastIdx = -(k + 1); // Stores the last index of value 1 
   
   // Traverse the array using for loop
   for (int i = 0; i < n; i++) { 
      // If the current element is 1
      if (arr[i] == 1) { 
      
         // Verify whether there are enough 0s between two consecutive 1s to add another 1 in between them.
         if (i - lastIdx - 1 >= 2 * (k - 1)) {
            count += (i - lastIdx - 1 - k) / (k + 1);
         } 
         lastIdx = i; // Update the last index of the value 1 of the array
      }
   } 
   
   // condition to include the last section of 0s in the array
   count += (n - lastIdx - 1) / (k + 1);
 
   // Return the answer
   return count;
} 
int main(){
   int arr[] = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }; // given array
   int N = sizeof(arr) / sizeof(arr[0]); //getting size of an array
   int K = 2; //given integer 
   
   // Call the function
   int result = onesCount(arr, N, K);    
   cout<< "The count of Maximum filliped of 0's is "<< result ;
   return 0;
}

Output

The Count of Maximum filliped of 0's is 2

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N) kerana kami hanya mengulang melalui tatasusunan. di mana N ialah saiz tatasusunan yang diberikan.

Kerumitan ruang kod di atas ialah O(1) kerana kami tidak menggunakan sebarang ruang tambahan.

Kesimpulan

Dalam tutorial ini, kami melaksanakan program untuk mencari bilangan maksimum 0s untuk diselak dalam tatasusunan binari yang diberikan supaya terdapat sekurang-kurangnya K 0s antara dua 1s. Masalah ini diselesaikan dengan mengira bilangan sifar berturut-turut antara dua 1 dan menyemak sama ada ia sesuai untuk membalikkan beberapa sifar di antara mereka. Kerumitan masa ialah O(N) dan kerumitan ruang ialah O(1). di mana N ialah saiz rentetan.

Atas ialah kandungan terperinci Maksimumkan bilangan 0s untuk membalikkan dalam tatasusunan binari yang diberikan supaya terdapat sekurang-kurangnya K 0s antara dua 1s. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!