ដំណោះស្រាយកោះឡេត្រេយឡេស៊្រី


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ទីភ្នាក់ងារ Bloomberg Facebook ក្រុមហ៊ុន google ក្រុមហ៊ុន Microsoft
អារេ

សេចក្តីថ្លែងការណ៍បញ្ហា។

នៅក្នុងបញ្ហានេះយើងត្រូវបានផ្តល់ក្រឡាចត្រង្គជាទម្រង់អារេ 2 ឌី។ ក្រឡាចត្រង្គ [ខ្ញុំ] [ច] = ០ តំណាងឱ្យទឹកនៅចំណុចនោះហើយក្រឡាចត្រង្គ [i] [ច] = ១ តំណាងឱ្យដី។ ក្រឡាក្រឡាចត្រង្គត្រូវបានតភ្ជាប់បញ្ឈរ / ផ្ដេកប៉ុន្តែមិនមានអង្កត់ទ្រូងទេ។ ពិតជាមានកោះមួយ (សមាសធាតុផ្សំនៃកោសិកាដី) នៅក្នុងធាតុបញ្ចូលដែលបានផ្តល់។ យើងត្រូវកំណត់បរិវេណនៃបញ្ហានេះ។

ឧទាហរណ៍

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

កម្មវិធីចាវ៉ា

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 = ចំនួនជួរឈរនៅក្នុងបណ្តាញអគ្គិសនី។

ភាពស្មុគស្មាញនៃលំហ 

ឱ (១) ដូចដែលយើងប្រើទំហំថេរសម្រាប់អថេរ។

វិធីសាស្រ្ត (ការរាប់មានប្រសិទ្ធិភាព)

នៅក្នុងវិធីសាស្រ្តខាងលើយើងកំពុងរាប់ផ្នែកម្ខាងនៃកោសិកាដីដែលរួមចំណែកដល់បរិវេណដោយពិនិត្យមើលអ្នកជិតខាងទាំងបួន។ យើងអាចធ្វើឱ្យប្រសើរឡើងដើម្បីគ្រាន់តែពិនិត្យមើលអ្នកជិតខាងពីរនាក់។ នៅពេលដែលយើងចុះក្រោមនិងក្រឡាចត្រង្គដើម្បីឆ្លងកាត់វាយើងគ្រាន់តែអាចពិនិត្យកោសិកាខាងឆ្វេងនិងឡើងទៅកោសិកាដីប៉ុណ្ណោះ។ យើងអាចសន្មតបានថារាល់កោសិកាដីធ្លីបានចូលរួមចំណែក '៤' ដល់បរិវេណកោះ។ ប៉ុន្តែប្រសិនបើកោសិកាដីចែកចំណែករបស់ខ្លួនជាមួយកោសិកាផ្សេងទៀតយើងនឹងដកលេខ ២ ពីវា (មួយសម្រាប់ចំណែករួមរបស់វានិងមួយទៀតជាក្រឡាផ្សេងទៀតចែកមួយចំហៀងផងដែរ) ។ ភាពស្មុគស្មាញនៃពេលវេលានៃដំណោះស្រាយទាំងពីរគឺដូចគ្នាប៉ុន្តែយើងធ្វើឱ្យប្រសើរឡើងនូវមូលដ្ឋាននៃប្រតិបត្តិការនៅក្នុងវិធីសាស្រ្តនេះ។

ការអនុវត្តដំណោះស្រាយកោះឡេត្រេយឡេស៊្រី

កម្មវិធី 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;
}

កម្មវិធីចាវ៉ា

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 = ចំនួនជួរឈរនៅក្នុងបណ្តាញអគ្គិសនី។

ភាពស្មុគស្មាញនៃលំហ 

ឱ (១) ដូចដែលយើងប្រើទំហំថេរសម្រាប់អថេរ។