给一系列比赛结果，例如“a beats b”, “b beat c”，“c beat d”；输出最终排名，这个例子是abcd，算是alien dictionary的变形。
不存在circle，例如“d beats a”。然后问了time and space complexity，还有会用什么样的test case去测试。
先上代码
public class GetGameRank {
public static void main(String[] args) {
// write your code here
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) {
LinkedList<String> res = new LinkedList<>();
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);
graph.computeIfAbsent(team[1], x -> new ArrayList<>()).add(team[0]);
}
Queue<String> queue = new LinkedList<>();
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);
res.addFirst(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;
}
}
首先看到这种题 一个压着一个 第一个想到的就是topological sort （拓扑排序）
首先我们要将这个String 进行拆分
每个String的格式基本都是
xxxx beat yyyy
用 String[] team = game.split(" beat "); 来进行拆分成两个队伍
拓扑排序我们需要知道 这个element被多少个element压着 我们因此也称为 indegree
这里的element指的就是队伍 这里的indegree指的是这个队伍打败多少个队伍
记住这里很重要的一个条件 那就是这里不存在circle
最后一名队伍 打败0个人 因此最后一名队伍的indegree 就是0
Map<String, Integer> inDegree = new HashMap<>();
为什么这里会用到graph？key代表着是当前的队伍，value则是打败过此队伍的队，有点绕口 接下来我给个例子解释一下
举个例子
["a beat b", "b beat c" ]
//c 作为 key的话 b就是c的value
//b 作为key的话 a就是b的value
{c:[b], b:[a]}
首先作为入口 我们得找出最后一名 然后作为突破口 用BFS, 拓扑据我了解基本都是用BFS来做。
所以我把被打败的队伍也放进indegree里面 就是之后找到突破口，上文提到 最后哪个队伍打败0个队伍就是最后一名，所以这个indegree的map逐个走一遍，看看哪个队伍的indegree是0， 就知道知道哪个队伍是最后一名
inDegree.put(team[1], inDegree.getOrDefault(team[1], 0));
在indegree里面每次要remove掉 indegree只有0的队伍 代表 这个队伍 在这个state 就是最后一名， 然后我们要把这个队伍放到queue里面 然后找出 哪些队伍打败过这个队伍 这些队伍的indegree需要减去一个。 如果这些队伍打败最后一名的队伍 那么下一个state 这个队伍就是最后一名，所以要放到queue里面来找到打败这些队伍的人
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);
时间复杂度 我会说是O(N) N代表队伍数量 空间复杂度也是O(N) N 等于队伍数量
最后有一个地方希望大家注意一下 虽然是很小的东西 新手可能都会犯的错误
找入口的时候需要循环 indegree的map 然后移除掉 indegree为0的队伍 为什么用iterator? 这里不是我为了展现代码风骚来装逼才使用 iterator. 因为使用for loop来循环这个map 然后遇到indegree为0的entry 然后remove掉这个entry会导致concurrentModificationException
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();
}
}
这个我就不仔讲了 详情大家感兴趣可以去网上搜搜看
楼主新人写算法教程帖子，不喜勿喷 喜欢就点个赞吧。