leetcode 332. Reconstruct Itinerary

「爱情、让人受尽委屈。」 2022-08-20 12:20 20阅读 0赞

Given a list of airline tickets represented by pairs of departure and arrival airports \[from, to\], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.  
  
  
Note:  
If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary \["JFK", "LGA"\] has a smaller lexical order than \["JFK", "LGB"\].  
All airports are represented by three capital letters (IATA code).  
You may assume all tickets form at least one valid itinerary.  
Example 1:  
tickets = \[\["MUC", "LHR"\], \["JFK", "MUC"\], \["SFO", "SJC"\], \["LHR", "SFO"\]\]  
Return \["JFK", "MUC", "LHR", "SFO", "SJC"\].  
Example 2:  
tickets = \[\["JFK","SFO"\],\["JFK","ATL"\],\["SFO","ATL"\],\["ATL","JFK"\],\["ATL","SFO"\]\]  
Return \["JFK","ATL","JFK","SFO","ATL","SFO"\].

Another possible reconstruction is \["JFK","SFO","ATL","JFK","ATL","SFO"\]. But it is larger in lexical order.

// ConsoleApplication6.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<string>
    #include<vector>
    #include<map>
    #include<set>
    #include<algorithm>
    #include<iostream>
    
    
    using namespace std;
    
    class Solution {
    public:
    	vector<string> findItinerary(vector<pair<string, string>> tickets) {
    		struct compare
    		{
    			vector<pair<string, string>>vv;
    			compare(vector<pair<string, string>>uu){ vv = uu; }
    			bool operator()(pair<string, string > ds1, pair<string, string>ds2)
    			{
    				for (int i = 0; i < 3; i++)
    				{
    					if (ds1.first[i] - ds2.first[i] < 0)
    						return true;
    					else if (ds1.first[i] - ds2.first[i] > 0)
    						return false;
    				}
    				for (int i = 0; i < 3; i++)
    				{
    					if (ds1.second[i] - ds2.second[i] < 0)
    						return true;
    					else if (ds1.second[i] - ds2.second[i] > 0)
    						return false;
    				}
    				return false;
    			}
    		};
    		std::sort(tickets.begin(), tickets.end(), compare(tickets));
    		map<string, set<string>>pp, ppp;
    		map<pair<string, string>, int>count, count2;
    		for (int i = 0; i < tickets.size(); i++)
    		{
    			pp[tickets[i].first].insert(tickets[i].second);
    			count[tickets[i]]++;
    		}
    		vector<string>re;
    		set<vector<string>>aa;
    		for (int i = 0; i < tickets.size(); i++)
    		{
    			if (i>0 && tickets[i - 1] == tickets[i])
    				continue;
    			aa.clear();
    			re.clear();
    			count2 = count;
    			ppp = pp;
    			re.push_back(tickets[i].first);
    			re.push_back(tickets[i].second);
    			count2[tickets[i]]--;
    			if (count2[tickets[i]] == 0)
    				ppp[tickets[i].first].erase(ppp[tickets[i].first].find(tickets[i].second));
    			while (true)
    			{
    				while (ppp[re.back()].size() > 0)
    				{
    					string str = re.back();
    					re.push_back(*ppp[str].begin());
    					count2[pair<string, string>(str, re.back())]--;
    					if (count2[pair<string, string>(str, re.back())] == 0)
    						ppp[str].erase(ppp[str].begin());
    					if (re.size() == tickets.size() + 1)
    						return re;
    				}
    				int kk = re.size() - 2;
    				bool f = false;
    				while (!f&&kk >= 1)
    				{
    					while (kk >= 1 && ppp[re[kk]].size() == 0)
    					{
    						kk--;
    					}
    					if (kk == 0)
    						break;
    					for (int j = kk; j < re.size() - 1; j++)
    					{
    						ppp[re[j]].insert(re[j + 1]);
    						count2[pair<string, string>(re[j], re[j + 1])]++;
    					}
    					aa.insert(vector<string>(re.begin(), re.begin() + kk + 2));
    					re.erase(re.begin() + kk + 1, re.end());
    					for (set<string>::iterator it = ppp[re.back()].begin(); it != ppp[re.back()].end(); it++)
    					{
    						vector<string>temp = re;
    						temp.push_back(*it);
    						if (aa.find(temp) == aa.end())
    						{
    							f = true;
    							aa.insert(temp);
    							count2[pair<string, string>(re.back(), *it)]--;
    							if (count2[pair<string, string>(re.back(), *it)] == 0)
    								ppp[re.back()].erase(it);
    							re = temp;
    							break;
    						}
    					}
    					if (!f)
    						kk--;
    				}
    				if (kk == 0)
    					break;
    			}
    		}
    	}
    };
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	Solution sl;
    	vector<pair<string, string>>tickets;
    	//tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
    
    	/*[["EZE","TIA"],["EZE","HBA"],["AXA","TIA"],["JFK","AXA"],["ANU","JFK"],
    	["ADL","ANU"],["TIA","AUA"],["ANU","AUA"],["ADL","EZE"],["ADL","EZE"],
    	["EZE","ADL"],["AXA","EZE"],["AUA","AXA"],["JFK","AXA"],["AXA","AUA"],
    	["AUA","ADL"],["ANU","EZE"],["TIA","ADL"],["EZE","ANU"],["AUA","ANU"]]*/
    	tickets.push_back(pair<string, string>("EZE", "TIA"));
    	tickets.push_back(pair<string, string>("EZE", "HBA"));
    	tickets.push_back(pair<string, string>("AXA", "TIA"));
    	tickets.push_back(pair<string, string>("JFK", "AXA"));
    	tickets.push_back(pair<string, string>("ANU", "JFK"));
    
    	tickets.push_back(pair<string, string>("ADL", "ANU"));
    	tickets.push_back(pair<string, string>("TIA", "AUA"));
    	tickets.push_back(pair<string, string>("ANU", "AUA"));
    	tickets.push_back(pair<string, string>("ADL", "EZE"));
    	tickets.push_back(pair<string, string>("ADL", "EZE"));
    
    	tickets.push_back(pair<string, string>("EZE", "ADL"));
    	tickets.push_back(pair<string, string>("AXA", "EZE"));
    	tickets.push_back(pair<string, string>("AUA", "AXA"));
    	tickets.push_back(pair<string, string>("JFK", "AXA"));
    	tickets.push_back(pair<string, string>("AXA", "AUA"));
    
    	tickets.push_back(pair<string, string>("AUA", "ADL"));
    	tickets.push_back(pair<string, string>("ANU", "EZE"));
    	tickets.push_back(pair<string, string>("TIA", "ADL"));
    	tickets.push_back(pair<string, string>("EZE", "ANU"));
    	tickets.push_back(pair<string, string>("AUA", "ANU"));
    
    	vector<string>re = sl.findItinerary(tickets);
    
    	system("pause");
    	return 0;
    }

