[LeetCode] 0133. Clonar gráfico

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Medio

Dada una referencia de un nodo en un conectado gráfico no dirigido.

Devolver un copia profunda (clon) del gráfico.

Cada nodo del gráfico contiene un valor (entero) y una lista (Lista[Nodo]) de sus vecinos.

clase Nodo { public int val; lista pública vecinos; }

Formato de caso de prueba:

Para simplificar, el valor de cada nodo es el mismo que el índice del nodo (indexado en 1). Por ejemplo, el primer nodo con. valor==1, el segundo nodo con valor==2, y así sucesivamente. El gráfico se representa en el caso de prueba mediante una lista de adyacencia.

Una lista de adyacencia es una colección de desordenado liza se utiliza para representar un gráfico finito. Cada lista describe el conjunto de vecinos de un nodo en el gráfico.

El nodo dado siempre será el primer nodo con valor=1Debes devolver el copia del nodo dado como referencia al gráfico clonado.

Ejemplo 1:

Aporte: listaadj = [[2,4],[1,3],[2,4],[1,3]]
Producción: [[2,4],[1,3],[2,4],[1,3]]
Explicación: Hay 4 nodos en el gráfico. Los vecinos del primer nodo (val = 1) son el segundo nodo (val = 2) y los vecinos del cuarto nodo (val = 4) son el primer nodo (val). = 1) y el tercer nodo (val = 3). Los vecinos del tercer nodo (val = 3) son los vecinos del segundo nodo (val = 2) y el cuarto nodo (val = 4). 1er nodo (val = 1) y 3er nodo (val = 3).

Ejemplo 2:

Aporte: listaadj = [[]]
Producción: [[]]
Explicación: Tenga en cuenta que la entrada contiene una lista vacía. El gráfico consta de un solo nodo con val = 1 y no tiene vecinos.

Ejemplo 3:

Aporte: listaadj = []
Producción: []
Explicación: Este es un gráfico vacío, no tiene ningún nodo.

Restricciones:

El número de nodos en el gráfico está en el rango [0, 100].
1 <= Valor.nodo <= 100
Nodo.val es único para cada nodo.
No hay aristas repetidas ni bucles automáticos en el gráfico.
El gráfico está conectado y se pueden visitar todos los nodos comenzando desde el nodo dado.

Tabla de contenido

Pitón

				
					# Definición para un Nodo. clase Nodo: def __init__(self, val=0, vecinos=Ninguno): self.val = val self.neighbors = vecinos si los vecinos no son Ninguna otra [] clase Solución: def __init__(self): self.visited = {} def cloneGraph(self, nodo: 'Nodo') -> 'Nodo': si no es nodo: devolver nodo si nodo en self.visited: devolver self.visited[nodo] clone_node = Nodo(nodo.val , []) self.visited[node] = clone_node if node.neighbors: clone_node.neighbors = [self.cloneGraph(n) for n in node.neighbors] return clone_node

Pitón

Artículos relacionados