8000 refactor 332 · sakurazz/Leetcode-1@a973cb0 · GitHub
[go: up one dir, main page]
Skip to content

Commit a973cb0

Browse files
fishercoder1534fishercoder1534
committed
refactor 332
1 parent f384beb commit a973cb0

File tree

2 files changed

+34
-85
lines changed

2 files changed

+34
-85
lines changed

‎src/main/java/com/fishercoder/solutions/_332.java

Lines changed: 14 additions & 63 deletions
Original file line numberDiff line numberDiff line change
@@ -33,75 +33,26 @@ All airports are represented by three capital letters (IATA code).
3333
*/
3434
public class _332 {
3535

36-
/**credit: https://discuss.leetcode.com/topic/36383/share-my-solution*/
37-
public List<String> findItinerary(String[][] tickets) {
38-
Map<String, PriorityQueue<String>> flights = new HashMap<>();
39-
LinkedList<String> path = new LinkedList<>();
40-
for (String[] ticket : tickets) {
41-
flights.putIfAbsent(ticket[0], new PriorityQueue<>());
42-
flights.get(ticket[0]).add(ticket[1]);
43-
}
44-
dfs("JFK", flights, path);
45-
return path;
46-
}
47-
48-
public void dfs(String departure, Map<String, PriorityQueue<String>> flights, LinkedList path) {
49-
PriorityQueue<String> arrivals = flights.get(departure);
50-
while (arrivals != null && !arrivals.isEmpty()) {
51-
dfs(arrivals.poll(), flights, path);
52-
}
53-
path.addFirst(departure);
54-
}
55-
56-
57-
public static class MyOwnAttempt {
36+
public static class Solution1 {
37+
/** credit: https://discuss.leetcode.com/topic/36383/share-my-solution */
5838
public List<String> findItinerary(String[][] tickets) {
59-
List<List<String>> allPossibilities = new ArrayList<>();
60-
/**Find all tickets that start from JFK first*/
61-
List<String[]> JFKStarts = new ArrayList<>();
62-
for (String[] ticket : tickets) {
63-
if (ticket[0].equals("JFK")) {
64-
JFKStarts.add(ticket);
65-
}
66-
}
67-
68-
for (String[] ticket : JFKStarts) {
69-
List<String> thisPossibility = new ArrayList<>();
70-
thisPossibility.add(ticket[0]);
71-
thisPossibility.add(ticket[1]);
72-
dfs(ticket, thisPossibility, tickets, allPossibilities);
73-
}
74-
75-
//sort lexicographically and return the smallest
76-
Collections.sort(allPossibilities, new ListComparator<>());
77-
return allPossibilities.get(0);
78-
}
79-
80-
private void dfs(String[] thisTicket, List<String> thisPossibility, String[][] tickets, List<List<String>> allPossibilities) {
81-
if (thisPossibility.size() == tickets.length + 1) {
82-
allPossibilities.add(new ArrayList<>(thisPossibility));
83-
return;
84-
}
39+
Map<String, PriorityQueue<String>> flights = new HashMap<>();
40+
LinkedList<String> path = new LinkedList<>();
8541
for (String[] ticket : tickets) {
86-
if (!ticket.equals(thisTicket) && thisPossibility.get(thisPossibility.size() - 1).equals(ticket[0])) {
87-
thisPossibility.add(ticket[1]);
88-
dfs(ticket, thisPossibility, tickets, allPossibilities);
89-
thisPossibility.remove(thisPossibility.size() - 1);
90-
}
42+
flights.putIfAbsent(ticket[0], new PriorityQueue<>());
43+
flights.get(ticket[0]).add(ticket[1]);
9144
}
45+
dfs("JFK", flights, path);
46+
return path;
9247
}
9348

94-
private class ListComparator<T extends Comparable<T>> implements Comparator<List<T>> {
95-
@Override
96-
public int compare(List<T> o1, List<T> o2) {
97-
for (int i = 0; i < Math.min(o1.size(), o2.size()); i++) {
98-
int c = o1.get(i).compareTo(o2.get(i));
99-
if (c != 0) {
100-
return c;
101-
}
102-
}
103-
return Integer.compare(o1.size(), o2.size());
49+
public void dfs(String departure, Map<String, PriorityQueue<String>> flights,
50+
LinkedList path) {
51+
PriorityQueue<String> arrivals = flights.get(departure);
52+
while (arrivals != null && !arrivals.isEmpty()) {
53+
dfs(arrivals.poll(), flights, path);
10454
}
55+
path.addFirst(departure);
10556
}
10657
}
10758
}

‎src/test/java/com/fishercoder/_332Test.java

Lines changed: 20 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -7,30 +7,28 @@
77

88
import java.util.List;
99

10-
/**
11-
* Created by stevesun on 6/3/17.
12-
*/
1310
public class _332Test {
14-
private static _332 test;
15-
private static String[][] tickets;
16-
private static List<String> expected;
11+
private static _332.Solution1 solution1;
12+
private static String[][] tickets;
13+
private static List<String> expected;
1714

18-
@BeforeClass
19-
public static void setup() {
20-
test = new _332();
21-
}
15+
@BeforeClass
16+
public static void setup() {
17+
solution1 = new _332.Solution1();
18+
}
2219

23-
@Test
24-
public void test1() {
25-
tickets = new String[][]{{"MUC", "LHR"}, {"JFK", "MUC"}, {"SFO", "SJC"}, {"LHR", "SFO"}};
26-
expected = test.findItinerary(tickets);
27-
CommonUtils.print(expected);
28-
}
20+
@Test
21+
public void test1() {
22+
tickets = new String[][] {{"MUC", "LHR"}, {"JFK", "MUC"}, {"SFO", "SJC"}, {"LHR", "SFO"}};
23+
expected = solution1.findItinerary(tickets);
24+
CommonUtils.print(expected);
25+
}
2926

30-
@Test
31-
public void test2() {
32-
tickets = new String[][]{{"JFK", "SFO"}, {"JFK", "ATL"}, {"SFO", "ATL"}, {"ATL", "JFK"}, {"ATL", "SFO"}};
33-
expected = test.findItinerary(tickets);
34-
CommonUtils.print(expected);
35-
}
27+
@Test
28+
public void test2() {
29+
tickets = new String[][] {{"JFK", "SFO"}, {"JFK", "ATL"}, {"SFO", "ATL"}, {"ATL", "JFK"},
30+
{"ATL", "SFO"}};
31+
expected = solution1.findItinerary(tickets);
32+
CommonUtils.print(expected);
33+
}
3634
}

0 commit comments

Comments
 (0)
0