LeetCode 1615: Maximal Network Rank

Question

Sto pubblicando una soluzione per il "Maximal Network Rank" di LeetCode. Se desideri rivedere, fallo. Grazie!

Problema

Esiste un'infrastruttura di n città con un certo numero di strade che collegano queste città. Ogni strade [i] = [ai, bi] indica che esiste una strada bidirezionale tra le città ai e bi.

Il grado di rete di due città diverse è definito come il numero totale di strade direttamente collegate a ciascuna città. Se una strada è collegata direttamente a entrambe le città, viene conteggiata una sola volta.

Il grado di rete massimo dell'infrastruttura è il grado di rete massimo di tutte le coppie di città diverse.

Dati il ​​numero intero n e le strade della matrice, restituire il rango di rete massimo dell'intera infrastruttura.

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        indegrees = collections.defaultdict(list)
        for i in range(n):
            for a, b in roads:
                if i == a:
                    indegrees[i].append(f'{i}-{b}')
                    indegrees[i].append(f'{b}-{i}')
                if i == b:
                    indegrees[i].append(f'{i}-{a}')
                    indegrees[i].append(f'{a}-{i}')

        max_net = 0
        for i in range(n):
            for j in range(n):
                if f'{i}-{j}' or f'{j}-{i}' in indegrees[i]:
                    net = len(set(indegrees[i] + indegrees[j])) // 2
                    max_net = max(max_net, net)

        return max_net

Answer 1

Evita di convertire inutilmente le strutture dati in stringhe

Memorizza solo tuple di valori indegreesinvece di stringhe:

if i == a:
    indegrees[i].append((i, b))
    indegrees[i].append((b, i))

Scorri indegreesdirettamente le chiavi

In questo pezzo di codice:

for i in range(n):
    for j in range(n):
        if f'{i}-{j}' or f'{j}-{i}' in indegrees[i]:
            ...

Quello che stai dicendo in pratica è: per ogni possibile coppia di numeri interi, controlla se è dentro indegreese, in caso affermativo, fai qualcosa con esso. È molto inefficiente se ci sono solo pochi elementi indegrees. Perché non solo iterare sulle chiavi di indegreesinvece? Puoi farlo con le stringhe, ma poi devi analizzare ogni chiave in due valori, se invece archivi le tuple diventa davvero semplice:

for i, j in indegrees:
    ...