Островен периметър Leetcode решение  


Ниво на трудност Лесно
Често задавани в Амазонка Bloomberg Facebook Google Microsoft
алгоритми Array кодиране Интервю интерпретация LeetCode LeetCodeSolutions

Декларация за проблема  

В този проблем ни е дадена решетка под формата на 2-D масив. решетка [i] [j] = 0 представлява, че в тази точка има вода, а мрежа [i] [j] = 1 представлява земя. Решетките са свързани вертикално/хоризонтално, но не диагонално. Има точно един остров (a свързан компонент на сухоземни клетки) в дадения вход. Трябва да определим периметъра на този проблем.

Пример

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;
}

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

Анализ на сложността на решението на Leetcode на периметъра на острова

Сложност във времето

O (N * M) където N = брой редове в мрежата, M = брой колони в мрежата.

Вижте също
Попълване на следващи десни указатели във всеки възел

Сложност на пространството 

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

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

Анализ на сложността на решението на Leetcode на периметъра на острова

Сложност във времето

O (N * M) където N = брой редове в мрежата, M = брой колони в мрежата.

Вижте също
Брой на най-дълго нарастващите последствия

Сложност на пространството 

O (1) тъй като използваме постоянно пространство за променливи.