የከተማው ዳኛ የሌትኮድ መፍትሄን ይፈልጉ  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን
ስልተ ምስጠራ ግራፍ ቃለ መጠይቅ interviewprep ሊት ኮድ LeetCodeSolutions

የችግሩ መግለጫ  

በዚህ ችግር ውስጥ እኛ ከ 1 ወደ n የተሰየሙ n ሰዎች ተሰጠን ፡፡ እኛ ደግሞ 2 ዲ ተሰጥቶናል ደርድር መተማመን [] [] የሚያሳየው እምነት [i] [0] ኛ ሰዎች በእምነት [i] [1] ኛ ሰዎች ለእያንዳንዱ 0 <= i <trust.length.
እኛ በማንም ሰው የማይተማመን እና ሌሎች ሁሉም ሰዎች በእርሱ የሚያምኑትን “የከተማ ዳኛ” መፈለግ አለብን ፡፡ እንደዚህ ያለ ሰው ከሌለ ከዚያ ይመለሱ -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 ገቢ ጠርዝ ፡፡
በመጪዎቹ ጠርዞች ቁጥር እና በወጪ ጠርዞች ብዛት መካከል ያለው ልዩነት ለከተማ ዳኛ ብቻ n-1 መሆኑን እንገነዘባለን ፡፡
ስለ አንድ ቀላል ሰው ከተነጋገርን ታዲያ እሱ በእውነቱ የከተማ ዳኛን ያምናሉ (የወጪ ጠርዞች) = 1 እና በጥሩ ሁኔታ ምንም እንኳን ሁሉም ሰው ቢተማመንበት (በእርግጥ የከተማው ዳኛ አያምነውም) ስለሆነም ከፍተኛ (የሚመጡ ጠርዞች) = n-2 ፡፡
ለዚህ ሰው በመጪ እና በወጪ ጠርዞች መካከል ያለው ከፍተኛ ልዩነት n-2- (1) = n-3 ነው ፡፡
እንዲሁም የከተማ ዳኛ ከሌለ በመጪ እና በወጪ ጠርዞች ቁጥር መካከል የ n-1 ልዩነት ማንም ሰው ሊያሳካ አይችልም።

ተመልከት
ሁለት ሕብረቁምፊ ድርድር ተመጣጣኝ የሌቲኮድ መፍትሔ መሆኑን ያረጋግጡ

አሁን ዋናው ሥራችን ልዩነቱን ማለትም የገቢ ጠርዞችን ቁጥር ማስላት ነው - ለእያንዳንዱ ሰው የወጪ ጠርዞች ቁጥር ፡፡ እኛ የእምነት አደራደር ረድፍ-ጥበበኛን በማለፍ እናደርጋለን።
በማንኛውም ረድፍ ውስጥ ሁለት አካላት አሉ ፡፡ የግራ አካል የሚያምነው ሲሆን የቀኝ አካል ደግሞ የግራው አካል ይታመናል።
ስለዚህ የግራ አካል ከጫፍ እስከ ቀኝ አካል ድረስ ይወጣል። ስለሆነም ለግራ አካል ልዩነት እሴት በ 1 ይቀንሳል እና ለትክክለኛው አካል በ 1 ይጨምራል።
በእኛ ኮድ ውስጥ ለዚህ ተግባር netTrustGains ድርድርን ተጠቅመናል ፡፡ የዚህ ድርድር እያንዳንዱ መረጃ ጠቋሚ i ለእራሱ ሰው ልዩነትን ያሳያል ፡፡

የእምነት ድርድርን ካለፍን በኋላ ሀ መዞር ለእያንዳንዱ ሰው ከ 1 እስከ 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

የከተማው ዳኛ ሌትኮድ መፍትሔ ለማግኘት ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (ከፍተኛ (n ፣ trust.size ())): እኛ የእምነት ቀለበቱን በተዘዋዋሪ ተላልፈናል እና ሌላ ዙር መጠኑን n ነው 1 ከ XNUMX ወደ n የተጣራ ኔትዎርኪ ግኝቶችን ለመፈተሽ።

ተመልከት
ራቢን ካርፕ አልጎሪዝም

የቦታ ውስብስብነት 

ኦ (n): የመጠን n + 1 መጠን የድርድር netTrustGains ፈጥረናል ስለዚህ የቦታ ውስብስብነት O (n)።

2