LeetCode 1615: Peringkat Jaringan Maksimal

Question

Saya memposting solusi untuk "Peringkat Jaringan Maksimal" LeetCode. Jika Anda ingin meninjau, lakukanlah. Terima kasih!

Masalah

Terdapat infrastruktur di n kota dengan sejumlah jalan yang menghubungkan kota-kota tersebut. Setiap jalan [i] = [ai, bi] menunjukkan bahwa terdapat jalan dua arah antara kota ai dan bi.

Peringkat jaringan dari dua kota yang berbeda didefinisikan sebagai jumlah total jalan yang terhubung langsung ke salah satu kota tersebut. Jika sebuah jalan terhubung langsung dengan kedua kota tersebut, itu hanya dihitung sekali.

Peringkat jaringan maksimal dari infrastruktur adalah peringkat jaringan maksimum dari semua pasangan kota yang berbeda.

Dengan adanya bilangan bulat n dan jalan larik, kembalikan peringkat jaringan maksimal dari seluruh infrastruktur.

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

Hindari mengonversi struktur data menjadi string jika tidak perlu

Simpan saja tupel nilai indegreessebagai ganti string:

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

Iterasi tombol indegreessecara langsung

Dalam kode ini:

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

Apa yang pada dasarnya Anda katakan adalah: untuk setiap kemungkinan pasangan bilangan bulat, periksa apakah sudah masuk indegrees, dan jika demikian, lakukan sesuatu dengannya. Itu sangat tidak efisien jika hanya ada sedikit elemen indegrees. Mengapa tidak hanya mengulangi tombol indegreessaja? Anda dapat melakukannya dengan string, tetapi kemudian Anda harus mengurai setiap kunci kembali menjadi dua nilai, jika Anda menyimpan tupel, ini menjadi sangat sederhana:

for i, j in indegrees:
    ...