Dada una lista de billetes de avión representados por pares de aeropuertos de salida y de llegada [from, to], reconstruir el itinerario en orden. Todos los boletos pertenecen a un hombre que parte de JFK. Por lo tanto, el itinerario debe comenzar con JFK.
Análisis
Esta es una aplicación del algoritmo de Hierholzer para encontrar un Camino euleriano.
Se debe utilizar PriorityQueue en lugar de TreeSet, porque hay entradas duplicadas.
Solución Java
public class Solution{ HashMap<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>(); LinkedList<String> result = new LinkedList<String>(); public List<String> findItinerary(String[][] tickets) { for (String[] ticket : tickets) { if (!map.containsKey(ticket[0])) { PriorityQueue<String> q = new PriorityQueue<String>(); map.put(ticket[0], q); } map.get(ticket[0]).offer(ticket[1]); } dfs("JFK"); return result; } public void dfs(String s) { PriorityQueue<String> q = map.get(s); while (q != null && !q.isEmpty()) { dfs(q.poll()); } result.addFirst(s); } } |