妈的，超时

过了大概一个月重新看这道题，发现题意没审清楚，JFK要打头，这就简单很多了嘛。然后修改了下

class Solution {
    public:
    	vector<string> findItinerary(vector<pair<string, string>> tickets) {
    		clock_t start, finish;
    		double Total_time;
    		start = clock();
    
    		struct compare
    		{
    			vector<pair<string, string>>vv;
    			compare(vector<pair<string, string>>uu){ vv = uu; }
    			bool operator()(pair<string, string > ds1, pair<string, string>ds2)
    			{
    				for (int i = 0; i < 3; i++)
    				{
    					if (ds1.first[i] - ds2.first[i] < 0)
    						return true;
    					else if (ds1.first[i] - ds2.first[i] > 0)
    						return false;
    				}
    				for (int i = 0; i < 3; i++)
    				{
    					if (ds1.second[i] - ds2.second[i] < 0)
    						return true;
    					else if (ds1.second[i] - ds2.second[i] > 0)
    						return false;
    				}
    				return false;
    			}
    		};
    		std::sort(tickets.begin(), tickets.end(), compare(tickets));
    		map<string, set<string>> ppp;
    		map<pair<string, string>, int>count;
    		for (int i = 0; i < tickets.size(); i++)
    		{
    			ppp[tickets[i].first].insert(tickets[i].second);
    			count[tickets[i]]++;
    		}
    		vector<string>re;
    		set<vector<string>>aa;
    
    		re.push_back("JFK");
    
    		while (true)
    		{
    			while (ppp[re.back()].size() > 0)
    			{
    				string str = re.back();
    				re.push_back(*ppp[str].begin());
    				count[pair<string, string>(str, re.back())]--;
    				if (count[pair<string, string>(str, re.back())] == 0)
    					ppp[str].erase(ppp[str].begin());
    				if (re.size() == tickets.size() + 1)
    					return re;
    			}
    			int kk = re.size() - 2;
    			if (kk == 0)
    			{
    				string s = re[1];
    				re.pop_back();
    				re.push_back(*ppp[re[0]].begin());
    				count[pair<string, string>(re[0], re.back())]--;
    				if (count[pair<string, string>(re[0], re.back())] == 0)
    					ppp[re[0]].erase(ppp[re[0]].begin());
    				ppp[re[0]].insert(s);
    				count[pair<string, string>(re[0], s)]++;
    			}
    			bool f = false;
    			while (!f&&kk >= 1)
    			{
    				while (kk >= 1 && ppp[re[kk]].size() == 0)
    				{
    					kk--;
    				}
    				if (kk == 0)
    				{
    					for (int i = re.size() - 1; i > 1; i--)
    					{
    						string s = re.back();
    						re.pop_back();
    						ppp[re.back()].insert(s);
    						count[pair<string, string>(re.back(), s)]++;
    					}
    					string s = re[1];
    					re.pop_back();
    					re.push_back(*ppp[re[0]].begin());
    					count[pair<string, string>(re[0], re.back())]--;
    					if (count[pair<string, string>(re[0], re.back())] == 0)
    						ppp[re[0]].erase(ppp[re[0]].begin());
    					ppp[re[0]].insert(s);
    					count[pair<string, string>(re[0], s)]++;
    					continue;
    				}
    				for (int j = kk; j < re.size() - 1; j++)
    				{
    					ppp[re[j]].insert(re[j + 1]);
    					count[pair<string, string>(re[j], re[j + 1])]++;
    				}
    				aa.insert(vector<string>(re.begin(), re.begin() + kk + 2));
    				re.erase(re.begin() + kk + 1, re.end());
    				for (set<string>::iterator it = ppp[re.back()].begin(); it != ppp[re.back()].end(); it++)
    				{
    					vector<string>temp = re;
    					temp.push_back(*it);
    					if (aa.find(temp) == aa.end())
    					{
    						f = true;
    						aa.insert(temp);
    						count[pair<string, string>(re.back(), *it)]--;
    						if (count[pair<string, string>(re.back(), *it)] == 0)
    							ppp[re.back()].erase(it);
    						re = temp;
    						break;
    					}
    				}
    				if (!f)
    					kk--;
    			}
    			
    		}
    
    		finish = clock();
    		Total_time = (double)(finish - start) / CLOCKS_PER_SEC;
    		printf("%f seconds\n", Total_time);
    	}
    };

不过话说现在看一个月前的代码感觉很low，不过也懒得改了