淘客网站难做吗,wordpress文章付费支付宝,flash网站教程,wordpress sina1. 重新安排行程
332. 重新安排行程https://leetcode.cn/problems/reconstruct-itinerary/给你一份航线列表 tickets #xff0c;其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK#xff08;肯…1. 重新安排行程
332. 重新安排行程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] 但是它字典排序更大更靠后。
解题思路
给出一堆边要从这些边里面得到可以把所有边使用到的路在找路的过程中显然是深度优先也就是需要递归然后回溯。对于所有的路来说还要找到一条权重最低的路。
对于找到权重最低的路显然最好的办法就是一开始就是从权重最低的选项开始的然后呢如果权重最低的回溯成功了那就结束。
在最后一个测试用例中出现了超时原因在于有很多的重复的票会存在多次重复需要剪枝
代码
class Solution {LinkedListString path new LinkedList();LinkedListString res;public ListString findItinerary(ListListString tickets) {Collections.sort(tickets, (a, b) - a.get(1).compareTo(b.get(1)));boolean[] mark new boolean[tickets.size()];Arrays.fill(mark, false);path.add(JFK);backTrack(tickets, mark);return res;}private boolean backTrack(ListListString tickets, boolean[] mark) {if (path.size() tickets.size() 1) {res new LinkedList(path);return true;}for (int i 0; i tickets.size(); i) {if (i 0 !mark[i - 1] tickets.get(i).get(0).equals(tickets.get(i - 1).get(0)) tickets.get(i).get(1).equals(tickets.get(i - 1).get(1))) {continue;}if (!mark[i] tickets.get(i).get(0).equals(path.getLast())) {path.add(tickets.get(i).get(1));mark[i] true;if (backTrack(tickets, mark)) {return true;}mark[i] false;path.removeLast();}}return false;}
}
