बेट परिमिती लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन ब्लूमबर्ग फेसबुक Google मायक्रोसॉफ्ट
अरे

समस्या विधान

या समस्येमध्ये, आम्हाला 2-डी अ‍ॅरेच्या स्वरूपात एक ग्रिड दिला जातो. ग्रीड [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

दृष्टीकोन (साधी मोजणी)

समस्या पाहण्याचा सोपा मार्ग म्हणजे केवळ भूमी पेशी पॅरामीटरमध्ये योगदान देतात. परिमितीची गणना करण्यासाठी कोणत्याही अन्य जमीन सेलसह सामायिक नसलेली कोणतीही बाजू असलेली जमीन सेल विचारात घेतली जाऊ शकते. हे असे आहे कारण जर एखाद्या लँड सेलने इतर कोणत्याही लँड सेलबरोबर काही भाग सामायिक केला असेल तर ते ग्रीडमधील बेटाची बाह्य सीमा नसेल.

बेट परिमिती लीटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#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

बेट परिमिती लीटकोड सोल्यूशनचे जटिल विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन * एम) जिथे ग्रिडमधील एन = पंक्तींची संख्या, ग्रीडमधील स्तंभांची संख्या =

स्पेस कॉम्प्लेक्सिटी 

ओ (1) आपण व्हेरिएबल्ससाठी स्थिर जागा वापरत आहोत.

दृष्टीकोन (प्रभावी मोजणी)

वरील पध्दतीमध्ये आम्ही लँड सेलच्या चार बाजूंनी मोजत होतो जे त्या चार शेजार्‍यांना तपासून परिमितीला हातभार लावते. आम्ही फक्त दोन शेजारी तपासून त्यात सुधारणा करू शकतो. ग्रिडमध्ये जाण्यासाठी आम्ही उजवीकडे आणि खाली जाताना, आम्ही फक्त लँड सेलमध्ये डाव्या आणि वरच्या पेशींचा धंदा ठेवू शकतो. आम्ही असे मानू शकतो की प्रत्येक लँड सेल बेटाच्या परिमितीमध्ये '4' चे योगदान देईल. परंतु जर एखाद्या लँड सेलने आपली बाजू कोणत्याही सेलसह सामायिक केली असेल तर आम्ही त्यापासून 2 वजा करू (त्यातील एक सामायिक बाजू आणि दुसरा सेल ज्याप्रमाणे त्याचे भाग सामायिक करतो). दोन्ही सोल्यूशन्सची वेळ जटिलता समान आहे परंतु आम्ही या दृष्टिकोनातून काही प्रमाणात ऑपरेशनच्या कारणास्तव सुधारतो.

बेट परिमिती लीटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#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

बेट परिमिती लीटकोड सोल्यूशनचे जटिल विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन * एम) जिथे ग्रिडमधील एन = पंक्तींची संख्या, ग्रीडमधील स्तंभांची संख्या =

स्पेस कॉम्प्लेक्सिटी 

ओ (1) आपण व्हेरिएबल्ससाठी स्थिर जागा वापरत आहोत.