Zatrzymywanie wody deszczowej Rozwiązanie LeetCode

Poziom trudności Ciężko
Często zadawane pytania Adobe Amazonka Apple Bloomberg Pamięci danych Expedia Facebook Flipkart Goldman Sachs Google Microsoft wyrocznia Qualtrics ServiceNow Tesla Laboratoria Walmart Yahoo
Szyk Stos Dwa wskaźnikiodwiedzajacy 99

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

W zadaniu Trapping Rain Water LeetCode podaliśmy N nieujemnych liczb całkowitych reprezentujących mapę wysokości, a szerokość każdego słupka wynosi 1. Musimy znaleźć ilość wody, która może zostać uwięziona w powyższej strukturze.

Przykład

Rozumiemy to na przykładzie

Zatrzymywanie wody deszczowejszpilka

Dla powyższej mapy wysokości

Wkład

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

Wydajność

6

Spójrzmy na więcej przypadków testowych:

Wkład

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

Wydajność

6

Podejście-1 do znalezienia pułapki wody deszczowej

Brutalna siła

  • Przejdź przez każdy element w szyk
  • Znajdź maksymalną wysokość od lewej = L
  • Znajdź maksymalną wysokość z prawej strony = R
  • Maksymalna ilość wody jaką można zmagazynować = min (L, R) - wysokość elementu

Przyjrzyjmy się temu samemu kodowi w Javie i C ++.

Program Java do zatrzymywania wody deszczowej

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;
    }
}

Program C ++ do zatrzymywania wody deszczowej

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

Analiza złożoności

Złożoność czasową powyższego można obliczyć jako O (n ^ 2)

Podejście-2 do znalezienia pułapki wody deszczowej

Programowanie dynamiczne

Zamiast powtarzać iterację po całych częściach, wysokość najwyższego bloku do punktu może być przechowywana w odpowiednich tablicach.

Przyjrzyjmy się kodowi

Program Java

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;
    }
}

Program w C ++

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

Podejście-3 do znalezienia pułapki wody deszczowej

Podejście za pomocą dwóch wskaźników

Przyjrzyjmy się obserwacjom z poprzedniego podejścia

  • Tak długo, jak right_max jest większe niż left_max, polegamy na left_max, aby znaleźć ilość uwięzionej wody
  • Tak długo, jak left_max jest większe niż right_max, polegamy na right_max, aby znaleźć ilość uwięzionej wody.

Dlatego zamiast utrzymywać lewą i prawą tablicę, utrzymujemy dwa wskaźniki.

Zrozummy to lepiej za pomocą kodu.

Program Java

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;
    }
}

Program w C ++

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

Analiza złożoności

  • Złożoność czasowa powyższego rozwiązania = O (n)
  • Złożoność przestrzeni = O (1), ponieważ nie używamy tutaj żadnej dodatkowej spacji.

Tak więc był to problem zatrzymywania wody deszczowej i wiele sposobów jego rozwiązania!

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »
1