දූපත් පරිමිතිය ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන් බ්ලූම්බර්ග් ෆේස්බුක් ගූගල් මයික්රොසොෆ්ට්
අරා

ගැටළු ප්රකාශය

මෙම ගැටළුවේදී අපට 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

ප්‍රවේශය (සරල ගණන් කිරීම)

ගැටළුව බැලීමට ඇති සරලම ක්‍රමය නම් පරාමිතියට දායක වන්නේ ඉඩම් සෛල පමණි. පරිමිතිය ගණනය කිරීම සඳහා වෙනත් ඕනෑම භූමි කොටුවක් සමඟ බෙදා නොගත් ඕනෑම පැත්තක් ඇති ඉඩම් සෛලයක් සැලකිල්ලට ගත හැකිය. එයට හේතුව ඉඩම් සෛලයක් වෙනත් භූමි කෝෂයක් සමඟ යම් පැත්තක් බෙදා ගන්නේ නම් එය විදුලිබල පද්ධතියේ දිවයිනේ පිටත මායිම නොවන බැවිනි.

දූපත් පරිමිතිය ලීට්කෝඩ් විසඳුම ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#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

දූපත් පරිමිතිය ලීට්කෝඩ් විසඳුමේ සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (එන් * එම්) එහිදී N = ජාලකයේ පේළි ගණන, M = ජාලකයේ ඇති තීරු ගණන.

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (1) අපි විචල්යයන් සඳහා නියත අවකාශය භාවිතා කරන බැවින්.

ප්‍රවේශය (Count ලදායී ගණනය කිරීම)

ඉහත ප්‍රවේශයේදී, අප අසල්වැසි සිව්දෙනා පරික්ෂා කිරීමෙන් පරිමිතියට දායක වන ඉඩම් සෛලයක පැති ගණන් කරමින් සිටියෙමු. අසල්වැසියන් දෙදෙනෙකු පරීක්ෂා කිරීම සඳහා අපට එය වැඩි දියුණු කළ හැකිය. විදුලිබල පද්ධතියට ගමන් කිරීම සඳහා අප දකුණට සහ පහළට ගමන් කරන විට, අපට කළ හැක්කේ වම් සහ ඉහළ සෛල පරීක්ෂා කිරීම පමණි. සෑම භූමි කෝෂයක්ම දිවයිනේ පරිමිතියට '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

දූපත් පරිමිතිය ලීට්කෝඩ් විසඳුමේ සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (එන් * එම්) එහිදී N = ජාලකයේ පේළි ගණන, M = ජාලකයේ ඇති තීරු ගණන.

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (1) අපි විචල්යයන් සඳහා නියත අවකාශය භාවිතා කරන බැවින්.