TEHNIKA DRSNIH OKEN - TECHCODEVIEW.COM

Težave z drsečim oknom so težave, pri katerih se okno s fiksno ali spremenljivo velikostjo premika skozi podatkovno strukturo, običajno matriko ali niz, za učinkovito reševanje težav na podlagi zveznih podmnožic elementov. Ta tehnika se uporablja, ko moramo najti podnize ali podnize glede na dani nabor pogojev.

Tehnika drsnih oken

Kazalo

Kaj je tehnika drsnih oken?
Kako uporabljati tehniko drsnega okna?
Kako prepoznati težave z drsnimi okni
Primeri uporabe tehnike drsnih oken
Vadbene naloge pri tehniki drsnega okna

Kaj je tehnika drsnih oken?

Tehnika drsnih oken je metoda, ki se uporablja za učinkovito reševanje problemov, ki vključujejo definiranje a okno oz obseg v vhodne podatke (matrike ali nize) in nato premikanje tega okna po podatkih za izvedbo neke operacije znotraj okna. Ta tehnika se pogosto uporablja v algoritmih, kot je iskanje podnizov z določeno vsoto, iskanje najdaljšega podniza z edinstvenimi znaki ali reševanje problemov, ki zahtevajo okno fiksne velikosti za učinkovito obdelavo elementov.

Vzemimo primer, da to pravilno razumemo, recimo, da imamo niz velikosti n in tudi celo število K. Zdaj moramo natančno izračunati največjo vsoto podniza K. Kako naj zdaj pristopimo k temu problemu?

Eden od načinov za to je, da vzamete vsako podnizo velikosti K iz matrike in ugotovite največjo vsoto teh podnizov. To je mogoče storiti z uporabo ugnezdenih zank, ki bodo povzročile O(N²) Časovna zapletenost.

Toda ali lahko optimiziramo ta pristop?

Odgovor je Da, namesto da bi vzeli vsakega K podniz velikosti K in izračunamo njegovo vsoto, lahko samo vzamemo eno podmatrizo velikosti K od 0 do indeksa K-1 in izračunamo njeno vsoto, zdaj premaknemo naš obseg enega za drugim skupaj s ponovitvami in posodobimo rezultat, kot v naslednji ponovitvi povečamo levo in desni kazalec in posodobite prejšnjo vsoto, kot je prikazano na spodnji sliki:

Tehnika drsnih oken

Zdaj sledite tej metodi za vsako ponovitev, dokler ne dosežemo konca niza:

Tehnika drsnih oken

aritmetično logična enota

Tako lahko vidimo, da namesto ponovnega izračuna vsote vsake podmatrike velikosti K uporabljamo prejšnje okno velikosti K in z uporabo njegovih rezultatov posodobimo vsoto in premaknemo okno v desno s premikanjem kazalcev levo in desno, ta operacija je optimalna, ker vzemite O(1) časa za premik obsega namesto ponovnega izračuna.

Ta pristop premikanja kazalcev in ustreznega izračuna rezultatov je znan kot Tehnika drsnih oken .

Kako uporabljati tehniko drsnega okna?

V osnovi obstajata dve vrsti drsnih oken:

1. Drsno okno fiksne velikosti:

Splošni koraki za rešitev teh vprašanj z upoštevanjem spodnjih korakov:

Poiščite želeno velikost okna, recimo K.
Izračunajte rezultat za 1. okno, tj. vključite prvih K elementov podatkovne strukture.
Nato z zanko premaknite okno za 1 in nadaljujte z izračunavanjem rezultata okno za oknom.

2. Drsno okno spremenljive velikosti:

Splošni koraki za rešitev teh vprašanj z upoštevanjem spodnjih korakov:

Pri tej vrsti problema z drsečim oknom povečujemo desni kazalec enega za drugim, dokler naš pogoj ni resničen.
Na katerem koli koraku, če se naše stanje ne ujema, zmanjšamo velikost okna s povečanjem levega kazalca.
Ko je naš pogoj izpolnjen, začnemo povečevati desni kazalec in sledimo 1. koraku.
Sledimo tem korakom, dokler ne pridemo do konca niza.

Kako prepoznati težave z drsnimi okni:

