Kasabanın güvenilen yargıcı
Görev tanımı
Problem
Bir kasabada 1'den n'ye kadar etiketlenmiş n kişi ve a, b çiftinin a'nın b'ye güvendiği anlamına geldiği bir çift listesi var. Tam olarak bir kişi yargıç olabilir: yargıç kimseye güvenmez ve kasabadaki diğer herkes yargıca güvenir. Yargıcın etiketini döndür; böyle biri yoksa -1 döndür.
Örnekler
Input: n = 2, trust = [[1, 2]]
Output: 2
Neden: 2 numaralı kişi kimseye güvenmiyor ve diğer tek kişi ona güveniyor
Input: n = 3, trust = [[1, 3], [2, 3], [3, 1]]
Output: -1
Neden: 3 numaralı kişiye herkes güveniyor ama o da birine güveniyor
Input: n = 1, trust = []
Output: 1
Neden: edge case: tek sakin iki kuralı da boş yere sağlıyor
İpuçları
0 / 3
Burada yol arama. İki kural da nereye gidebileceğinle değil, bir kişiye kaç ok değdiğiyle ilgili.
Her çift a'dan bir ok çıkarıp b'ye sokar. Kişi başına gelen ve giden okları saymak iki kuralı da test etmeye yeter.
Kişi başına tek bir sayı tut: birisi ona güvendiğinde bir ekle, o birine güvendiğinde bir çıkar. Sayısı nüfusun bir eksiğine ulaşabilen tek kişi yargıçtır; bu değeri ara, kimsede yoksa başarısızlık bildir.
- Hedef zaman
- O(n + p)
- Hedef alan
- O(n)
Kısıtlar
- people are labelled 1 to n
- at most one person can be the judge
Çözüm
İki kural da derece koşuludur, bu yüzden kişi başına tek bir sayım ikisini birlikte cevaplar: güvenilmek bir ekler, güvenmek bir çıkarır. Yalnız diğer n-1 kişinin hepsinin güvendiği ve kimseye güvenmeyen biri n-1 puanına ulaşabilir, çünkü giden herhangi bir güven onu bu tavanın altına düşürürdü. Çiftler üzerinde bir geçiş ve kişiler üzerinde bir geçiş yeter. p çift için zaman O(n + p), alan O(n).
def find_judge(n, trust):
score = [0] * (n + 1) # times trusted minus times trusting
for a, b in trust:
score[a] -= 1
score[b] += 1
for person in range(1, n + 1):
if score[person] == n - 1: # trusted by all the others, trusts nobody
return person
return -1
print(find_judge(2, [[1, 2]])) # -> 2
print(find_judge(3, [[1, 3], [2, 3], [3, 1]])) # -> -1
print(find_judge(1, [])) # -> 1Kodda değil de fikirde mi takıldın? Graf temelleri bunu anlatıyor.