Dada una lista de boletos, encuentre el itinerario en orden usando la lista dada.
Ejemplo:
Java
// Java program to print itinerary in order
import java.util.HashMap;
import java.util.Map;
public class printItinerary
{
// Driver function
public static void main(String[] args)
{
Map<String, String> dataSet = new HashMap<String, String>();
dataSet.put("Chennai", "Banglore");
dataSet.put("Bombay", "Delhi");
dataSet.put("Goa", "Chennai");
dataSet.put("Delhi", "Goa");
printResult(dataSet);
}
// This function populates 'result' for given input 'dataset'
private static void printResult(Map<String, String> dataSet)
{
// To store reverse of given map
Map<String, String> reverseMap = new HashMap<String, String>();
// To fill reverse map, iterate through the given map
for (Map.Entry<String,String> entry: dataSet.entrySet())
reverseMap.put(entry.getValue(), entry.getKey());
// Find the starting point of itinerary
String start = null;
for (Map.Entry<String,String> entry: dataSet.entrySet())
{
if (!reverseMap.containsKey(entry.getKey()))
{
start = entry.getKey();
break;
}
}
// If we could not find a starting point, then something wrong
// with input
if (start == null)
{
System.out.println("Invalid Input");
return;
}
// Once we have starting point, we simple need to go next, next
// of next using given hash map
String to = dataSet.get(start);
while (to != null)
{
System.out.print(start + "->" + to + ", ");
start = to;
to = dataSet.get(to);
}
}
}
C++
#include <bits/stdc++.h>
using namespace std;
void printItinerary(map<string, string> dataSet)
{
// To store reverse of given map
map<string, string> reversemap;
map<string, string>::iterator it;
// To fill reverse map, iterate through the given map
for (it = dataSet.begin(); it!=dataSet.end(); it++)
reversemap[it->second] = it->first;
// Find the starting point of itinerary
string start;
for (it = dataSet.begin(); it!=dataSet.end(); it++)
{
if (reversemap.find(it->first) == reversemap.end())
{
start = it->first;
break;
}
}
// If we could not find a starting point, then something wrong with input
if (start.empty())
{
cout << "Invalid Input" << endl;
return;
}
// Once we have starting point, we simple need to go next,
//next of next using given hash map
it = dataSet.find(start);
while (it != dataSet.end())
{
cout << it->first << "->" << it->second << endl;
it = dataSet.find(it->second);
}
}
int main()
{
map<string, string> dataSet;
dataSet["Chennai"] = "Banglore";
dataSet["Bombay"] = "Delhi";
dataSet["Goa"] = "Chennai";
dataSet["Delhi"] = "Goa";
printItinerary(dataSet);
return 0;
}
// C++ implementation is contributed by Aditya Goel
Python3
class Solution(): #Solution class carries method for printing itinerary def __init__(self): pass #method for printing itinerary def printitinerary(self,d): # First step : create a reversed mapping. Here also for storing key value pairs dictionary is used. reverse_d = dict() for i in d: reverse_d[d[i]] = i # Second step : find the starting point. Starting point will be that value which is not present in 'd' as key. for i in reverse_d: if reverse_d[i] not in reverse_d: starting_pt = reverse_d[i] break; #Third step : simply proceed one by one to print whole route. Assuming that there exist Starting point. while(starting_pt in d): print(starting_pt,"->",d[starting_pt],end=", ") starting_pt = d[starting_pt] #method prints here only. Does not return anything. if __name__=="__main__": # Mapping using inbuilt data structure 'dictionary' d = dict() d["Chennai"] = "Banglore" d["Bombay"] = "Delhi" d["Goa"] = "Chennai" d["Delhi"] = "Goa" # call for method that would print itinerary. obj = Solution() obj.printIterary(d)
Javascript
// JavaScript approach to sollve the problem
function printItinerary(dataSet)
{
// To store reverse of given map
let reversemap = new Map();
// To fill reverse map, iterate through the given map
for (const[key,value] of dataSet)
reversemap.set(value,key);
// Find the starting point of itinerary
let start = "";
for (const key of dataSet.keys())
{
if (!reversemap.has(key))
{
start = key;
break;
}
}
// If we could not find a starting point, then something wrong with input
if (start.length == 0)
{
console.log("Invalid Input");
return;
}
// Once we have starting point, we simple need to go next,
//next of next using given hash map
let it = start;
while (dataSet.has(it))
{
console.log(it+"->"+dataSet.get(it));
it = dataSet.get(it);
}
}
// driver code
let dataSet = new Map();
dataSet.set("Chennai","Banglore");
dataSet.set("Bombay","Delhi");
dataSet.set("Goa","Chennai");
dataSet.set("Delhi","Goa");
printItinerary(dataSet);
//code is contributed by shinjanpatra
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA