LeetCode 1615: Maximaler Netzwerkrang

Question

Ich veröffentliche eine Lösung für LeetCodes "Maximal Network Rank". Wenn Sie eine Bewertung abgeben möchten, tun Sie dies bitte. Dankeschön!

Problem

Es gibt eine Infrastruktur von n Städten mit einer Anzahl von Straßen, die diese Städte verbinden. Jede Straße [i] = [ai, bi] zeigt an, dass zwischen den Städten ai und bi eine bidirektionale Straße besteht.

Der Netzrang von zwei verschiedenen Städten ist definiert als die Gesamtzahl der direkt verbundenen Straßen zu beiden Städten. Wenn eine Straße direkt mit beiden Städten verbunden ist, wird sie nur einmal gezählt.

Der maximale Netzwerkrang der Infrastruktur ist der maximale Netzwerkrang aller Paare verschiedener Städte.

Geben Sie unter Berücksichtigung der Ganzzahl n und der Array-Straßen den maximalen Netzwerkrang der gesamten Infrastruktur zurück.

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

Vermeiden Sie es, Datenstrukturen unnötig in Zeichenfolgen zu konvertieren

Speichern Sie einfach Tupel mit Werten indegreesanstelle von Zeichenfolgen:

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

Iterieren Sie indegreesdirekt über die Schlüssel

In diesem Code:

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

Was Sie im Grunde sagen, ist: Überprüfen Sie für jedes mögliche Paar von Ganzzahlen, ob es vorhanden ist indegrees, und tun Sie in diesem Fall etwas damit. Das ist sehr ineffizient, wenn nur wenige Elemente vorhanden sind indegrees. Warum nicht einfach indegreesstattdessen über die Tasten von iterieren ? Sie können es mit Zeichenfolgen tun, aber dann müssen Sie jeden Schlüssel wieder in zwei Werte zerlegen. Wenn Sie stattdessen Tupel speichern, wird es wirklich einfach:

for i, j in indegrees:
    ...