Leetcode 1615: Rango de red máximo -- python campo con beginner campo con algorithm campo con python-3.x campo con programming-challenge camp codereview Relacionados El problema

LeetCode 1615: Maximal Network Rank


4
vote

problema

Español

Estoy publicando una solución para "Rank Maximal Rank" de Leetcode. Si desea revisar, por favor hágalo. ¡Gracias!

problema

Hay una infraestructura de n ciudades con algunos caminos que conectan estas ciudades. Cada carretera [I] = [ai, bi] indica que hay un camino bidireccional entre las ciudades AI y BI.

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

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

Dado el entero N y las carreteras de matriz, devuelva el rango máximo de la red 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    
Original en ingles

I'm posting a solution for LeetCode's "Maximal Network Rank". If you'd like to review, please do so. Thank you!

Problem

There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [ai, bi] indicates that there is a bidirectional road between cities ai and bi.

The network rank of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.

The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.

Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.

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  
              

Lista de respuestas

1
 
vote
vote
La mejor respuesta
 

Evite convertir las estructuras de datos para caden innecesariamente

Solo almacenar tuplas de valores en indegrees en lugar de cadenas:

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

iterar sobre las teclas en indegrees directamente

en esta pieza de código:

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

Lo que usted está diciendo básicamente es: para todos los pares posibles de enteros, verifique si está en indegrees , y si es así, haz algo con él. Eso es muy ineficiente si solo hay pocos elementos en indegrees . ¿Por qué no solo iterar sobre las llaves de indegrees en su lugar? Puede hacerlo con cuerdas, pero luego tiene que analizar cada tecla en dos valores, si almacena las tuplas, en su lugar, se vuelve realmente simple:

  for i, j in indegrees:     ...   
 

Avoid converting data structures to string unnecessarily

Just store tuples of values in indegrees instead of strings:

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

Iterate over the keys in indegrees directly

In this piece of code:

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

What you are basically saying is: for every possible pair of integers, check if it's in indegrees, and if so, do something with it. That's very inefficient if there only few elements in indegrees. Why not just iterate over the keys of indegrees instead? You can do it with strings, but then you have to parse each key back into two values, if you store tuples instead it becomes really simple:

for i, j in indegrees:     ... 
 
 

Relacionados problema

6  Encontrar el siguiente palíndromo de una cadena de números  ( Finding the next palindrome of a number string ) 
Aquí está el problema: Un entero positivo se llama palíndromo si su representación en el El sistema decimal es el mismo cuando se lee de izquierda a dere...

6  Proyecto EULER # 7: 10001ST PRIME  ( Project euler 7 10001st prime ) 
Esta es mi implementación de Project Euler # 7 . ¿Lo he exagerado de nuevo? ¿Hay algo más que debería o no debo hacer? Se ejecuta en 9 milisegundos en mi com...

5  Cuatro cuatro para obtener cualquier número  ( Four fours to get any number ) 
Decidí resolver un problema de Código Golf llamado los cuatro cuatro . Descripción del problema: El Puzzle Four Fours es un popular rompecabezas matemát...

6  Las vocales en una cadena están en orden alfabético  ( Vowels in a string are in alphabetical order ) 
Tarea Escriba una implementación que devuelva si un 99887776655544330 tiene vocales (idioma inglés) en orden alfabético (A-Z) o no. Feedback es mi v...

6  Solución de codewars a "ascensor simple"  ( Codewars solution to simple elevator ) 
Soy nuevo en la programación (menos de un año), y me gustaría mejorar. Resolví un problema en las claquinas y copié tanto mi solución como la solución venci...

5  Proyecto EULER NO. 17: contando letras para escribir los números de 1 a 1000  ( Project euler no 17 counting letters to write the numbers from 1 to 1000 ) 
Soy muy nuevo en la programación y, cierto, estoy avergonzado de compartir mi código para la crítica. Este código funciona y produce la respuesta correcta a l...

4  Encuentre el número de subcadenas de una cadena numérica mayor que una cadena numérica dada  ( Find the number of substrings of a numerical string greater than a given num str ) 
Pregunta: http://qa.geeksforgeeks.org/9744/vinay-queried-interesting -Problem-optimización Entrada La primera línea contiene n que denota la longitud...

56  Proyecto Euler Problema 1 en Python - Múltiples de 3 y 5  ( Project euler problem 1 in python multiples of 3 and 5 ) 
Me gustaría sugerencias para optimizar esta solución de fuerza bruta a problema 1 . El algoritmo actualmente comprueba cada entero entre 3 y 1000. Me gustarí...

1  Codificación de Google Jam: Tienda Credit Java Solution  ( Google code jam store credit java solution ) 
Sería genial si pudiera obtener este código revisado. Me encantaría consejos sobre cómo podría mejorar mi código. problema Recibirá un crédito C en una...

61  Uso de funciones separadas para Project Euler 1  ( Using separate functions for project euler 1 ) 
Comencé a programar con Java y C ++, así que estoy acostumbrado a tener una función "principal" que llama a otras funciones que realizan el trabajo real. En l...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos