代码随想录第三十天 | 回溯问题P6 | ● 332● 51● 37● 总结

本文主要是介绍代码随想录第三十天 | 回溯问题P6 | ● 332● 51● 37● 总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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;}
}