LeetCode Reconstruct Itinerary
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.
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.
给定一系列机票，每张机票标明了A→B的一段旅程，现在要求把所有的机票旅程连成一条完整的长距离航线，要求起点是JFK。如果有多条合法的航线，则输出字典序最小的那条。 显然要转换为图的问题，每个机场转换为一个点，每张机票转换为一条边，然后从JFK开始DFS，保留每条合法的航线，然后sort取字典序最小的航线。 把问题转换为图不难，使用hash给每个机场编号，然后新建一个图。在图中以JFK开始DFS也不难，每深入DFS一层，机票数目减1，当机票数目为0时，DFS结束，找到一条合法航线。 我一开始是这么做的，但是TLE了，因为这样可能会进行很多次DFS， 找到多条航线，还需要sort取字典序最小的航线。 有没有办法一次找到字典序最小的航线呢，只需要在DFS的时候，每次都从字典序最小的机场开始下一层DFS，这样第一次DFS成功的航线肯定是字典序最小的航线。 所以我们给机场编号的时候，先使用map记录，map会自动按key的字典序从小到大排好。然后遍历map重新编号，并且用hash2记录编号和机场的对应关系。这样，在DFS的时候，从0→n的遍历，就自动是按字典序从小到大遍历。 代码如下： [cpp] class Solution { private: bool dfs(string& ans, vector<string>& hash2, vector<vector<int>>& graph, int start, int lines) { if (lines == 0) return true; int n = hash2.size(); for (int i = 0; i < n; ++i) { // 字典序从小到大深搜 if (graph[start][i] > 0) { –graph[start][i]; ans += hash2[i]; if (dfs(ans, hash2, graph, i, lines – 1))return true; ++graph[start][i]; ans = ans.substr(0, ans.size() – 3); } } return false; } public: vector<string> findItinerary(vector<pair<string, string>> tickets) { map<string, int> hash1; vector<string> hash2; int cnt = 0, n = tickets.size(); for (int i = 0; i < tickets.size(); ++i) { // 记录 hash1[tickets[i].first] = 0; hash1[tickets[i].second] = 0; } for (auto it = hash1.begin(); it != hash1.end(); ++it) { it->second = cnt++; // 字典序从小到大编号 hash2.push_back(it->first); } vector<vector<int>> graph(cnt, vector<int>(cnt, 0)); // 构图 for (int i = 0; i < tickets.size(); ++i)++graph[hash1[tickets[i].first]][hash1[tickets[i].second]]; int start = hash1["JFK"]; string ans = "JFK"; dfs(ans, hash2, graph, start, n); // 深搜 vector<string> Itinerary; for (int i = 0; i <= ans.size() – 3; i += 3)Itinerary.push_back(ans.substr(i, 3)); return Itinerary; } }; [/cpp] 本代码提交AC，用时22MS。]]>
贪心的代码如下：
[cpp]
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
int ans = 1, i = 0, j = 1;
bool up = false;
while (j < n && nums[j] == nums[i])++j;
if (nums[j] > nums[i])up = true;
else up = false;
while (j < n) {
if (nums[j] > nums[i] && up) {
++ans;
up = false;
while (j + 1 < n&&nums[j + 1] >= nums[j])++j;
}
else if (nums[j] < nums[i] && !up) {
++ans;
up = true;
while (j + 1 < n&&nums[j + 1] <= nums[j])++j;
}
i = j++;
}
return ans;
}
};
[/cpp]
本代码提交AC，用时3MS。
还可以用动态规划的方法，假设up[i]表示第i个元素处于抖动序列的最后一个位置，且是上升的趋势时，前[0,i]的抖动子序列的最大长度。类似的，down[i]表示第i个元素处于抖动序列的最后一个位置，且是下降趋势时，前[0,i]的抖动子序列的最大长度。
则对于第i个元素，可以枚举所有i前面的元素j跳到i，如果nums[i]>nums[j]，则i处于抖动序列的上升末尾，则从j到i构成的抖动序列中，j是处于下降趋势的，所以有up[i]=max(up[i],down[j]+1)。类似的，如果nums[i]<nums[j]，则有down[i]=max(down[i],up[j]+1)。最后返回1+max(up[n-1],down[n-1])。
代码如下：
[cpp]
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
vector<int> up(n, 0), down(n, 0);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j])up[i] = max(up[i], down[j] + 1);
else if (nums[i] < nums[j])down[i] = max(down[i], up[j] + 1);
}
}
return 1 + max(up[n – 1], down[n – 1]);
}
};
[/cpp]
本代码提交AC，用时6MS。
可以对上述代码优化。j无需枚举所有i前面的元素，而是i直接根据和前一个元素i-1的大小关系进行更新。如果nums[i]>nums[i-1]，则i处于上升末端，所以i-1必须处于下降末端，有up[i]=down[i-1]+1，down[i]不变，即down[i]=down[i-1]。如果nums[i]<nums[i-1]，则i处于下降末端，所以i-1必须处于上升末端，有down[i]=up[i-1]+1，up[i]不变，即up[i]=up[i-1]。如果nums[i]==nums[i-1]，则up[i]和down[i]都不变，分别等于up[i-1]和down[i-1]。
为什么这里可以不用枚举所有i前面的元素了呢，因为上述三种情况中，只更新了该更新的，不能更新的情况都等于前一个元素的结果了，比如第一种情况更新了up[i]，则down[i]保持了down[i-1]的值，所以后续如果要用到down[i-1]的值，也可以直接用down[i]的值了。
代码如下：
[cpp]
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
vector<int> up(n, 0), down(n, 0);
up[0] = down[0] = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] > nums[i – 1]) {
up[i] = down[i – 1] + 1;
down[i] = down[i – 1];
}
else if (nums[i] < nums[i – 1]) {
down[i] = up[i – 1] + 1;
up[i] = up[i – 1];
}
else {
up[i] = up[i – 1];
down[i] = down[i – 1];
}
}
return max(up[n – 1], down[n – 1]);
}
};
[/cpp]
本代码提交AC，用时3MS。
还可以对上述代码进行空间的优化，因为up[i]和down[i]都只用到了前一个结果up[i-1]和down[i-1]，所以只需保留前一个结果就行，不需要两个数组。代码如下：
[cpp]
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
int up = 1, down = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] > nums[i – 1]) {
up = down + 1;
}
else if (nums[i] < nums[i – 1]) {
down = up + 1;
}
}
return max(up, down);
}
};
[/cpp]
本代码提交AC，用时0MS，是效率最好的一种解法了。
参考：