面试题113：
解决方案：
- 将课程看成图中的节点，如果两门课程存在先修顺序那么它们在图中对应的节点之间存在一条从先修课程到后修课程的边，因此这是一个有向图。
- 可行的修课序列实际上是图的拓扑排序序列。图中的每条边都是从先修课程指向后修课程，而拓扑排序能够保证任意一条边的起始节点一定排在终止节点的前面，因此拓扑排序得到的序列与先修顺序一定不会存在冲突，于是这个问题转变成如何求有向图的拓扑排序序列。对有向图进行拓扑排序的算法是每次找出一个入度为0的节点添加到序列中，然后删除该节点及所有以该节点为起点的边。重复这个过程，直到图为空或图中不存在入度为0的节点。
源代码：
import java.util.*;
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < numCourses; i++) {
graph.put(i, new LinkedList<Integer>());
}
int[] inDegrees = new int[numCourses];
for (int[] prereq : prerequisites) {
int course = prereq[0];
int prerequisite = prereq[1];
graph.get(prerequisite).add(course);
inDegrees[course]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegrees[i] == 0) {
queue.add(i);
}
}
List<Integer> order = new LinkedList<>();
while (!queue.isEmpty()) {
int course = queue.remove();
order.add(course);
for (int next : graph.get(course)) {
inDegrees[next]--;
if (inDegrees[next] == 0) {
queue.add(next);
}
}
}
return order.size() == numCourses ? order.stream().mapToInt(i -> i).toArray() : new int[0];
}
}
面试题114：
解决方案：
- 在排序的单词列表[“ac”，“ab”，“bc”，“zc”，“zb”]中，一共出现了4个字母，即’a’、‘b’、‘c’和’z’。需要根据单词的顺序确定这个4个字母的顺序。由于"ac"排在"ab"的前面，因此字母’c’应该排在字母’b’的前面（即’c’＜’b’）。这是因为这两个单词的第1个字母相同，第2个字母不同，那么它们的第2个字母的顺序确定了两个单词的顺序。接下来两个相邻的单词是"ab"和"bc"，它们的第1个字母就不同，那么它们的顺序由它们的第1个字母确定，所以’a’＜’b’。类似地，可以根据"bc"排在"zc"的前面得知’b’＜’z’，根据"zc"排在"zb"的前面得知’c’＜’b’。
- 由比较排序的单词列表中两两相邻的单词可知’c’＜’b’、‘a’＜’b’和’b’＜’z’，现在需要找出一个包含4个字母的字母序列满足已知的3个字母的大小顺序。这看起来就是一个关于拓扑排序的问题，可以将每个字母看成图中的一个节点。如果已知两个字母的大小关系，那么图中就有一条从较小的字母指向较大的字母的边。
源代码：
class Solution {
public String alienOrder(String[] words) {
Map<Character, Set<Character>> graph = new HashMap<>();
Map<Character, Integer> inDegrees = new HashMap<>();
for (String word : words) {
for (char ch : word.toCharArray()) {
graph.putIfAbsent(ch, new HashSet<>());
inDegrees.put(ch, 0);
}
}
for (int i = 1; i < words.length; i++) {
String w1 = words[i - 1];
String w2 = words[i];
if (w1.startsWith(w2) && !w1.equals(w2)) {
return "";
}
for (int j = 0; j < w1.length() && j < w2.length(); j++) {
char ch1 = w1.charAt(j);
char ch2 = w2.charAt(j);
if (ch1 != ch2) {
if (!graph.get(ch1).contains(ch2)) {
graph.get(ch1).add(ch2);
inDegrees.put(ch2, inDegrees.get(ch2) + 1);
}
break;
}
}
}
Queue<Character> queue = new LinkedList<>();
for (char ch : inDegrees.keySet()) {
if (inDegrees.get(ch) == 0) {
queue.add(ch);
}
}
StringBuilder sb = new StringBuilder();
while (!queue.isEmpty()) {
char ch = queue.remove();
sb.append(ch);
for (char next : graph.get(ch)) {
inDegrees.put(next, inDegrees.get(next) - 1);
if (inDegrees.get(next) == 0) {
queue.add(next);
}
}
}
return sb.length() == graph.size() ? sb.toString() : "";
}
}
面试题115：
解决方案：
- 按照题目的要求，如果在seqs的某个序列中数字i出现在数字j的前面，那么由seqs重建的序列中数字i一定也要出现在数字j的前面。也就是说，重建序列的数字顺序由seqs的所有序列定义。可以将seqs中每个序列的每个数字看成图中的一个节点，两个相邻的数字之间有一条从前面数字指向后面数字的边。
- 如果得到的是有向图的拓扑排序序列，那么任意一条边的起始节点在拓扑排序序列中一定位于终止节点的前面。因此，由seqs重建的序列就是由seqs构建的有向图的拓扑排序的序列。这个问题就转变成判断一个有向图的拓扑排序序列是否唯一。
源代码：
class Solution {
public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
Map<Integer, Integer> inDegrees = new HashMap<>();
for (int[] sequence : sequences) {
for (int num : sequence) {
if (num < 1 || num > nums.length) {
return false;
}
graph.putIfAbsent(num, new HashSet<>());
inDegrees.putIfAbsent(num, 0);
}
for (int i = 0; i < sequence.length - 1; i++) {
int num1 = sequence[i];
int num2 = sequence[i + 1];
if (!graph.get(num1).contains(num2)) {
graph.get(num1).add(num2);
inDegrees.put(num2, inDegrees.get(num2) + 1);
}
}
}
Queue<Integer> queue = new LinkedList<>();
for (int num : inDegrees.keySet()) {
if (inDegrees.get(num) == 0) {
queue.add(num);
}
}
List<Integer> built = new LinkedList<>();
while (queue.size() == 1) {
int num = queue.remove();
built.add(num);
for (int next : graph.get(num)) {
inDegrees.put(next, inDegrees.get(next) - 1);
if (inDegrees.get(next) == 0) {
queue.add(next);
}
}
}
int[] result = new int[built.size()];
result = built.stream().mapToInt(i -> i).toArray();
return Arrays.equals(result, nums);
}
}
