アイランドペリメーターリートコードソリューション


難易度 簡単に
よく聞かれる Amazon (アマゾン) ブルームバーグ Facebook Googleポリシー マイクロソフト
配列

問題文

この問題では、2次元配列の形式のグリッドが与えられます。 grid [i] [j] = 0はそのポイントに水があることを表し、grid [i] [j] = 1は土地を表します。 グリッドセルは垂直/水平に接続されていますが、斜めには接続されていません。 指定された入力には、正確にXNUMXつの島(ランドセルの連結成分)があります。 この問題の境界を決定する必要があります。

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

アプローチ(単純なカウント)

問題を確認する簡単な方法は、ランドセルのみがパラメータに寄与することです。 周囲長を計算するために、他のランドセルと共有されていない側面を持つランドセルを考慮することができます。 ランドセルが他のランドセルと一部の側面を共有している場合、それはグリッド内の島の外側の境界ではないためです。

Island PerimeterLeetcodeソリューションの実装

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

島周辺のリートコードソリューションの複雑さの分析

時間の複雑さ

O(N * M) ここで、N =グリッド内の行数、M =グリッド内の列数。

スペースの複雑さ 

O(1) 変数に定数スペースを使用するため。

アプローチ(効果的なカウント)

上記のアプローチでは、4つの隣接セルをチェックすることにより、周囲に寄与するランドセルの側面をカウントしていました。 これを改善して、2つのネイバーをチェックするだけにすることができます。 グリッドを右下に移動してトラバースするとき、ランドセルまでの左セルと上セルのチェックのみを維持できます。 すべての陸のセルが島の周囲に「XNUMX」を与えていると推測できます。 ただし、ランドセルが他のセルとそのサイドを共有している場合は、そこからXNUMXを減算します(XNUMXつは共有サイド用、もうXNUMXつは他のセルもサイドを共有しているため)。 両方のソリューションの時間計算量は同じですが、このアプローチでは操作上の理由でいくらか改善されています。

Island PerimeterLeetcodeソリューションの実装

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

島周辺のリートコードソリューションの複雑さの分析

時間の複雑さ

O(N * M) ここで、N =グリッド内の行数、M =グリッド内の列数。

スペースの複雑さ 

O(1) 変数に定数スペースを使用するため。