Te težave običajno zahtevajo iskanje maksimuma/minimuma Podniz , Podnizi ki izpolnjujejo določen pogoj.
Velikost podmatrike ali podniza ' K’ bo podan v nekaterih težavah.
Te težave je mogoče zlahka rešiti v O(N²) časovna kompleksnost z uporabo ugnezdenih zank, z drsečim oknom jih lahko rešimo v O(n) Časovna zapletenost.
Zahtevana časovna kompleksnost: O(N) ali O(Nlog(N))
Omejitve: N <= 10⁶, Če je N velikost matrike/niza.

Primeri uporabe tehnike drsnih oken:

1. Če želite najti največjo vsoto vseh podnizov velikosti K:

Podana je matrika celih števil velikosti 'n', Naš cilj je izračunati največjo vsoto 'k' zaporednih elementov v nizu.

Vnos: arr[] = {100, 200, 300, 400}, k = 2
Izhod: 700

Vnos: arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Izhod: 39
Največjo vsoto dobimo tako, da dodamo podmatriko {4, 2, 10, 23} velikosti 4.

Vnos: arr[] = {2, 3}, k = 3
Izhod: Neveljavno
Podmatrika velikosti 3 ne obstaja, saj je velikost celotne matrike 2.

Naivni pristop: Torej, analizirajmo težavo z Pristop surove sile . Začnemo s prvim indeksom in seštevamo do kth element. To naredimo za vse možne zaporedne bloke ali skupine k elementov. Ta metoda zahteva ugnezdeno zanko for, zunanja zanka for se začne z začetnim elementom bloka k elementov, notranja ali ugnezdena zanka pa se bo seštevala do k-tega elementa.

Spodaj je izvedba zgornjega pristopa:

C++

 // O(n*k) solution for finding maximum sum of // a subarray of size k #include  using namespace std; // Returns maximum sum in a subarray of size k. int maxSum(int arr[], int n, int k) {  // Initialize result  int max_sum = INT_MIN;  // Consider all blocks starting with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = max(current_sum, max_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  cout << maxSum(arr, n, k);  return 0; } // This code is contributed by Aditya Kumar (adityakumar129)>

 // O(n*k) solution for finding maximum sum of // a subarray of size k #include  #include  #include  // Find maximum between two numbers. int max(int num1, int num2) {  return (num1>št.2)? num1 : num2; } // Vrne največjo vsoto v podnizu velikosti k. int maxSum(int arr[], int n, int k) { // Inicializiraj rezultat int max_sum = INT_MIN;  // Upoštevajte vse bloke, ki se začnejo z i.  za (int i = 0; i< n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = max(current_sum, max_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  printf('%d', maxSum(arr, n, k));  return 0; } // This code is contributed by Aditya Kumar (adityakumar129)>

Java

 // Java code O(n*k) solution for finding maximum sum of // a subarray of size k class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int arr[], int n, int k)  {  // Initialize result  int max_sum = Integer.MIN_VALUE;  // Consider all blocks starting with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = Math.max(current_sum, max_sum);  }  return max_sum;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.length;  System.out.println(maxSum(arr, n, k));  } } // This code is contributed by Aditya Kumar (adityakumar129)>

Python3

 # code import sys # O(n * k) solution for finding # maximum sum of a subarray of size k INT_MIN = -sys.maxsize - 1 # Returns maximum sum in a # subarray of size k. def maxSum(arr, n, k): # Initialize result max_sum = INT_MIN # Consider all blocks # starting with i. for i in range(n - k + 1): current_sum = 0 for j in range(k): current_sum = current_sum + arr[i + j] # Update result if required. max_sum = max(current_sum, max_sum) return max_sum # Driver code arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] k = 4 n = len(arr) print(maxSum(arr, n, k)) # This code is contributed by mits>

 // C# code here O(n*k) solution for // finding maximum sum of a subarray // of size k using System; class GFG {  // Returns maximum sum in a  // subarray of size k.  static int maxSum(int[] arr, int n, int k)  {  // Initialize result  int max_sum = int.MinValue;  // Consider all blocks starting  // with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = Math.Max(current_sum, max_sum);  }  return max_sum;  }  // Driver code  public static void Main()  {  int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.Length;  Console.WriteLine(maxSum(arr, n, k));  } } // This code is contributed by anuj_67.>

