Решение за островски периметар на лек код  


Ниво на тешкотија Лесно
Често прашувано во Амазон Блумберг Facebook Google Мајкрософт
алгоритми Низа кодирање интервју интервју подготви LeetCode LeetCodeSolutions

Изјава за проблем  

Во овој проблем, ни е дадена мрежа во форма на 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

Пристап (едноставно броење)  

Едноставен начин да се согледа проблемот е дека само копнените ќелии ќе придонесат за параметарот. Земјината ќелија која има која било страна што не е споделена со која било друга копнена ќелија може да се земе предвид за да се пресмета периметарот. Тоа е затоа што ако копнената ќелија дели некоја страна со која било друга копнена ќелија, тоа нема да биде надворешната граница на островот во мрежата.

Имплементација на решение за островски периметар на леткод

Програма 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;
}

Програма за Java

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) како што користиме постојан простор за променливи.

Пристап (ефективно броење)  

Во горенаведениот пристап, ги броевме страните на копнената копна што придонесува кон периметарот, проверувајќи ги нејзините четири соседи. Можеме да го подобриме тоа само да провериме два соседи. Додека се наоѓаме десно и надолу во мрежата за да ја поминеме, можеме да извршиме само проверка на левите и горе клетките во копнената ќелија. Можеме да претпоставиме дека секоја копнена ќелија придонесува со '4' на периметарот на островот. Но, ако копнената ќелија ги сподели своите страни со кои било друга ќелија, ќе одземеме 2 од неа (една за нејзината заедничка страна и една, бидејќи другата ќелија дели и една страна). Временската сложеност на обете решенија е иста, но ние во одреден степен се подобруваме врз основа на работењето.

Имплементација на решение за островски периметар на леткод

Програма 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;
}

Програма за Java

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) бидејќи користиме постојан простор за променливи.