332.重新安排行程
给你一份航线列表 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"] ,但是它字典排序更大更靠后。
思路
代码
class Solution {
public List<String> path = new ArrayList<>();
public List<String> res;
public List<String> findItinerary(List<List<String>> tickets) {
//使用lambda表达式,按照目的地将 航线列表 进行排序,使得其满足字典排序,
// 这样首次得到的有效行程一定是所有可能的有效行程中最小的
Collections.sort(tickets,(a, b) -> a.get(1).compareTo(b.get(1)));
//用于记录某机票是否被用过
boolean[] used = new boolean[tickets.size()];
path.add("JFK");
backtracking((ArrayList<List<String>>) tickets, used);
return res;
}
public boolean backtracking(ArrayList<List<String>> tickets, boolean[] used){
//此时已完成所有行程
if(path.size() -1 == tickets.size()){
res = new ArrayList<>(path);
return true;
}
for(int i = 0; i < tickets.size(); i++){
//机票未用过且可以使用
if(!used[i] && tickets.get(i).get(0).equals(path.get(path.size() - 1))){
used[i] = true;
path.add(tickets.get(i).get(1));
if(backtracking(tickets, used)){
return true;
}
used[i] = false;
path.remove(path.size() - 1);
}
}
return false;
}
}
51. N皇后
37. 解数独
总结
代码随想录 (programmercarl.com)