Yağış suyunun tutulması LeetCode Həlli

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Verilənlər bazası Expedia Facebook Flipkart Goldman Sachs google microsoft Kahin Kvalifikasiya XidmətNow Tesla Walmart Laboratoriyaları Yahoo
Geyim Qalaq İki işarəBaxılıb 37

Yağış Suyu LeetCode Tutma problemində biz hündürlük xəritəsini təmsil edən N qeyri-mənfi tam ədəd verdik və hər bir çubuğun eni 1-dir. Biz yuxarıdakı strukturda tutula biləcək suyun miqdarını tapmalıyıq.

misal

Bunu bir nümunə ilə başa düşək

Yağış suyunu tutmaqPin

Yuxarıdakı yüksəklik xəritəsi üçün

Input

[2,1,0,2,2,0,1,4]

Buraxılış

6

Daha bir neçə sınaq işinə baxaq:

Input

[0,1,0,2,1,0,1,3,2,1,2,1]

Buraxılış

6

Yağış suyunu tutmağı tapmaq üçün yanaşma-1

Brute Force

  • Hər elementi keçin array
  • Soldan maksimum hündürlüyü tapın = L
  • Sağdan maksimum hündürlüyü tapın = R
  • Saxlanıla bilən maksimum su miqdarı = min (L, R) - elementin hündürlüyü

Gəlin Java və C ++ dillərində olanların kodunu nəzərdən keçirək.

Yağış suyunu tutmaq üçün Java proqramı

class Solution 
{
    public int trap(int[] height)
    {
    if(height==null)
        return 0;
    int ans=0;
    for(int i=1;i<height.length-1;i++)
    {
        int l=Integer.MIN_VALUE;
        int r=Integer.MIN_VALUE;
        for(int j=0;j<i+1;j++)
            l=Math.max(l,height[j]);
        for(int j=i;j<height.length;j++)
            r=Math.max(r,height[j]);
        ans=ans+Math.min(l,r)-height[i];
    }
    return ans;
    }
}

Yağış Suyu Tutmaq üçün C ++ Proqramı

class Solution 
{
public:
    int max(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int min(int a,int b)
    {
        if(b>a)
            return a;
        else
            return b;
    }
public:
    int trap(vector<int>& height)
    {
    if(height.size()==0) 
        return 0; 
    int ans=0; 
    int i,j;
    for(i=1;i<height.size()-1;i++) 
    { 
      int l=-1; 
      int r=-1; 
      for(j=0;j<i+1;j++) 
      l=max(l,height[j]); 
      for(j=i;j<height.size();j++)
      r=max(r,height[j]); 
      ans=ans+min(l,r)-height[i]; 
    } 
    return ans;    
    }
};
[2,1,0,2,2,0,1,4]
6

Mürəkkəblik təhlili

Yuxarıda göstərilənlərin vaxt mürəkkəbliyi O (n ^ 2) olaraq hesablana bilər.

Yağış suyunu tutmağı tapmaq üçün yanaşma-2

Dinamik proqramlaşdırma

Bütün hissələr üzərində təkrarlamaqdansa, ən yüksək blokun nöqtəyə qədər hündürlüyü müvafiq massivlərdə saxlanıla bilər.

Kodu nəzərdən keçirək

Java Proqramı

class Solution 
{
    public int trap(int[] height)
    {
    if(height.length==0)
        return 0;
    int ans=0;
    //left[i] contains the maximum height of the pillar encountered before the ith pillar
    int left[]=new int[height.length];
    left[0]=height[0];
    //righ[i] contains the maximum height of the pillar encountered after the ith pillar
    int righ[]=new int[height.length];
    righ[righ.length-1]=height[height.length-1];
    for(int i=1;i<height.length;i++)
    {
      left[i]=Math.max(height[i],left[i-1]);
    }
    for(int i=height.length-2;i>-1;i--)
    {
        righ[i]=Math.max(height[i],righ[i+1]);
    }
    for(int i=1;i<height.length-1;i++)
    {
        ans=ans+Math.min(left[i],righ[i])-height[i];
    }
    return ans;
    }
}

C ++ Proqramı

class Solution 
{
public:
    int max(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int min(int a,int b)
    {
        if(b>a)
            return a;
        else
            return b;
    }
public:
    int trap(vector<int>& height)
    {
    if(height.size()==0)
        return 0;
    int ans=0;
    int left[height.size()];
    left[0]=height[0];
    int righ[height.size()];
    righ[height.size()-1]=height[height.size()-1];
    for(int i=1;i<height.size();i++)
    {
      left[i]=max(height[i],left[i-1]);
    }
    for(int i=height.size()-2;i>-1;i--)
    {
        righ[i]=max(height[i],righ[i+1]);
    }
    for(int i=1;i<height.size()-1;i++)
    {
        ans=ans+min(left[i],righ[i])-height[i];
    }
    return ans;   
    }
};
[0,1,0,2,1,0,1,3,2,1,2,1]
6

Yağış suyunu tutmağı tapmaq üçün yanaşma-3

İki işarəçi yanaşma

Əvvəlki yanaşmadan müşahidələrə nəzər salaq

