კუნძულის პერიმეტრი Leetcode Solution


Რთული ტური Easy
ხშირად ეკითხებიან Amazon Bloomberg Facebook Google microsoft
Array

პრობლემის განცხადება

ამ პრობლემის დროს, ჩვენ გვეძლევა ქსელი 2-D მასივის სახით. ქსელი [i] [j] = 0 წარმოადგენს ამ წერტილში წყალს, ხოლო ქსელი [i] [j] = 1 წარმოადგენს მიწას. ქსელის უჯრედები ვერტიკალურად / ჰორიზონტალურად არის დაკავშირებული, მაგრამ არა დიაგონალზე. მოცემულ შესავალში ზუსტად არის ერთი კუნძული (მიწის უჯრედების დაკავშირებული კომპონენტი). უნდა დავადგინოთ ამ პრობლემის პერიმეტრი.

მაგალითი

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

მიდგომა (მარტივი დათვლა)

პრობლემის ნახვის მარტივი გზაა ის, რომ მხოლოდ მიწის უჯრედები შეუწყობენ ხელს პარამეტრს. პერიმეტრის გამოსათვლელად შეიძლება გაითვალისწინოს მიწის უჯრედი, რომელსაც აქვს ნებისმიერი მხარე, რომელიც გაუზიარებელია სხვა მიწის უჯრედთან. ეს იმიტომ ხდება, რომ თუ მიწის უჯრედი გარკვეულ მხარეს იზიარებს სხვა მიწის უჯრედთან, ეს არ იქნება კუნძულის გარე საზღვარი ქსელში.

კუნძულის პერიმეტრის Leetcode ამოხსნის განხორციელება

C ++ პროგრამა

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

ჯავა პროგრამა

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

კუნძულის პერიმეტრის Leetcode ამოხსნის სირთულის ანალიზი

დროის სირთულე

O (N * M) სადაც N = ქსელის მწკრივების რაოდენობა, M = ქსელის სვეტების რაოდენობა.

სივრცის სირთულე 

O (1) როგორც ცვლადების მუდმივ ადგილს ვიყენებთ.

მიდგომა (ეფექტური დათვლა)

ზემოხსენებული მიდგომისას, ჩვენ ვითვლიდით ხმელეთის უჯრედის გვერდებს, რომელიც ხელს უწყობდა პერიმეტრს მისი ოთხი მეზობლის შემოწმებით. ჩვენ შეგვიძლია გავაუმჯობესოთ ეს, რომ შევამოწმოთ ორი მეზობელი. როდესაც ჩვენ პირდაპირ და ქვემოთ ვიმყოფებით ქსელში, რომ გადავკვეთოთ მას, ჩვენ მხოლოდ მარცხენა და ზემოთ უჯრედების შემოწმება შეგვიძლია მიწის უჯრედში. შეგვიძლია ვივარაუდოთ, რომ ყველა მიწის უჯრედი კუნძულის პერიმეტრში მონაწილეობს '4'. მაგრამ თუ მიწის უჯრედი თავის მხარეს (მხარეებს) სხვა უჯრედს უზიარებს, ჩვენ მას გამოვაკლებთ 2-ს (ერთი მისი საერთო მხარისთვის და ერთიც, რადგან მეორე უჯრედიც იზიარებს მხარეს). ორივე გადაწყვეტილების დროის სირთულე ერთნაირია, მაგრამ გარკვეულწილად ვიხვეწებით ამ მიდგომის მოქმედების საფუძველზე.

კუნძულის პერიმეტრის Leetcode ამოხსნის განხორციელება

C ++ პროგრამა

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

ჯავა პროგრამა

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

კუნძულის პერიმეტრის Leetcode ამოხსნის სირთულის ანალიზი

დროის სირთულე

O (N * M) სადაც N = ქსელის მწკრივების რაოდენობა, M = ქსელის სვეტების რაოდენობა.

სივრცის სირთულე 

O (1) როგორც ცვლადების მუდმივ ადგილს ვიყენებთ.