টাউন জজ লেটকোড সমাধানটি সন্ধান করুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক
চিত্রলেখ

সমস্যা বিবৃতি

এই সমস্যায়, আমাদের 1 জন থেকে n পর্যন্ত লেবেলযুক্ত লোক দেওয়া হয়। আমাদেরও একটি 2 ডি দেওয়া হয় বিন্যাস বিশ্বাস [] [] দেখায় যে এই বিশ্বাস [i] [0] তম লোকেরা আস্থা রাখে [i] [1] তম প্রতিটি 0 <= i <trust.length।
আমাদের এমন একজন ব্যক্তির সন্ধান করতে হবে যে "শহরে বিচারক" যিনি অন্য কোনও লোককে বিশ্বাস করেন না এবং অন্যান্য সমস্ত লোক তাকে বিশ্বাস করে। যদি এ জাতীয় কোনও ব্যক্তি উপস্থিত না থাকে তবে -1 অন্য বিচারককে ফেরত দিন return

উদাহরণ

#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

অভিগমন

আসুন প্রদত্ত দৃশ্যাবলিকে একটি নির্দেশক গ্রাফ হিসাবে বিবেচনা করুন যেখানে ব্যক্তি থেকে এক প্রান্তে একটি প্রান্তটি দেখায় যে একটি বিশ্বস্ত বি।
একজন শহরের বিচারক কারও উপর নির্ভর করেন না, টাউন বিচারকের কোনও বহির্গমন প্রান্ত নেই। অন্য সমস্ত এন -1 ব্যক্তি শহরের বিচারককে এইভাবে বিশ্বাস করে, অন্য সমস্ত ব্যক্তির কাছ থেকে শহরের বিচারকের দিকে মোট এন -1 আগত প্রান্ত।
আমরা আরও বুঝতে পারি যে আগত প্রান্তগুলির সংখ্যা এবং বহির্গামী প্রান্তগুলির সংখ্যার মধ্যে পার্থক্য কেবলমাত্র শহরের বিচারকের জন্য এন -1।
যদি আমরা কোনও সাধারণ ব্যক্তির কথা বলি তবে তিনি অবশ্যই শহরের বিচারককে এইভাবে মিনি (বহির্গমন প্রান্ত) = 1 এবং তারপরে সর্বোত্তম ক্ষেত্রে এমনকি অন্য সমস্ত ব্যক্তি যদি তাকে বিশ্বাস করেন (অবশ্যই শহরে বিচারক তাকে বিশ্বাস করবেন না) এইভাবে সর্বোচ্চ (আগত প্রান্তগুলি) = এন -২।
এই ব্যক্তির জন্য আগত এবং বহির্গামী প্রান্তগুলির মধ্যে সর্বাধিক পার্থক্য হ'ল n-2- (1) = n-3।
এছাড়াও যদি কোনও জনপদে বিচারক না থাকে তবে কোনও ব্যক্তি আগত এবং বহির্গামী প্রান্তগুলির মধ্যে এন -1 পার্থক্য অর্জন করতে পারে না।

এখন, আমাদের মূল কাজটি হ'ল পার্থক্যটি গণনা করা - আগত প্রান্তগুলির সংখ্যা - প্রতিটি ব্যক্তির জন্য বহির্গামী প্রান্তগুলির সংখ্যা। আমরা বিশ্বাসের অ্যারে সারি অনুসারে ট্র্যাভার করে এটি করব।
যে কোনও সারিতে দুটি উপাদান রয়েছে। বাম উপাদান হ'ল কে বিশ্বাস করে এবং ডান উপাদান যাকে বিশ্বাস করে।
সুতরাং বাম উপাদান ডান উপাদান থেকে বহির্গামী প্রান্ত আছে। সুতরাং, বাম উপাদানগুলির জন্য পার্থক্য মান 1 এবং ডান উপাদানটির জন্য হ্রাস পাবে, 1 দ্বারা বৃদ্ধি পাবে।
আমাদের কোডে, আমরা এই কাজের জন্য নেট ট্রাস্টগেইনস অ্যারে ব্যবহার করেছি। এই অ্যারের প্রতিটি সূচী আইথ ব্যক্তির জন্য পার্থক্য মান দেখায়।

আস্থার অ্যারে অনুসরণ করার পরে, আমরা একটি চালাব লুপ 1 থেকে n পর্যন্ত প্রতিটি ব্যক্তির জন্য এবং কোনও ব্যক্তির পার্থক্যের মান = এন -1 আছে কিনা তা পরীক্ষা করুন।
যদি এমন ব্যক্তির সন্ধান পাওয়া যায় তবে আমরা তাকে ফিরিয়ে দেব অন্যথায় আমরা ফিরে যাব -1।

টাউন জজ লেটকোড সমাধানটি সন্ধান করুন

বাস্তবায়ন

টাউন জজ লেটকোড সলিউশন সন্ধানের জন্য সি ++ প্রোগ্রাম

#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

টাউন জজ লেটকোড সমাধানের জন্য জটিলতা বিশ্লেষণ Anal

সময় জটিলতা

ও (সর্বোচ্চ (এন, ট্রাস্ট.সাইজ ()): আমরা আস্থার লুপকে রৈখিকভাবে অবিচ্ছিন্ন করে দিয়েছি এবং প্রতিটি ব্যক্তির 1 থেকে n পর্যন্ত নেট ট্রাস্টজেনগুলি পরীক্ষা করতে অন্য লুপটি আকার n এর।

স্পেস জটিলতা ity 

চালু) : আমরা n + 1 আকারের একটি অ্যারে নেট ট্রাস্টগেইন তৈরি করেছি যাতে স্পেস জটিলতা হে (এন) হয়।