Taisnstūru skaits ar apgabalu K, kas sastāv tikai no 1 no dotajiem binārajiem masīviem

Blogs

Doti divi bināri masīvi TO [] un B [] , garumā N un M attiecīgi uzdevums ir atrast laukuma taisnstūru skaitu TO kas sastāv no 1 Ir matricā C [] [] ģenerēts, reizinot abus masīvus tā, lai ** C [i] [j] = A [i] *B [j] ** (1

Piemēri:

Ievads: _ N = 3, M = 3, A [] = {1, 1, 0}, B [] = {0, 1, 1}, K = 2_

Izeja: _ 4_

Paskaidrojums: _ C [] [] = {0, 1, 1}, {0, 1, 1}, {0, 0, 0}} _

0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0

Tāpēc no matricas ir iespējami 4 laukuma 2 taisnstūri.

Ievads: _ N = 4, M = 2, A [] = {0, 0, 1, 1}, B [] = {1, 0, 1}, K = 2_

Izeja: _ 2_

Paskaidrojums: _ C [] [] = {{0, 0, 0}, {0, 0, 0}, {1, 0, 1}, {1, 0, 1}} _

0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 1 1 0 1

Tāpēc matricā ir 2 iespējamie 2. apgabala taisnstūri.

Ieteicams: lūdzu, izmēģiniet savu pieeju {ŠEIT} Pirmkārt, pirms pārejat pie risinājuma.

** Naiva pieeja: ** Vienkāršākā pieeja problēmas risināšanai ir ģenerēt nepieciešamo matricu reizinot abus masīvus un katru iespējamo laukuma ** K taisnstūri, ** pārbaudiet, vai tas sastāv tikai no 1 vai nē ...

Laika sarežģītība: _ O (N * M * K) _

Palīgtelpa: _ O (N * M) _

** Efektīva pieeja: ** Lai optimizētu iepriekš minēto pieeju, matricas ģenerēšanas vietā ir jāveic šādi novērojumi:

Tāpēc problēma samazinās, atrodot apakšmasas, kas sastāv tikai no 1 Visu iespējamo garumu, kuru pareizie dalītāji ir TO , no masīviem TO [] un B [] . Lai atrisinātu problēmu, veiciet tālāk norādītās darbības.

  • Iepriekš aprēķiniet iespējamo apakšmasu skaits .
  • Atkārtojiet visus dalītāji no TO un katram iespējamajam pārim ( p, q ) kur p * q = K , pārbaudiet, vai A [] un B [] eksistē apakšslāņi ar garumu p, q.
  • Attiecīgi palieliniet iespējamo šādu apakšmasu skaitu un, visbeidzot, izdrukājiet iegūto skaitu.

Tālāk ir aprakstīta iepriekš minētās pieejas ieviešana:

  • C ++

// C++ Program to implement

// the above approach

#include

**using** **namespace** std;

// Function to find the subarrays of

// all possible lengths made up of only 1s

vector findSubarrays(vector& a)

{

**int** n = a.size();

// Stores the frequency

// of the subarrays

vector freq(n + 1);

**int** count = 0;

**for** (``**int** i = 0; i

**if** (a[i] == 0) {

// Check if the previous

// value was also 0

**if** (count == 0)

**continue**``;

// If the previous value was 1

**else** {

**int** value = count;

**for** (``**int** j = 1; j <= count; j++) {

// Find the subarrays of

// each size from 1 to count

freq[j] += value;

value--;

}

izvēlnes ikonas materiāls UI

count = 0;

}

}

**else**

count++;

}

// If A[] is of the form ....111

**if** (count > 0) {

**int** value = count;

**for** (``**int** j = 1; j <= count; j++) {

freq[j] += value;

value--;

}

}

**return** freq;

}

// Function to find the count

Mērija Kerija van Dīka

// of all possible rectangles

**void** countRectangles(vector& a,

vector& b, **int** K)

{

// Size of each of the arrays

**int** n = a.size();

**int** m = b.size();

// Stores the count of subarrays

// of each size consisting of

// only 1s from array A[]

vector subA

= findSubarrays(a);

// Stores the count of subarrays

// of each size consisting of

// only 1s from array B[]

vector subB

= findSubarrays(b);

**int** total = 0;

// Iterating over all subarrays

// consisting of only 1s in A[]

**for** (``**int** i = 1; i

// If i is a factor of K, then

// there is a subarray of size K/i in B[]

**if** (K % i == 0 and (K / i) <= m) {

total = total + subA[i] * subB[K / i];

}

}

cout << total;

}

// Driver Code

**int** main()

{

vector a = { 0, 0, 1, 1 };

vector b = { 1, 0, 1 };

**int** K = 2;

countRectangles(a, b, K);

**return** 0;

}

Izeja:

2

Laika sarežģītība: _ O (D) * O (N + M), kur D ir K dalītāju skaits.

Palīgtelpa: _ O (N + M) _

Uzmanību lasītāj! Nepārtrauciet mācīties tagad. Iegūstiet visas svarīgās DSA koncepcijas, izmantojot DSA pašmācības kurss par studentiem draudzīgu cenu un sagatavojies nozarei.

#masīvi #ģeometriskā #matemātiskā #matrica #meklēšana #apgabala apjoma programmas #binārais attēlojums #kvadrātveida taisnstūris #apakšslānis #apakšmatrica

www.geeksforgeeks.org

Taisnstūru skaits ar apgabalu K, kas sastāv tikai no 1 no dotajiem binārajiem masīviem

Datorzinātņu portāls geekiem. Tas satur labi uzrakstītus, labi pārdomātus un labi izskaidrotus datorzinātnes un programmēšanas rakstus, viktorīnas un praksi/konkurētspējīgu programmēšanu/uzņēmuma interviju.