Sürüşmə Pəncərə texnikası

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Fanatics
Geyim Sürüşmə pəncərə Texniki Scripter nəzəriyyəBaxılıb 39

Sürüşmə pəncərəsi texnikası nə ilə bir yerə gəlməzdən əvvəl? Nə edir və nə edirsə, bu konsepsiyanı kiçik bir problemlə həll etməyə imkan verir

Verilmiş bir array tam ədədlərdən ibarətdir ki, k ölçüsündə olan bütün subraylardan minimum cəmi tapmaq vəzifəmiz var.

Giriş: {1,4,0,3,5,2,6,1}

k = 4

Çıxış: 4 ölçülü minimum cəmi alt sıra (0,3)

Yanaşma-1

Brute Force

İndeks 0-dan n-k + 1-ə qədər k elementlərin cəmlərini nəzərə alaraq bütün subarrayslardan minimum cəmi tapmağa çalışaq.

Mümkün olan bütün ardıcıl alt serialları əldə edin və sonra hamısından minimum cəmi tapmağa çalışın.

Kod parçası ilə başa düşməyə çalışaq.

Sürüşən Pəncərə Texnikası üçün Java Kodu

import java.util.*;
public class brute
{
  public static int maxk(int nums[],int k)
  {
    int min=Integer.MAX_VALUE;
    for(int i=0;i<nums.length-k+1;i++)
    {
      int sum=0;
      for(int j=i;j<i+k;j++)
      {
        sum=sum+nums[j];
      }
      min=Math.min(min,sum);
    }
    return min;
  }
  public static void main(String args[])
  {
    int a[]={1,4,0,3,5,2,6,1};
    int k=4;
    int ans=maxk(a,k);
    System.out.println(ans);
  }
}

Sürüşən Pəncərə Texnikası üçün C ++ Kodu

#include<iostream>
using namespace std;
int mins(int a,int b)
{
  if(a>b)
    return b;
  else
    return a;
}
int maxk(int nums[],int k,int l)
{
  int min=9999;
  for(int i=0;i<l-k+1;i++)
  {
    int sum=0;
    for(int j=i;j<i+k;j++)
    {
      sum=sum+nums[j];
    }
    min=mins(min,sum);
  }
  return min;
}
int main()
{
  int a[]={1,4,0,3,5,2,6,1};
  int k=4;
  int l=sizeof(a)/sizeof(a[0]);
  int ans=maxk(a,k,l);
  cout<<ans;
}
{1,4,0,3,5,2,6,1}
4

(0,3)

Sürüşən Pəncərə Texnikası üçün Mürəkkəblik Analizi

Yuxarıda göstərilən yanaşma üçün vaxt mürəkkəbliyi = O (n ^ 2)

Ancaq bu sürətli və qəzəbli bir dövrdə bir O (n ^ 2) həllini istəyən.

Bunu mütləq optimallaşdırmalıyıq. Nə edək?

Yeni bir texnika tövsiyə edirəm.

Sürüşmə pəncərə nədir?

Bu konsepsiya bir ağaca dırmaşmağa çalışan bir tırtıl kimi hiss edir / bənzəyir.

Pəncərə nədir?

Pəncərə massivin içərisindən keçən bir ardıcıllıq hissəsidir

Kifayət qədər aydın deyil?

Bunu aydınlaşdırmaq üçün bir nümunədir

Sürüşmə Pəncərə texnikasıPin
2 ölçülü bir sıra üçün 6 ölçülü sürüşmə pəncərə

Yuxarıdakı şəkildə 2 ölçülü qırmızı bölgə (pəncərə) massivdən sürüşür.

Dizidən irəlilədikdə I-ni başlanğıc, j-ni pəncərənin bitmə indeksi kimi götürsək, ikisi də bir sürüşmə pəncərə vermək üçün hər ikisi bir-bir artır.

İndi eyni problemi “Sürüşmə Pəncərə Texnikası” nı yeni konsepsiya ilə həll edək

Yanaşma-2

Sürüşmə pəncərə

  • İlk k ədədlərinin cəmini hesablayın və cəminə qoyun

TADA! ilk pəncərəmizin cəmi tamamlandı

  • Hər pəncərədə cəmi tapın
    • Son pəncərədən köhnəlmiş məlumatların silinməsi, yəni massiv [current_start-1]
    • Təzə məlumatların əlavə edilməsi, yəni sıra [əvvəlki_end + 1]
    • Beləliklə, pəncərəni sürüşdürürük
  • Cəmin minimumunu bütün pəncərələrdən tapırıq

Voila! Artıq eyni problemi O (n) vaxtında həll edə bilərik

Sürüşən Pəncərə Texnikası üçün Java Kodu

import java.util.*;
public class brute
{
  public static int maxk(int nums[],int k,int n)
  {
    //If the array does not contain k elements it is not eligible
    if(n<k)
      return -1;
    //Declaring the minimum
    int min=0;
    //Finding the sum of first k elements
    for(int i=0;i<k;i++)
      min=min+nums[i];
    int cur=min;
    //As the sliding window moves 
    //We move the start and end index by 1
    for(int i=k;i<n;i++)
    {
      //Thus we remove the initial index value
      cur=cur-nums[i-k]+nums[i];
      //And add the current index value
      min=Math.min(cur,min);
    }
    return min;
  }
  public static void main(String args[])
  {
    int a[]={1,1,0,3,2,2,6,1};
    int k=5;
    int n=a.length;
    int ans=maxk(a,k,n);
    System.out.println(ans);
  }
}

Sürüşən Pəncərə Texnikası üçün C ++ Kodu

#include<iostream>
using namespace std;
    int mins(int a,int b)
    {
    	if(a>b)
    		return b;
    	else
    		return a;
    }
    int maxk(int nums[],int k,int n)
  {
    //If the array does not contain k elements it is not eligible
    if(n<k)
      return -1;
    //Declaring the minimum
    int min=0;
    int i=0;
    //Finding the sum of first k elements
    for(i=0;i<k;i++)
      min=min+nums[i];
    int cur=min;
    //As the sliding window moves 
    //We move the start and end index by 1
    for(i=k;i<n;i++)
    {
      //Thus we remove the initial index value
      cur=cur-nums[i-k]+nums[i];
      //And add the current index value
      min=mins(cur,min);
    }
    return min;
  }
  int main()
  {
    int a[]={1,1,0,3,2,2,6,1};
    int k=5;
    int n=8;
    int ans=maxk(a,k,n);
    cout<<ans;
  }
{1,1,0,3,2,2,6,1}
5
(0,4)

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi = O (n)

Budur yanınızda. Sabit sürüşmə pəncərə konsepsiyası izah edildi!

Yeni əldə edilənlərlə təcrübə keçmək necədir bir problem haqqında məlumat?

References

Translate »