រកដំណោះស្រាយចៅក្រមឡេថិលកូដ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon
ក្រាប

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

នៅក្នុងបញ្ហានេះយើងត្រូវបានផ្តល់ឱ្យមនុស្ស n ដែលមានស្លាកពីលេខ 1 ដល់លេខ n ។ យើងក៏ត្រូវបានគេផ្តល់ឱ្យជាលើកទីពីរ អារេ ការជឿទុកចិត្ត [] [] បង្ហាញថាការជឿទុកចិត្ត [ខ្ញុំ] [០] ប្រជាជនជឿជាក់លើការជឿទុកចិត្ត [ខ្ញុំ] [១] ប្រជាជនសម្រាប់ ០ ម្នាក់ៗ <= ខ្ញុំ <ទុកចិត្ត។
យើងត្រូវរកមនុស្សម្នាក់ជា“ ចៅហ្វាយក្រុង” ដែលមិនទុកចិត្តអ្នកដទៃហើយមនុស្សទាំងអស់ជឿជាក់លើគាត់។ ប្រសិនបើមិនមានមនុស្សបែបនេះទេចូរវិលត្រឡប់មកវិញ -១ ផ្សេងទៀតប្រគល់ចៅក្រមក្រុង។

ឧទាហរណ៍

#1

N = 2, trust = [[1,2]]
2

#2

N = 3, trust = [[1,3],[2,3],[3,1]]
-1

#3

N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
3

វិធីសាស្រ្ត

តោះពិចារណាសេណារីយ៉ូដែលបានផ្តល់ឱ្យជាក្រាហ្វិចមួយដែលគែមពីមនុស្សម្នាក់ទៅខបង្ហាញថាការទុកចិត្តខ។
ចៅហ្វាយក្រុងមិនទុកចិត្តនរណាម្នាក់ទេដូច្នេះចៅហ្វាយក្រុងមិនមានភាពវង្វេងស្មារតីទេ។ មនុស្សទាំងអស់ n-1 ផ្សេងទៀតជឿជាក់លើចៅក្រមក្រុងដូច្នេះគែមចូលថ្មីឆ្ពោះទៅរកចៅក្រមក្រុងពីមនុស្សទាំងអស់។
យើងអាចយល់បន្ថែមទៀតថាភាពខុសគ្នារវាងចំនួនគែមចូលនិងចំនួនគែមខាងក្រៅគឺលេខ ១ សម្រាប់ចៅក្រមក្រុង។
ប្រសិនបើយើងនិយាយអំពីមនុស្សសាមញ្ញនោះគាត់ប្រាកដជាជឿជាក់លើចៅក្រមក្រុងដូច្នេះតិចបំផុត (អ្នកចេញក្រៅ) = ១ នាក់ហើយក្នុងករណីដែលល្អបំផុតបើទោះបីជាមនុស្សផ្សេងទៀតទាំងអស់ជឿជាក់លើគាត់ (ជាការពិតចៅក្រមក្រុងនឹងមិនទុកចិត្តគាត់) ដូច្នេះអតិបរមា (គែមចូល) = n-២ ។
ភាពខុសគ្នាអតិបរមារវាងគែមចូលនិងចេញសម្រាប់មនុស្សនេះគឺ n-2- (1) = n-3 ។
ដូចគ្នានេះផងដែរប្រសិនបើគ្មានចៅក្រមក្រុងទេនោះគ្មាននរណាម្នាក់អាចសម្រេចបាននូវភាពខុសគ្នារវាងលេខចូលនិងចេញទេ។

