岛屿外围Leetcode解决方案


难度级别 易得奖学金
经常问 亚马逊 彭博 Facebook 谷歌 微软
排列

问题陈述

在这个问题中,我们以二维数组的形式获得了一个网格。 grid [i] [j] = 2表示该点有水,grid [i] [j] = 0表示土地。 网格单元垂直/水平但不对角连接。 给定输入中仅存在一个岛(陆地单元的连接组成部分)。 我们需要确定此问题的范围。

使用案列

grid = {{0,1,0,0},{1,1,1,0},{0,1,0,0},{1,1,0,0}}
16
grid = {{1}}
4

方式(简单计数)

解决此问题的简单方法是仅陆地单元将对参数有所贡献。 为了计算周长,可以考虑具有任何一侧都与任何其他陆地单元共享的陆地单元。 这是因为,如果一个陆地单元格与任何其他陆地单元格共享一侧,那将不会是网格中该岛的外部边界。

Island Perimeter 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(一个为它的共享面,另一单元也为另一面)。 两种解决方案的时间复杂度是相同的,但是我们以这种方法的操作为基础有所改进。

Island Perimeter 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) 因为我们为变量使用恒定空间。