Ada Perimetri Leetcode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Bloomberg Facebook google microsoft
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 34

Problem bəyanat

Bu problemdə bizə 2-D bir sıra şəklində bir ızgara verilir. grid [i] [j] = 0 o nöqtədə suyun olduğunu və [i] [j] = 1 torpağı təmsil edir. Şəbəkə hüceyrələri şaquli/üfüqi olaraq bağlanır, lakin diaqonal olaraq deyil. Tam olaraq bir ada var (a bağlı komponent torpaq hüceyrələrinin) verilmiş girişində. Bu problemin perimetrini təyin etməliyik.

misal

grid = {{0,1,0,0},{1,1,1,0},{0,1,0,0},{1,1,0,0}}
16
grid = {{1}}
4

Pin

Yanaşma (Sadə Hesablama)

Problemi görməyin sadə yolu budur ki, parametrə yalnız torpaq hüceyrələri kömək edəcəkdir. Perimetri hesablamaq üçün digər quru hüceyrələri ilə bölüşdürülməmiş bir tərəfi olan bir torpaq hüceyrəsi nəzərə alına bilər. Çünki quru hüceyrəsi bir tərəfi digər quru hüceyrəsi ilə bölüşürsə, bu adanın ızgaradakı xarici sərhədi olmayacaqdır.

Ada Perimetri Leetcode həllinin tətbiqi

C ++ Proqramı

#include <bits/stdc++.h>

using namespace std;

int islandPerimeter(vector<vector<int>>& grid) {
    int n = grid.size() , m = grid[0].size();
    int perimeter = 0 , sides = 0;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < m;  j++) {
            if(grid[i][j] == 1) {
                sides = 0;
                if(i == 0)
                    sides++;
                else
                    sides += (grid[i - 1][j] == 0);

                if(j == 0)
                    sides++;
                else
                    sides += (grid[i][j - 1] == 0);

                if(i == n - 1)
                    sides++;
                else
                    sides += (grid[i + 1][j] == 0);

                if(j == m - 1)
                    sides++;
                else
                    sides += (grid[i][j + 1] == 0);

                perimeter += sides;
            }
        }
    return perimeter;
}

int main() {
    vector< vector <int> > grid = {{0 , 1 , 0 , 0},
                                   {1 , 1 , 1 , 0},
                                   {0 , 1 , 0 , 0},
                                   {1 , 1 , 0 , 0}};
    cout << islandPerimeter(grid) << endl;
    return 0;
}

Java Proqramı

class island_perimeter {

    public static void main(String args[]) {
        int[][] grid = {{0 , 1 , 0 , 0},
                        {1 , 1 , 1 , 0},
                        {0 , 1 , 0 , 0},
                        {1 , 1 , 0 , 0}};
        System.out.println(islandPerimeter(grid));
    }

    public static int islandPerimeter(int[][] grid) {
        int n = grid.length , m = grid[0].length;
        int perimeter = 0 , sides = 0;
        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < m;  j++) {
                if(grid[i][j] == 1) {
                    sides = 0;
                    if(i == 0)
                        sides++;
                    else if(grid[i - 1][j] == 0)
                        sides++;

                    if(j == 0)
                        sides++;
                    else if(grid[i][j - 1] == 0)
                        sides++;

                    if(i == n - 1)
                        sides++;
                    else if(grid[i + 1][j] == 0)
                        sides++;

                    if(j == m - 1)
                        sides++;
                    else if(grid[i][j + 1] == 0)
                        sides++;

                    perimeter += sides;
                }
            }
        return perimeter;
    }
}
16

Ada Perimetri Leetcode Həllinin Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (N * M) burada N = şəbəkədəki sıra sayı, M = şəbəkədəki sütun sayı.

Kosmik Mürəkkəblik 

O (1) istifadə etdiyimiz kimi daimi yer dəyişənlər üçün.

Yanaşma (Effektiv sayma)

Yuxarıdakı yanaşmada, dörd qonşusunu yoxlayaraq perimetrə töhfə verən quru hüceyrəsinin tərəflərini sayırdıq. Bunu yalnız iki qonşunu yoxlamaq üçün inkişaf etdirə bilərik. Şəbəkədən keçmək üçün sağa və aşağı düşdükdə, yalnız bir quru hüceyrəsinə sol və yuxarı hüceyrələri yoxlaya bilərik. Hər quru hüceyrənin adanın ətrafına '4' töhfə verdiyini düşünə bilərik. Ancaq quru hüceyrə öz tərəflərini (tərəflərini) başqa bir hüceyrə ilə bölüşürsə, ondan 2 çıxardacağıq (biri bölüşdürülən tərəfi üçün, digəri digər hüceyrə də bir tərəfi paylaşdığı üçün). Hər iki həllin də vaxt mürəkkəbliyi eynidir, lakin bu yanaşmada işləmə baxımından bir qədər yaxşılaşırıq.

Ada Perimetri Leetcode həllinin tətbiqi

C ++ Proqramı

#include <bits/stdc++.h>

using namespace std;

int islandPerimeter(vector<vector<int>>& grid) {
    int n = grid.size() , m = grid[0].size() , perimeter = 0;
    for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < m ; j++) {
            if(grid[i][j] == 1) {
                perimeter += 4;

                if(i > 0 && grid[i - 1][j] == 1)
                    perimeter -= 2;

                if(j > 0 && grid[i][j - 1] == 1)
                    perimeter -= 2;
            }
        }
    }
    return perimeter;
}

int main() {
    vector< vector <int> > grid = {{0 , 1 , 0 , 0},
                                   {1 , 1 , 1 , 0},
                                   {0 , 1 , 0 , 0},
                                   {1 , 1 , 0 , 0}};
    cout << islandPerimeter(grid) << endl;
    return 0;
}

Java Proqramı

class island_perimeter {

    public static void main(String args[]) {
        int[][] grid = {{0 , 1 , 0 , 0},
                        {1 , 1 , 1 , 0},
                        {0 , 1 , 0 , 0},
                        {1 , 1 , 0 , 0}};
        System.out.println(islandPerimeter(grid));
    }

    public static int islandPerimeter(int[][] grid) {
        int n = grid.length , m = grid[0].length , perimeter = 0;
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < m ; j++) {
                if(grid[i][j] == 1) {
                    perimeter += 4;

                    if(i > 0 && grid[i - 1][j] == 1)
                        perimeter -= 2;

                    if(j > 0 && grid[i][j - 1] == 1)
                        perimeter -= 2;
                }
            }
        }
        return perimeter;
    }
}
16

Ada Perimetri Leetcode Həllinin Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (N * M) burada N = şəbəkədəki sıra sayı, M = şəbəkədəki sütun sayı.

Kosmik Mürəkkəblik 

O (1) dəyişənlər üçün sabit yer istifadə etdiyimiz üçün.

Şərh yaz

Translate »
2