AlgoPressAppearance
0332-重新安排行程
https://leetcode.cn/problems/reconstruct-itinerary
给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
示例 1：
输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]
示例 2：
输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。
提示：
- 1 <= tickets.length <= 300
- tickets[i].length == 2
- fromi.length == 3
- toi.length == 3
- fromi 和 toi 由大写英文字母组成
- fromi != toi
思路 : 回溯会超时
- 先排序，保证字典顺序的再前面
- 回溯法，探测可以使用的线路，设置 used = true
- 当全部线路轮询完毕后，得到结果
参考代码
csharp
public class Solution {
private List<string> result = new List<string>();
private bool[] used;
private void dfs(IList<IList<string>> tickets, int index, string last,List<int> list){
if(index == tickets.Count){
//输出结果
result.Clear();
for(int i=0; i<list.Count; i++){
result.Add(tickets[list[i]][0]);
}
result.Add(tickets[list[list.Count-1]][1]);
return;
}
for(int i=0; i<tickets.Count; i++){
if(tickets[i][0] == last && !used[i]){
used[i] = true;
list.Add(i);
dfs(tickets,index+1,tickets[i][1],list);
list.RemoveAt(list.Count - 1);
used[i] = false;
}
}
}
public IList<string> FindItinerary(IList<IList<string>> tickets) {
tickets = tickets.OrderByDescending(x => x.ElementAt(1)).ToList();
List<int> list = new List<int>();
used = new bool[tickets.Count];
dfs(tickets,0,"JFK",list);
return result;
}
}
思路2：官方题解
- 定义一个数组，记录每一次选择的 索引位置
- 找 from 在tickets 子集，从 0 索引开始找，找到的话：tickets 减去这个元素，list 增加一个元素
- 当 一次新的 from 找不到 tickets 子集时，说明前面选择有误，回退一步
- 当 一次新的 from 找出来的 tickets 子集个数 已经都跑过了，也没有办法找到解决方案，同样回退一步
- 注意：回退一步的操作是，tickets 追加回去，list 减去一个
csharp
public class Solution {
public IList<string> FindItinerary(IList<IList<string>> tickets) {
IList<string> list = new List<string>();
string from = "JFK";
list.Add(from);
int len = tickets.Count + 1;
int[] pa = new int[len];
int pos = 0;
while (list.Count < len)
{
IList<IList<string>> curList = tickets.Where(x => x.ElementAt(0) == from).OrderBy(x => x.ElementAt(1)).ToList();
if (curList.Count== 0 || curList.Count == pa[pos])
{
from = list.ElementAt(list.Count-2);
//tickets 加回去
IList<string> reback = new List<string>();
reback.Add(from);
reback.Add(list.ElementAt(list.Count - 1));
tickets.Add(reback);
// list 减掉
list.RemoveAt(list.Count - 1);
if (curList.Count == pa[pos])
{
pa[pos] = 0;
}
pos--;
continue;
}
from = curList.ElementAt(pa[pos]).ElementAt(1);
//tickets 减
tickets.Remove(curList.ElementAt(pa[pos]));
//list 加
list.Add(from);
pa[pos]++;
pos++;
}
return list;
}
}
复习：欧拉回路 20220713
- 用哈希表和list储存图的关系，因为满足条件的需要是字典序，所以 list 按照自增排序
- 从 JFK 出发之后，dfs遍历能到达的点，然后到达之后，就拆掉这一边。 因为这是半欧拉图，所以死胡同必然是第一个到达的并且递归回来的，把它加入到 result 里面，最后按照 result 的反序输出
csharp
public class Solution {
Dictionary<string,List<string>> dict = new Dictionary<string,List<string>>();
List<string> result = new List<string>();
private void dfs(string source){
if(dict.ContainsKey(source) && dict[source].Count > 0){
while(dict[source].Count > 0){ //这里不能用 for 循环，因为 remove 的时候 count 会改变
string target = dict[source][0]; //每次取第一个
dict[source].Remove(target);
dfs(target);
}
}
result.Add(source);
}
public IList<string> FindItinerary(IList<IList<string>> tickets) {
//储存数据到图
for(int i=0; i<tickets.Count; i++){
string source = tickets[i][0];
string target = tickets[i][1];
if(!dict.ContainsKey(source)){
dict.Add(source,new List<string>());
}
// target 不需要加入，没有target起点的地方， dfs会跳过
// if(!dict.ContainsKey(target)){
// dict.Add(target,new List<string>());
// }
dict[source].Add(target);
}
//排序元素
foreach(string key in dict.Keys){
if(dict[key].Count > 0){
dict[key].Sort((a,b)=>{
return a.CompareTo(b);
});
}
}
dfs("JFK");
result.Reverse();
return result;
}
}