ວິທີແກ້ໄຂ Leetcode ຂອງເກາະ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon Bloomberg ເຟສບຸກ ກູໂກ Microsoft
Array

ຖະແຫຼງການບັນຫາ

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບຕາຂ່າຍໄຟຟ້າໃນຮູບແບບຂອງ 2-D array. ຕາຂ່າຍໄຟຟ້າ [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

ວິທີການ (ການນັບງ່າຍໆ)

ວິທີງ່າຍໆທີ່ຈະເຫັນບັນຫາແມ່ນມີພຽງແຕ່ຈຸລັງທີ່ດິນເທົ່ານັ້ນທີ່ຈະປະກອບສ່ວນກັບພາລາມິເຕີ. ຫ້ອງທີ່ດິນທີ່ຢູ່ເບື້ອງໃດທີ່ບໍ່ສາມາດແບ່ງປັນກັບຫ້ອງດິນອື່ນໆສາມາດ ຄຳ ນຶງເຖິງເພື່ອຄິດໄລ່ຂອບເຂດ. ມັນເປັນເພາະວ່າຖ້າຫ້ອງດິນແບ່ງປັນບາງສ່ວນກັບຫ້ອງດິນອື່ນໆ, ນັ້ນຈະບໍ່ແມ່ນເຂດແດນນອກຂອງເກາະໃນຕາຂ່າຍໄຟຟ້າ.

ການຈັດຕັ້ງປະຕິບັດວິທີແກ້ໄຂເກາະເທເລີ Leimeter

ໂຄງການ 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 Program

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

ການວິເຄາະຄວາມສັບສົນຂອງວິທີແກ້ບັນຫາຂອງເກາະ Perimeter Leetcode

ຄວາມສັບສົນເວລາ

O (N * M) ບ່ອນທີ່ N = ຈຳ ນວນແຖວໃນຕາຂ່າຍໄຟຟ້າ, M = ຈຳ ນວນຖັນໃນຕາຂ່າຍໄຟຟ້າ.

ຄວາມສັບສົນໃນອະວະກາດ 

O (1) ດັ່ງທີ່ພວກເຮົາໃຊ້ພື້ນທີ່ຄົງທີ່ ສຳ ລັບຕົວແປຕ່າງໆ.

ວິທີການ (ການນັບປະສິດທິຜົນ)

ໃນວິທີການຂ້າງເທິງນີ້, ພວກເຮົາ ກຳ ລັງນັບສອງຂ້າງຂອງຫ້ອງທີ່ດິນເຊິ່ງປະກອບສ່ວນເຂົ້າໃນຂອບເຂດໂດຍການກວດເບິ່ງເພື່ອນບ້ານ 4 ຄົນ. ພວກເຮົາສາມາດປັບປຸງສິ່ງນັ້ນໄດ້ພຽງແຕ່ກວດກາເພື່ອນບ້ານສອງຄົນ. ໃນຂະນະທີ່ພວກເຮົາລົງຂວາແລະລົງໃນຕາຂ່າຍໄຟຟ້າເພື່ອຂ້າມຜ່ານ, ພວກເຮົາພຽງແຕ່ສາມາດເກັບເຊັກຂອງຈຸລັງທີ່ຢູ່ເບື້ອງຊ້າຍແລະຂຶ້ນກັບຫ້ອງດິນ. ພວກເຮົາສາມາດສົມມຸດໄດ້ວ່າທຸກໆຫ້ອງທີ່ດິນປະກອບສ່ວນ '2' ໃນຂອບເຂດຂອງເກາະ. ແຕ່ຖ້າຫ້ອງດິນແບ່ງປັນກັບຫ້ອງອື່ນ, ພວກເຮົາຈະຫັກ XNUMX ຈາກມັນ (ອັນ ໜຶ່ງ ສຳ ລັບຫ້ອງທີ່ຢູ່ຮ່ວມກັນແລະອີກອັນ ໜຶ່ງ ຄືວ່າຫ້ອງອື່ນໆແບ່ງປັນຢູ່ເບື້ອງດຽວກັນ). ຄວາມສັບສົນຂອງເວລາຂອງການແກ້ໄຂທັງສອງແມ່ນຄືກັນແຕ່ພວກເຮົາປັບປຸງບາງຢ່າງບົນພື້ນຖານການ ດຳ ເນີນງານໃນວິທີການນີ້.

ການຈັດຕັ້ງປະຕິບັດວິທີແກ້ໄຂເກາະເທເລີ Leimeter

ໂຄງການ 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 Program

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

ການວິເຄາະຄວາມສັບສົນຂອງວິທີແກ້ບັນຫາຂອງເກາະ Perimeter Leetcode

ຄວາມສັບສົນເວລາ

O (N * M) ບ່ອນທີ່ N = ຈຳ ນວນແຖວໃນຕາຂ່າຍໄຟຟ້າ, M = ຈຳ ນວນຖັນໃນຕາຂ່າຍໄຟຟ້າ.

ຄວາມສັບສົນໃນອະວະກາດ 

O (1) ດັ່ງທີ່ພວກເຮົາໃຊ້ພື້ນທີ່ຄົງທີ່ ສຳ ລັບຕົວແປຕ່າງໆ.