LeetCode 1615: Rango máximo de red

Question

Estoy publicando una solución para el "Rango máximo de red" de LeetCode. Si desea revisarlo, hágalo. ¡Gracias!

Problema

Existe una infraestructura de n ciudades con cierto número de carreteras que conectan estas ciudades. Cada carreteras [i] = [ai, bi] indica que hay una carretera bidireccional entre las ciudades ai y bi.

El rango de la red de dos ciudades diferentes se define como el número total de carreteras conectadas directamente a cualquiera de las ciudades. Si una carretera está conectada directamente con ambas ciudades, solo se cuenta una vez.

El rango de red máximo de la infraestructura es el rango de red máximo de todos los pares de ciudades diferentes.

Dado el número entero ny los caminos de la matriz, devuelve el rango de red máximo de toda la infraestructura.

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

Evite convertir estructuras de datos en cadenas innecesariamente

Simplemente almacene tuplas de valores en indegreeslugar de cadenas:

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

Iterar las claves indegreesdirectamente

En este fragmento de código:

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

Básicamente, lo que estás diciendo es: para cada posible par de números enteros, verifica si está dentro indegreesy, si es así, haz algo con él. Eso es muy ineficiente si solo hay pocos elementos indegrees. ¿Por qué no simplemente iterar sobre las claves de en su indegreeslugar? Puede hacerlo con cadenas, pero luego debe volver a analizar cada clave en dos valores, si almacena tuplas en su lugar, se vuelve realmente simple:

for i, j in indegrees:
    ...