Daşqın Doldurma LeetCode

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Facebook google
alqoritmlər kodlaşdırma Dərinlik İlk Axtarış müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions MatrisBaxılıb 32

Flood Fill problemində 2D verdik array a [] [], koordinatdakı pikselin rəngini əks etdirən hər bir dəyəri ilə mxn ölçüsündə bir şəkil. Bir piksel və bir rəng yeri və ya koordinatları da verilir. Verilən bir yerdəki rəngi və bütün qonşu koordinatları və ya yerləri verilmiş bir yerlə eyni rənglə əvəz edin. Şəkildə yeni rəngləri əks etdirən massivi çap edin.

Daşqın Doldurma LeetCodePin

misal

İndi daşqın doldurma alqoritmi nümunələrinə baxın.

Giriş:

a [] [] = [[1 1 1]

[1 1 0]

[1 0 1]]

x = 1

y = 1

rəng = 2

Çıxış: 

[2 2 2]

[2 2 0]

[2 0 1]

Giriş:

a [] [] = [[1 1 0]

[1 1 0]

[1 0 0]]

x = 1

y = 3

rəng = 5

Çıxış:

[1 1 5]

[1 1 5]

[1 5 5]

Rekursiv metod

Daşqın Dolgu LeetCode üçün alqoritm

  1. Mxn ölçüsündə n-ə bərabər bir mxn ölçüsündə bir 2D massivini başladın, hər piksel rəngini göstərən piksel şəklindədir.
  2. Həm də iki koordinat x, y və bir rəng başladın.
  3. X və y 0-dan az və ya m və ya n-dən böyükdürsə, qayıdın.
  4. Rəngi ​​x və y koordinatlarında bir prevC dəyişkənində saxlayın.
  5. X və y koordinatlarındakı rəngin prevC-yə bərabər olmadığını yoxlayın, yəni əvvəlki rəng, qayıdın.
  6. X və y koordinatlarındakı rəng yeni bir rəngə bərabərdirsə, geri qayıdın.
  7. Başqa bir rəng x və y koordinatlarında yeni bir rəng olaraq yenilənir.
  8. (X + 1, y), (x-1, y), (x, y + 1) və (x, y-1) koordinatları ilə funksiyaya dörd rekursiv zəng edin.
  9. Yenilənmiş 2D seriyasını çap edin.

Daşqın Dolması üçün C ++ Proqramı LeetCode

#include<iostream> 
using namespace std; 
  
#define m 3
#define n 3
  
void floodFill(int a[][n], int x, int y, int prevC, int newC){ 
    
    if(x<0 || x>=m || y<0 || y>=n) 
        return; 
    if(a[x][y] != prevC) 
        return; 
    if(a[x][y] == newC)  
        return;  
  
    a[x][y] = newC; 
  
    floodFill(a, x+1, y, prevC, newC); 
    floodFill(a, x-1, y, prevC, newC); 
    floodFill(a, x, y+1, prevC, newC); 
    floodFill(a, x, y-1, prevC, newC); 
} 
  
void Fill(int a[][n], int x, int y, int color){ 
    int prevColor = a[x][y]; 
    floodFill(a, x, y, prevColor, color); 
} 
  
int main(){ 
    
    int a[m][n] = {{1, 1, 1}, 
                   {1, 1, 0}, 
                   {1, 0, 1},
                  }; 
    int x = 1, y = 1, color = 2; 
    
    Fill(a, x, y, color); 
    
    for(int i=0; i<m; i++){ 
        
        cout<<"[ ";
        for (int j=0; j<m; j++) 
           cout<<a[i][j]<<" "; 
        cout<<"]\n"; 
    } 
}
[ 2 2 2 ]
[ 2 2 0 ]
[ 2 0 1 ]

Daşqın Dolması üçün Java Proqramı LeetCode

class floodfill{ 
  
    static int m = 3; 
    static int n = 3; 
      
    static void floodFill(int a[][], int x, int y, int prevC, int newC){ 
         
        if(x<0 || x>=m || y<0 || y>=n) 
            return; 
        if(a[x][y] != prevC) 
            return; 
      
        a[x][y] = newC; 
      
        floodFill(a, x+1, y, prevC, newC); 
        floodFill(a, x-1, y, prevC, newC); 
        floodFill(a, x, y+1, prevC, newC); 
        floodFill(a, x, y-1, prevC, newC); 
    } 
      
    static void Fill(int a[][], int x, int y, int color){ 
        int prevColor = a[x][y]; 
        floodFill(a, x, y, prevColor, color); 
    } 
      
    public static void main(String[] args){ 
        int a[][] = {{1, 1, 1}, 
                        {1, 1, 0}, 
                        {1, 0, 1}, 
                        }; 
        int x = 1, y = 1, color = 2; 
        Fill(a, x, y, color); 
      
        for(int i=0; i<m; i++){ 
            System.out.print("[ ");
            for(int j=0; j<n; j++) 
                System.out.print(a[i][j]+" "); 
            System.out.print("]");    
            System.out.println(); 
        } 
    } 
}
[ 2 2 2 ]
[ 2 2 0 ]
[ 2 0 1 ]

Daşqın Dolması LeetCode üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi: O (N), burada N - Satır * Sütuna bərabər olan elementlərin sayı. yəni şəkil piksellərinin sayı.

Köməkçi məkan: O (1), çünki tətbiqdə heç bir köməkçi yer istifadə etmirik.

References

Şərh yaz

Translate »