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.
Spis treści
Przykład
Rozumiemy to na przykładzie
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!
