မြို့တရားသူကြီး Leetcode ဖြေရှင်းချက်ကိုရှာပါ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ
သရုပ်ပြဇယား

ပြProbleနာဖော်ပြချက်

ဒီပြproblemနာမှာ၊ 1 မှ n အထိတံဆိပ်ကပ်ထားသောလူများကိုကျွန်ုပ်တို့အားပေးသည်။ ငါတို့ကိုလည်း 2d ပေးထားတယ် အခင်းအကျင်း ယုံကြည်မှု [] [] က 0 [= i <trust.length] တစ်ခုစီအတွက်လူတွေကိုယုံကြည်မှု [i] [1] th trusts [i] [0] th people ကပြသည်ကိုပြသည်။
အခြားမြို့သူမြို့သားများကိုမယုံ၊ အခြားလူများကသူ့ကိုယုံကြည်သောလူတစ် ဦး အား“ မြို့တွင်းတရားသူကြီး” ကိုကျွန်ုပ်တို့ရှာရမည်။ အကယ်၍ ထိုကဲ့သို့သောပုဂ္ဂိုလ်မရှိခဲ့ပါက -1 ကိုပြန်သွားပါ။

နမူနာ

#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-1 သည်။
ကျွန်ုပ်တို့အနေဖြင့်ဝင်လာသောအစွန်းအရေအတွက်နှင့်ထွက်လာသောအစွန်းအရေအတွက်အကြားခြားနားချက်သည်မြို့တရားသူကြီးအတွက်သာဖြစ်သည်။
ရိုးရိုးရှင်းရှင်းလူတစ်ယောက်အကြောင်းပြောရင်သူကမြို့တရားသူကြီးကိုသေချာပေါက်ယုံမှာသေချာတယ်။ min (အထွက်အစွန်း) = ၁၊ ပြီးတော့အကောင်းဆုံးလူကတော့သူ့ကိုလူတိုင်းယုံကြည်တယ်၊ = n-1 ။
ဤလူအတွက်အဝင်နှင့်အထွက်အနားအကြားအများဆုံးကွာခြားချက်မှာ n-2- (1) = n-3 ဖြစ်သည်။
မြို့ပြတရားသူကြီးမရှိလျှင် ၀ င်နှင့်ထွက်ပေါက်အနားများအကြား n-1 ခြားနားချက်ကိုမည်သူမျှမအောင်မြင်နိုင်ပါ။

ယခုကျွန်ုပ်တို့အဓိကတာ ၀ န်သည်ခြားနားချက်ကိုတွက်ချက်ရန်ဖြစ်သည်။ ယုံကြည်မှုခင်းကျင်းခြင်းအတန်းကိုဖြတ်သန်းခြင်းအားဖြင့်ကျွန်ုပ်တို့ထိုသို့ပြုလုပ်ပါလိမ့်မည်။
မည်သည့်အတန်းတွင်မဆိုဒြပ်စင်နှစ်ခုရှိသည်။ Left element ဆိုတာကယုံကြည်သူနဲ့ညာဖက်က left element ကိုယုံကြည်တဲ့သူ။
ထို့ကြောင့် left element တွင် right element သို့ထွက်သောအစွန်းများရှိသည်။ ထို့ကြောင့်ဘယ်ဘက် element အတွက်ခြားနားမှုတန်ဖိုးသည် ၁ နှင့်ညာဘက်ဒြပ်ထုအတွက် ၁ မှတိုးသွားသည်။
ဒီကုဒ်မှာ netTrustGains ခင်းကျင်းပြီးဒီအလုပ်ကိုလုပ်တယ်။ ဒီခင်းကျင်းခြင်း၏ i တစ်ခုချင်းစီသည် i ith အတွက်ခြားနားချက်တန်ဖိုးကိုပြသည်။

ယုံကြည်မှုခင်းကျင်းမှုကိုဖြတ်သန်းပြီးနောက်၊ ကွင်းဆက် လူတစ် ဦး ချင်းစီအတွက် ၁ မှ n နှင့်လူတစ် ဦး စီ၏ခြားနားချက်တန်ဖိုး = n-1 ရှိမရှိစစ်ဆေးပါ။
အကယ်၍ ထိုကဲ့သို့သောသူကိုတွေ့ရှိပါကအခြားသူကိုပြန်ပို့ပါမည် -1 ။

မြို့တရားသူကြီး Leetcode ဖြေရှင်းချက်ကိုရှာပါ

အကောင်အထည်ဖော်ရေး

မြို့ပြတရားသူကြီး Leetcode Solution ကိုရှာရန် 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

Find the Town Judge Leetcode ဖြေရှင်းချက်အတွက် Java အစီအစဉ်

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

မြို့နယ်တရားသူကြီး Leetcode Solution ကိုရှာဖွေရန်အတွက်ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (max (n, trust.size ())): ယုံကြည်မှုကွင်းဆက်ကိုကျွန်ုပ်တို့ဖြတ်သန်းသွားပြီးနောက်လူတစ် ဦး ချင်းစီအတွက် ၁ မှ n အထိ netTrustGains ကိုစစ်ဆေးရန်နောက်ထပ် loop တစ်ခုသည်အရွယ်အစား n ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု 

အို ()) ကျွန်ုပ်တို့သည် netTrustGains အရွယ်အစား n + 1 ကိုဖွဲ့စည်းထားသည်။ ထို့ကြောင့်ရှုပ်ထွေးမှုအို (n) ။