力扣题目链接
剑指 Offer II 115. 重建序列
https://leetcode.cn/problems/ur2n8P/
我们把sequences看成是一个有向图，若按照拓扑排序，入度为0的点只有一个，则一定是一个最短的超序列，否则不是。
此时的拓扑排序会产生歧义,即(1,2,3)或者(1,3,2),因此不满足超序列定义.
public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
//转化成边
Map<Integer, Set<Integer>> edge = new HashMap<>();
//记录入度
int[] inDegree = new int[nums.length + 1];
for (int[] sequence : sequences) {
//注意这里是一个子序列，有多个元素，不是两个
for (int i = 1; i < sequence.length; i++) {
int from = sequence[i - 1];
int to = sequence[i];
//判断是否有此条边
if (edge.containsKey(from) && edge.get(from).contains(to)) {
continue;
}
edge.putIfAbsent(from, new HashSet<>());
edge.get(from).add(to);
inDegree[to]++;
}
}
//记录入度为0的点
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 1; i <= nums.length; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
//存在多个入度为0的点 会有多个超序列 直接返回false
if (queue.size() > 1) {
return false;
}
int from = queue.poll();
Set<Integer> set = edge.get(from);
if (set == null) {
continue;
}
//和此点连通的点入度减一
for (int point : set) {
inDegree[point]--;
if (inDegree[point] == 0) {
queue.add(point);
}
}
}
return true;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之家整理，本文链接：https://www.bmabk.com/index.php/post/88894.html