ឥឡូវនេះភារកិច្ចចម្បងរបស់យើងគឺដើម្បីគណនាភាពខុសគ្នាពោលគឺចំនួនគែមចូល - ចំនួនគែមចេញសម្រាប់មនុស្សម្នាក់ៗ។ យើងនឹងធ្វើដូច្នេះដោយឆ្លងកាត់ការទុកចិត្តលើជួរដែលមានភាពជឿជាក់។
នៅជួរណាមួយមានធាតុពីរ។ ធាតុខាងឆ្វេងគឺជាអ្នកដែលទុកចិត្តនិងធាតុខាងស្តាំដែលធាតុខាងឆ្វេងទុកចិត្ត។
ដូច្នេះធាតុខាងឆ្វេងមានគែមខាងក្រៅទៅធាតុខាងស្តាំ។ ដូច្នេះតម្លៃខុសគ្នាសម្រាប់ធាតុខាងឆ្វេងនឹងថយចុះដោយ ១ ហើយសម្រាប់ធាតុខាងស្តាំកើនឡើង ១ ។
នៅក្នុងលេខកូដរបស់យើងយើងបានប្រើអាតថេតថេកហ្គ្រេនសម្រាប់ការងារនេះ។ សន្ទស្សន៍នីមួយៗនៃអារេនេះបង្ហាញពីតម្លៃខុសគ្នាសំរាប់មនុស្សម្នាក់។

បន្ទាប់ពីឆ្លងកាត់អារេជឿទុកចិត្តយើងនឹងដំណើរការក រង្វិលជុំ សម្រាប់មនុស្សម្នាក់ៗចាប់ពីលេខ ១ ដល់លេខ n ហើយពិនិត្យមើលថាតើមានមនុស្សណាម្នាក់មានតំលៃខុសគ្នា = n-1 ។
ប្រសិនបើមនុស្សបែបនេះត្រូវបានគេរកឃើញបន្ទាប់មកយើងនឹងប្រគល់គាត់វិញយើងនឹងត្រឡប់មកវិញ -1 ។

រកដំណោះស្រាយចៅក្រមឡេថិលកូដ

ការអនុវត្តន៍

កម្មវិធី C ++ សម្រាប់ស្វែងរកចៅក្រមក្រុងឡេធីកូដសូលូសិន

#include <bits/stdc++.h>
using namespace std;
int findJudge(int n, vector<vector<int>>& trust) 
{
    int netTrustGains[n+1];
    memset(netTrustGains, 0, sizeof(netTrustGains));
    for(vector<int>i:trust){
        netTrustGains[i[0]]--;
        netTrustGains[i[1]]++;

    }
    int judge=-1;
    for(int i=1;i<=n;i++){
        if(netTrustGains[i]==n-1){
            judge=i;
        }
    }
    return judge;
}
int main()
{
    int n=3;
    vector<vector<int>>trust
    {
        {1, 3},
        {2, 3}
    };
    cout << findJudge(3,trust);
}
3

កម្មវិធីចាវ៉ាសំរាប់ស្វែងរកដំណោះស្រាយថោនឡេឡេកូដ

import java.util.*;
import java.lang.*;

class Solution
{  
    public static void main(String args[])
    {
        int n = 3;
        int[][]trust = {{1,3},{2,3}};
        System.out.println(findJudge(n,trust));
    }
    public static int findJudge(int n, int[][] trust) 
    {
        int[]netTrustGains=new int[n+1];
        for(int[]i:trust){
            netTrustGains[i[0]]--;
            netTrustGains[i[1]]++;
            
        }
        int judge=-1;
        for(int i=1;i<=n;i++){
            if(netTrustGains[i]==n-1){
                judge=i;
            }
        }
        return judge;
    }
}
3

ការវិភាគស្មុគស្មាញសម្រាប់ស្វែងរកចៅក្រមក្រុងឡេឡេតកូដដំណោះស្រាយ

ស្មុគស្មាញពេលវេលា

O (អតិបរមា (n, trust.size ()))៖ យើងបានឆ្លងកាត់រង្វិលជុំនៃការជឿទុកចិត្តជាលីនេអ៊ែរហើយរង្វិលជុំមួយទៀតគឺមានទំហំ n ដើម្បីពិនិត្យមើល netTrustGains សម្រាប់មនុស្សម្នាក់ៗចាប់ពី 1 ដល់ n ។

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

O (n)៖ យើងបានបង្កើត NetTrustGains ដែលមានទំហំ n + 1 ដូច្នេះទំហំដក O (n) ។