ദ്വീപ് ചുറ്റളവ് ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ബ്ലൂംബർഗ് ഫേസ്ബുക്ക് ഗൂഗിൾ മൈക്രോസോഫ്റ്റ്
അറേ

പ്രശ്നം പ്രസ്താവന

ഈ പ്രശ്‌നത്തിൽ, ഞങ്ങൾക്ക് 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

ദ്വീപ് ചുറ്റളവ് ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N * M) ഇവിടെ ഗ്രിഡിലെ N = വരികളുടെ എണ്ണം, M = ഗ്രിഡിലെ നിരകളുടെ എണ്ണം.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (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

ദ്വീപ് ചുറ്റളവ് ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N * M) ഇവിടെ ഗ്രിഡിലെ N = വരികളുടെ എണ്ണം, M = ഗ്രിഡിലെ നിരകളുടെ എണ്ണം.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (1) വേരിയബിളുകൾക്കായി ഞങ്ങൾ സ്ഥിരമായ ഇടം ഉപയോഗിക്കുന്നതിനാൽ.