ຊອກຫາວິທີແກ້ໄຂຕົວເມືອງ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon
ເສັ້ນສະແດງ

ຖະແຫຼງການບັນຫາ

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບການໃຫ້ຄົນ n ຕິດສະຫລາກຕັ້ງແຕ່ 1 ເຖິງນ. ພວກເຮົາຍັງໄດ້ຮັບ 2d array ຄວາມໄວ້ວາງໃຈ [] [] ສະແດງໃຫ້ເຫັນວ່າຄວາມໄວ້ວາງໃຈ [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

ວິທີການ

ໃຫ້ພິຈາລະນາສະຖານະການທີ່ໄດ້ກ່າວມາເປັນເສັ້ນສະແດງໂດຍກົງໃນຂອບຂອງບຸກຄົນ a ເຖິງ b ສະແດງໃຫ້ເຫັນວ່າຄວາມໄວ້ວາງໃຈຂ.
ຜູ້ພິພາກສາເມືອງບໍ່ໄວ້ວາງໃຈຜູ້ໃດເລີຍ, ດັ່ງນັ້ນ, ຜູ້ພິພາກສາເມືອງບໍ່ມີຂອບເຂດທີ່ອອກໄປ. ບຸກຄົນອື່ນ n-1 ອື່ນໆໄວ້ວາງໃຈຜູ້ພິພາກສາເມືອງດັ່ງນັ້ນ, ຜູ້ເຂົ້າຮອບຕັດສິນຕົວເມືອງທັງ ໝົດ ຈາກ n-1 ມາຈາກຜູ້ອື່ນ.
ພວກເຮົາສາມາດເຂົ້າໃຈຕື່ມອີກວ່າຄວາມແຕກຕ່າງລະຫວ່າງ ຈຳ ນວນຂາເຂົ້າແລະ ຈຳ ນວນຂອບອອກແມ່ນ n-1 ສຳ ລັບຜູ້ພິພາກສາເມືອງເທົ່ານັ້ນ.
ຖ້າພວກເຮົາເວົ້າກ່ຽວກັບຄົນ ທຳ ມະດາແລ້ວລາວຈະໄວ້ວາງໃຈຜູ້ພິພາກສາເມືອງແນ່ນອນສະນັ້ນ (ຂອບເຂດທີ່ອອກ) = 1 ແລະໃນກໍລະນີທີ່ດີທີ່ສຸດເຖິງແມ່ນວ່າຄົນອື່ນໆຈະໄວ້ວາງໃຈລາວ (ແນ່ນອນວ່າຜູ້ພິພາກສາເມືອງຈະບໍ່ໄວ້ວາງໃຈລາວ) ດັ່ງນັ້ນສູງສຸດ (ຂາເຂົ້າ) = n-2.
ຄວາມແຕກຕ່າງສູງສຸດລະຫວ່າງຂາເຂົ້າແລະຂາອອກ ສຳ ລັບຄົນນີ້ແມ່ນ n-2- (1) = n-3.
ເຊັ່ນດຽວກັນຖ້າບໍ່ມີຜູ້ພິພາກສາເມືອງຫຼັງຈາກນັ້ນບໍ່ມີຜູ້ໃດສາມາດບັນລຸຄວາມແຕກຕ່າງລະຫວ່າງ n-1 ລະຫວ່າງ ຈຳ ນວນຂາເຂົ້າແລະຂາອອກ.

ດຽວນີ້, ໜ້າ ທີ່ຫຼັກຂອງພວກເຮົາແມ່ນການຄິດໄລ່ຄວາມແຕກຕ່າງກັນເຊັ່ນ: ຈຳ ນວນຂາເຂົ້າ - ຈຳ ນວນຂອບຂອງລາຍຈ່າຍ ສຳ ລັບແຕ່ລະຄົນ. ພວກເຮົາຈະເຮັດແນວນັ້ນໂດຍຜ່ານການປ່ຽນເສັ້ນທາງຄວາມໄວ້ວາງໃຈຕິດຕໍ່ກັນ.
ໃນແຖວໃດກໍ່ຕາມ, ມີສອງອົງປະກອບ. ອົງປະກອບຊ້າຍແມ່ນຜູ້ທີ່ໄວ້ວາງໃຈແລະອົງປະກອບທີ່ຖືກຕ້ອງແມ່ນຜູ້ທີ່ອົງປະກອບຊ້າຍໄວ້ວາງໃຈ.
ອົງປະກອບຊ້າຍດັ່ງນັ້ນຈຶ່ງມີສ່ວນປະກອບທີ່ຖືກຕ້ອງ. ດັ່ງນັ້ນ, ຄ່າຄວາມແຕກຕ່າງ ສຳ ລັບອົງປະກອບເບື້ອງຊ້າຍຈະຫຼຸດລົງ 1 ແລະ ສຳ ລັບອົງປະກອບທີ່ຖືກຕ້ອງ, ເພີ່ມຂື້ນ 1
ໃນລະຫັດຂອງພວກເຮົາ, ພວກເຮົາໄດ້ ນຳ ໃຊ້ອາຄານ NetTrustGains ສຳ ລັບວຽກນີ້. ແຕ່ລະດັດຊະນີ i ຂອງອາເລນີ້ສະແດງໃຫ້ເຫັນມູນຄ່າຄວາມແຕກຕ່າງ ສຳ ລັບບຸກຄົນ ith.

ຫຼັງຈາກຜ່ານອາຄານຄວາມໄວ້ວາງໃຈ, ພວກເຮົາຈະແລ່ນ a loop ສຳ ລັບແຕ່ລະຄົນຈາກ 1 ເຖິງ n ແລະກວດເບິ່ງວ່າມີບຸກຄົນໃດ ໜຶ່ງ ມີຄ່າທີ່ແຕກຕ່າງກັນ = n-1.
ຖ້າພົບຄົນດັ່ງກ່າວແລ້ວພວກເຮົາຈະສົ່ງຄືນລາວອີກພວກເຮົາຈະກັບຄືນ -1.

ຊອກຫາວິທີແກ້ໄຂຕົວເມືອງ Leetcode

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ສຳ ລັບຊອກຫາຜູ້ພິພາກສາເມືອງ Leetcode Solution

#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

Java Program ສຳ ລັບຊອກຫາຜູ້ພິພາກສາ Town Leetcode Solution

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

ຄວາມສັບສົນເວລາ

O (ສູງສຸດ (n, trust.size ())): ພວກເຮົາໄດ້ຜ່ານວົງຈອນຄວາມໄວ້ວາງໃຈເປັນໄລຍະແລະອີກວົງຈອນ ໜຶ່ງ ທີ່ມີຂະ ໜາດ n ເພື່ອກວດສອບ netTrustGains ສຳ ລັບແຕ່ລະຄົນຈາກ 1 ເຖິງ n.

ຄວາມສັບສົນໃນອະວະກາດ 

ໂອ (n): ພວກເຮົາໄດ້ສ້າງ NetTrustGains ຂບວນທີ່ມີຂະ ໜາດ n + 1 ດັ່ງນັ້ນຈຶ່ງມີຄວາມສັບສົນທາງຊ່ອງ (O).