# 来聊聊compass经典高频题 game rank

``````public class GetGameRank {

public static void main(String[] args) {
String[] test1 = new String[]{"a beat b", "b beat c", "c beat e"};
getOrder(test1).forEach(x -> System.out.print(x + " ")); //a b c e
System.out.println();

String[] test2 = new String[]{"a beat b", "a beat c"};
getOrder(test2).forEach(x -> System.out.print(x + " ")); //a b c OR a c b
System.out.println();

System.out.println(getOrder(null).size() == 0);

String[] test3 = new String[]{"a beat b", "b beat c", "c beat e", "e beat f", "e beat d", "d beat k"}; // a b c e d k f
getOrder(test3).forEach(x -> System.out.print(x + " ")); //a b c e
System.out.println();
}

public static List<String> getOrder(String[] games) {
if (games == null || games.length == 0) return res;
Map<String, Integer> inDegree = new HashMap<>();
Map<String, List<String>> graph = new HashMap<>();
for (String game : games) {
String[] team = game.split(" beat ");
inDegree.put(team[1], inDegree.getOrDefault(team[1], 0));
inDegree.put(team[0], inDegree.getOrDefault(team[0], 0) + 1);
}
Iterator<Map.Entry<String, Integer>> iterator = inDegree.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> entry = iterator.next();
if (entry.getValue() == 0) {
queue.offer(entry.getKey());
iterator.remove();
}
}

while (!queue.isEmpty()) {
String curr = queue.poll();
List<String> next = graph.get(curr);
if (next == null || next.size() == 0) continue;
for (String n : next) {
inDegree.put(n, inDegree.get(n) - 1);
if (inDegree.get(n) == 0) {
inDegree.remove(n);
queue.offer(n);
}
}
}
return res;
}
}
``````

``````xxxx beat yyyy
``````

`String[] team = game.split(" beat ");` 来进行拆分成两个队伍

``````Map<String, Integer> inDegree = new HashMap<>();
``````

``````["a beat b", "b beat c" ]
//c 作为 key的话  b就是c的value
//b 作为key的话 a就是b的value
{c:[b], b:[a]}
``````

`inDegree.put(team[1], inDegree.getOrDefault(team[1], 0));`

``````for (String n : next) {
inDegree.put(n, inDegree.get(n) - 1);
if (inDegree.get(n) == 0) {
inDegree.remove(n);
queue.offer(n);
}
}
``````

`res.add(0, curr);`

Iterator.remove()不会抛出ConcurrentModificationException,因为这是在迭代时修改集合的允许方式.

``````        Iterator<Map.Entry<String, Integer>> iterator = inDegree.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> entry = iterator.next();
if (entry.getValue() == 0) {
queue.offer(entry.getKey());
iterator.remove();
}
}
``````

1 Like

2 Likes

zillow有点不思进取，早期先发的优势都搞没了

redfin都上市了。zillow上市遥遥无期

``````       Iterator<Map.Entry<String, Integer>> iterator = inDegree.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> entry = iterator.next();
if (entry.getValue() == 0) {
queue.offer(entry.getKey());
iterator.remove();
}
}
``````

Given a series of game results such as xxxx beats yyyy, output the final ranking.

Example 1:

Input: [“a beats b”, “b beats c”, “c beats d”]
Output: [“a”, “b”, “c”, “d”]
Example 2:

Input: [“a beats b”, “a beats c”]
Output: [“a”, “b”, “c”] or [“a”, “c”, “b”]
You can assume that there are no cycles.