1.排序
Collections.sort(list,(o1, o2)-> o1.get(0).compareTo(o2.get(0)));
2.返回值
3.往集合添加元素
Arrays.asList(元素)
List<List<String>> list = new ArrayList<>();
List<String> path = new ArrayList<>();
// 将[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]加入list中
List<String> entry1 = new ArrayList<>(Arrays.asList("JFK", "SFO"));
List<String> entry2 = new ArrayList<>(Arrays.asList("JFK", "ATL"));
List<String> entry3 = new ArrayList<>(Arrays.asList("SFO", "ATL"));
List<String> entry4 = new ArrayList<>(Arrays.asList("ATL", "JFK"));
List<String> entry5 = new ArrayList<>(Arrays.asList("ATL", "SFO"));
list.add(entry1);
list.add(entry2);
list.add(entry3);
list.add(entry4);
list.add(entry5);
4.path为路线经过机场数,list为机票数,四张机票会经过5个机场
if (path.size() == tickets.size() + 1) {
res = new LinkedList(path);
return true;
}
5.整体代码
class Solution {
private LinkedList<String> res;
private LinkedList<String> path = new LinkedList<>();
public List<String> findItinerary(List<List<String>> tickets) {
Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
path.add("JFK");
boolean[] used = new boolean[tickets.size()];
backTracking((ArrayList) tickets, used);
return res;
}
public boolean backTracking(ArrayList<List<String>> tickets, boolean[] used) {
if (path.size() == tickets.size() + 1) {
res = new LinkedList(path);
return true;
}
for (int i = 0; i < tickets.size(); i++) {
if (!used[i] && tickets.get(i).get(0).equals(path.getLast())) {
path.add(tickets.get(i).get(1));
used[i] = true;
if (backTracking(tickets, used)) {
return true;
}
used[i] = false;
path.removeLast();
}
}
return false;
}
}