  • Right_max left_max-dan böyük olduğu müddətdə, tələyə düşən suyun miqdarını tapmaq üçün left_max-dan asılıyıq.
  • Sol_max right_max-dan böyük olduğu müddətdə, tutulan suyun miqdarını tapmaq üçün right_max-dan asılı oluruq.

Beləliklə, sol və sağ massivi qorumaq əvəzinə iki göstəricini saxlayırıq.

Bir kodun köməyi ilə daha yaxşı başa düşək.

Java Proqramı

class Solution 
{
    public int trap(int[] height)
    {
      int left=0;
      int righ=height.length-1;
      int lmax=Integer.MIN_VALUE;
      int rmax=Integer.MIN_VALUE;
      int ans=0;
      while(righ>left)
      {
          //We rely on the minimum of the both
          if(height[left]<height[righ])
          {
          //Update left max if the current height is greater
          if(height[left]>=lmax)
              lmax=height[left];
          //else add the water trapped to the answer
          else
          ans=ans+lmax-height[left];
          left=left+1;
          }
          else
          {
          //If current height is greater than right max update
          if(height[righ]>=rmax)
              rmax=height[righ];
          //else add to the answer
          else
          ans=ans+rmax-height[righ]; 
          righ=righ-1;
          }
      }
    return ans;
    }
}

C ++ Proqramı

class Solution 
{
public:
    int max(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int min(int a,int b)
    {
        if(b>a)
            return a;
        else
            return b;
    }
public:
    int trap(vector<int>& height)
    {
    int left=0; 
    int righ=height.size()-1; 
    int lmax=-1; 
    int rmax=-1; 
    int ans=0; 
    while(righ>left) 
    { 
        //We rely on the minimum of the both 
        if(height[left]<height[righ]) 
        { //Update left max if the current height is greater 
            if(height[left]>=lmax) 
                lmax=height[left]; 
            //else add the water trapped to the answer 
            else ans=ans+lmax-height[left]; left=left+1; 
        } 
        else 
        { //If current height is greater than right max update 
            if(height[righ]>=rmax) 
                rmax=height[righ]; 
            //else add to the answer 
            else 
                ans=ans+rmax-height[righ]; 
            righ=righ-1; 
        }
       }
    return ans;
    }
};
[ 8, 0, 8 ]
8

Mürəkkəblik təhlili

  • Yuxarıdakı həllin zaman mürəkkəbliyi = O (n)
  • Kosmik mürəkkəblik = O (1), çünki burada heç bir köməkçi yer istifadə etmirik.

Beləliklə, bu tələyə düşən yağış suyu problemi və həllinə bir çox yanaşma idi!

References

Translate »
1