O juiz de confiança da cidade
A missão
Problema
Uma cidade tem n pessoas rotuladas de 1 a n e uma lista de pares em que o par a, b significa que a confia em b. Exatamente uma pessoa pode ser o juiz: o juiz não confia em ninguém, e todas as outras pessoas da cidade confiam no juiz. Retorne o rótulo do juiz, ou -1 quando essa pessoa não existir.
Exemplos
Input: n = 2, trust = [[1, 2]]
Output: 2
Por quê: a pessoa 2 não confia em ninguém e recebe a confiança da única outra pessoa
Input: n = 3, trust = [[1, 3], [2, 3], [3, 1]]
Output: -1
Por quê: a pessoa 3 recebe a confiança de todos, mas também confia em alguém
Input: n = 1, trust = []
Output: 1
Por quê: edge case: o único morador satisfaz as duas regras trivialmente
Dicas
0 / 3
Não procure caminhos aqui. As duas regras falam de quantas setas tocam uma pessoa, não de para onde dá para ir.
Cada par manda uma seta saindo de a e entrando em b. Contar as setas de entrada e de saída de cada pessoa basta para testar as duas regras.
Guarde um único número por pessoa: some um quando ela recebe confiança e subtraia um quando ela confia em alguém. O juiz é a única pessoa cujo número pode chegar a um a menos que a população; procure esse valor e informe falha se ninguém o tiver.
- Tempo-alvo
- O(n + p)
- Espaço-alvo
- O(n)
Restrições
- people are labelled 1 to n
- at most one person can be the judge
Solução
As duas regras são condições de grau, então uma contagem por pessoa responde às duas ao mesmo tempo: receber confiança soma um e confiar subtrai um. Só alguém que recebe a confiança dos outros n-1 sem confiar em ninguém chega a uma pontuação de n-1, porque qualquer confiança de saída a derrubaria abaixo desse teto. Basta uma passada pelos pares e outra pelas pessoas. O tempo é O(n + p) para p pares, e o espaço é 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, [])) # -> 1Travou na ideia, e não no código? O básico de grafos explica isso.