द्वीप परिधि Leetcode समाधान


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना ब्लूमबर्ग Facebook गूगल माइक्रोसॉफ्ट
ऐरे

समस्या का विवरण

इस समस्या में, हमें 2-डी सरणी के रूप में एक ग्रिड दिया जाता है। ग्रिड [i] [j] = ० दर्शाता है कि उस बिंदु पर पानी है और ग्रिड [i] [j] = १ भूमि का प्रतिनिधित्व करता है। ग्रिड कोशिकाएँ लंबवत / क्षैतिज रूप से जुड़ी होती हैं लेकिन तिरछे नहीं। दिए गए इनपुट में एक द्वीप (भूमि कोशिकाओं का एक जुड़ा हुआ घटक) है। हमें इस समस्या की परिधि निर्धारित करने की आवश्यकता है।

उदाहरण

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 = स्तंभों की संख्या।

अंतरिक्ष जटिलता 

ओ (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 = स्तंभों की संख्या।

अंतरिक्ष जटिलता 

ओ (1) जैसा कि हम चर के लिए निरंतर स्थान का उपयोग करते हैं।