JavaScript

 function maxSum(arr, n, k) {  let max_sum = 0;    // Loop from i to k  for (let i = 0; i < k; i++) {  max_sum += arr[i];  }    let window_sum = max_sum;  for (let i = k; i < n; i++) {  window_sum = window_sum - arr[i - k] + arr[i];  max_sum = Math.max(max_sum, window_sum);  }  return max_sum; } // Driver code let arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]; let k = 4; let n = arr.length; console.log(maxSum(arr, n, k));>

PHP

  // code ?>// O(n*k) rešitev za iskanje največje vsote // podniza velikosti k // Vrne največjo vsoto v podmatrizi velikosti k. funkcija maxSum($arr, $n, $k) { // Inicializiraj rezultat $max_sum = PHP_INT_MIN ; // Upoštevajte vse bloke // začenši z i. za ($i = 0; $i< $n - $k + 1; $i++) { $current_sum = 0; for ( $j = 0; $j < $k; $j++) $current_sum = $current_sum + $arr[$i + $j]; // Update result if required. $max_sum = max($current_sum, $max_sum ); } return $max_sum; } // Driver code $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20); $k = 4; $n = count($arr); echo maxSum($arr, $n, $k); // This code is contributed by anuj_67. ?>>

Izhod

24>

Časovna zahtevnost: O(k*n), ker vsebuje dve ugnezdeni zanki.
Pomožni prostor: O(1)

Uporaba tehnike drsnega okna:

Vsoto prvih k elementov od n členov izračunamo z uporabo linearne zanke in vsoto shranimo v spremenljivko window_sum .
Nato bomo linearno prečkali matriko, dokler ne doseže konca in hkrati spremljali največjo vsoto.
Če želite dobiti trenutno vsoto bloka k elementov, preprosto odštejte prvi element od prejšnjega bloka in dodajte zadnji element trenutnega bloka.

Spodnja predstavitev bo pojasnila, kako okno drsi čez niz.

Razmislite o nizu prihod [] = {5, 2, -1, 0, 3} in vrednost k = 3 in n = 5

To je začetna faza, kjer smo izračunali začetno vsoto okna, začenši z indeksom 0. Na tej stopnji je okenska vsota 6. Zdaj smo največjo_vsoto nastavili kot trenutno_okno, tj. 6.

Zdaj pomaknemo naše okno za indeks enote. Zato zdaj iz okna zavrže 5 in oknu doda 0. Zato bomo našo novo okensko vsoto dobili tako, da odštejemo 5 in ji nato dodamo 0. Torej, naša okenska vsota zdaj postane 1. Zdaj bomo to okensko vsoto primerjali z največjo_vsoto. Ker je manjši, največje_vsote ne bomo spremenili.

en milijon v številkah

Podobno zdaj ponovno premaknemo naše okno za indeks enote in dobimo novo okensko vsoto 2. Ponovno preverimo, ali je ta trenutna okenska vsota večja od največje_vsote do zdaj. Ponovno je manjši, tako da največje_vsote ne spremenimo.
Zato je za zgornjo matriko naša največja_vsota 6.

Spodaj je koda za zgornji pristop:

C++

 // O(n) solution for finding maximum sum of // a subarray of size k #include  using namespace std; // Returns maximum sum in a subarray of size k. int maxSum(int arr[], int n, int k) {  // n must be greater  if (n <= k) {  cout << 'Invalid';  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = max(max_sum, window_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  cout << maxSum(arr, n, k);  return 0; }>

Java

 // Java code for // O(n) solution for finding // maximum sum of a subarray // of size k class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int arr[], int n, int k)  {  // n must be greater  if (n <= k) {  System.out.println('Invalid');  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = Math.max(max_sum, window_sum);  }  return max_sum;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.length;  System.out.println(maxSum(arr, n, k));  } } // This code is contributed // by prerna saini.>

Python3

 # O(n) solution for finding # maximum sum of a subarray of size k def maxSum(arr, k): # length of the array n = len(arr) # n must be greater than k if n <= k: print('Invalid') return -1 # Compute sum of first window of size k window_sum = sum(arr[:k]) # first sum available max_sum = window_sum # Compute the sums of remaining windows by # removing first element of previous # window and adding last element of # the current window. for i in range(n - k): window_sum = window_sum - arr[i] + arr[i + k] max_sum = max(window_sum, max_sum) return max_sum # Driver code arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] k = 4 print(maxSum(arr, k)) # This code is contributed by Kyle McClay>

 // C# code for O(n) solution for finding // maximum sum of a subarray of size k using System; class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int[] arr, int n, int k)  {  // n must be greater  if (n <= k) {  Console.WriteLine('Invalid');  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = Math.Max(max_sum, window_sum);  }  return max_sum;  }  // Driver code  public static void Main()  {  int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.Length;  Console.WriteLine(maxSum(arr, n, k));  } } // This code is contributed by anuj_67.>

JavaScript

PHP

  // O(n) solution for finding maximum sum of // a subarray of size k // Returns maximum sum in a  // subarray of size k. function maxSum( $arr, $n, $k) { // n must be greater if ($n <= $k) { echo 'Invalid'; return -1; } // Compute sum of first // window of size k $max_sum = 0; for($i = 0; $i < $k; $i++) $max_sum += $arr[$i]; // Compute sums of remaining windows by // removing first element of previous // window and adding last element of // current window. $window_sum = $max_sum; for ($i = $k; $i < $n; $i++) { $window_sum += $arr[$i] - $arr[$i - $k]; $max_sum = max($max_sum, $window_sum); } return $max_sum; } // Driver code $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20); $k = 4; $n = count($arr); echo maxSum($arr, $n, $k); // This code is contributed by anuj_67 ?>>

Izhod

24>

Časovna zapletenost: O(n), kjer n je velikost vhodne matrike prihod [] .
Pomožni prostor: O(1)

2. Najmanjša podmatrika z vsoto, večjo od dane vrednosti:

Podana matrika prihod [] celih števil in števila X , naloga je poiskati najmanjšo podnizo z vsoto, večjo od dane vrednosti.

Pristop:

To težavo lahko rešimo s tehniko drsnega okna in ohranimo dva kazalca: začetek in konec, ki označujeta začetek in konec okna. Končni kazalec lahko še naprej povečujemo, dokler vsota okna ni manjša ali enaka X. Ko vsota okna postane večja od X, zabeležimo dolžino okna in začnemo premikati začetni kazalec do vsote okna postane manjša ali enaka X. Zdaj, ko vsota postane manjša ali enaka X, ponovno začnite povečevati končni kazalec. Nadaljujte s premikanjem začetnega in končnega kazalca, dokler ne dosežemo konca polja.

3. Poiščite podmatriko z dano vsoto v matriki nenegativnih celih števil:

Podana matrika prihod [] nenegativnih celih števil in celega števila vsota , poiščite podmatriko, ki dodaja dano vsota .

Pristop:

Ideja je preprosta, saj vemo, da so vsi elementi v podmatriži pozitivni, torej če ima podmatrika vsoto večjo od podana vsota potem ni možnosti, da bo dodajanje elementov v trenutno podmatriko enako dani vsoti. Torej je ideja uporabiti podoben pristop kot a drsno okno .

Začnite s prazno podmatriko.
dodajajte elemente v podmatriko, dokler vsota ni manjša od x (navedena vsota) .
Če je vsota večja od x , odstranite elemente iz začetek trenutne podmatrike.

4. Najmanjše okno, ki vsebuje vse znake samega niza:

Pristop:

V bistvu se okno znakov vzdržuje z uporabo dveh kazalcev začetek in konec . te začetek in konec s kazalci lahko zmanjšate oziroma povečate velikost okna. Kadarkoli okno vsebuje vse znake danega niza, se okno skrči z leve strani, da se odstranijo dodatni znaki, nato pa se njegova dolžina primerja z najmanjšim oknom, najdenim do zdaj.
Če v trenutnem oknu ni mogoče izbrisati več znakov, začnemo povečevati velikost okna z uporabo konec dokler niso v oknu tudi vsi različni znaki v nizu. Na koncu poiščite najmanjšo velikost vsakega okna.

Vadbene težave pri tehniki drsnega okna:

Problem	Težava Povezava
Poiščite podniz z dano vsoto	Rešiti
Največ drsnega okna (največje od vseh podnizov velikosti K)	Rešiti
Najdaljša podmatrika z vsoto K	Rešiti
Poiščite največjo (ali najmanjšo) vsoto podniza velikosti k	Rešiti
Najmanjše okno v nizu, ki vsebuje vse znake drugega niza	Rešiti
Dolžina najdaljšega podniza brez ponavljajočih se znakov	Rešiti
Prvo negativno celo število v vsakem oknu velikosti k	Rešiti mysql pokaži uporabnike
Preštejte različne elemente v vsakem oknu velikosti k	Rešiti
Najmanjše okno, ki vsebuje vse znake samega niza	Rešiti
Največja podmatrika vsote z najmanj k števili	Rešiti

Povezani članki:

R ecent Članki o tehniki drsnih oken
Vprašanja za vadbo o drsnem oknu
DSA Self-Paced – Najbolj uporabljen in zaupanja vreden tečaj o DSA