入门力扣自学笔记101 C++ （题目编号：剑指Offer二 115）

剑指Offer二 115）"/>

入门力扣自学笔记101 C++ （题目编号：剑指Offer二 115）

剑指 Offer II 115. 重建序列

题目：

给定一个长度为 n 的整数数组 nums ，其中 nums 是范围为 [1，n] 的整数的排列。还提供了一个 2D 整数数组 sequences ，其中 sequences[i] 是 nums 的子序列。
检查 nums 是否是唯一的最短 超序列 。最短 超序列 是 长度最短 的序列，并且所有序列 sequences[i] 都是它的子序列。对于给定的数组 sequences ，可能存在多个有效的 超序列 。

例如，对于 sequences = [[1,2],[1,3]] ，有两个最短的 超序列 ，[1,2,3] 和 [1,3,2] 。
而对于 sequences = [[1,2],[1,3],[1,2,3]] ，唯一可能的最短 超序列 是 [1,2,3] 。[1,2,3,4] 是可能的超序列，但不是最短的。
如果 nums 是序列的唯一最短 超序列 ，则返回 true ，否则返回 false 。
子序列 是一个可以通过从另一个序列中删除一些元素或不删除任何元素，而不改变其余元素的顺序的序列。

示例 1：

输入：nums = [1,2,3], sequences = [[1,2],[1,3]]
输出：false
解释：有两种可能的超序列：[1,2,3]和[1,3,2]。
序列 [1,2] 是[1,2,3]和[1,3,2]的子序列。
序列 [1,3] 是[1,2,3]和[1,3,2]的子序列。
因为 nums 不是唯一最短的超序列，所以返回false。

示例 2：

输入：nums = [1,2,3], sequences = [[1,2]]
输出：false
解释：最短可能的超序列为 [1,2]。
序列 [1,2] 是它的子序列：[1,2]。
因为 nums 不是最短的超序列，所以返回false。

示例 3：

输入：nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
输出：true
解释：最短可能的超序列为[1,2,3]。
序列 [1,2] 是它的一个子序列：[1,2,3]。
序列 [1,3] 是它的一个子序列：[1,2,3]。
序列 [2,3] 是它的一个子序列：[1,2,3]。
因为 nums 是唯一最短的超序列，所以返回true。

提示：

n == nums.length
1 <= n <= 104
nums 是 [1, n] 范围内所有整数的排列
1 <= sequences.length <= 104
1 <= sequences[i].length <= 104
1 <= sum(sequences[i].length) <= 105
1 <= sequences[i][j] <= n
sequences 的所有数组都是 唯一 的
sequences[i] 是 nums 的一个子序列

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

拓扑排序

按照题目的要求，若在 seqs 的某个序列中数字 i 出现在数字 j 之前，那么由 seqs 重建的序列中数字 i 一定出现在 j 之前，也就是说重建的序列 org 就是由 seqs 确定的拓扑排序。题目中要求 org 是由 seqs 重建的唯一的序列，即序列 org 为由 seqs 确定的唯一的拓扑排序。

需要使用一个哈希表记录由 seqs 构建图的各节点的邻接表，用一个数组记录各节点的入度。之后在使用队列进行广度优先搜索确定图的拓扑排序时，因为需要满足唯一性，所以每次入度为 0 的节点必须唯一，且需要与 org 中一一对应。完整代码如下，因为节点数 v 为 org.size()，边的个数 e 为 O(sum(seqs[i].size))，所以时间复杂度为 O(v + e)。

代码：

class Solution {
public:bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {// 建图unordered_map<int, unordered_set<int>> graph;vector<int> inDegree(org.size() + 1, -1);for (auto& seq : seqs) {for (int& n : seq) {// 节点需要合法if (n < 1 || n > org.size()) {return false;}if (!graph.count(n)) {graph[n] = {};}if (inDegree[n] == -1) {inDegree[n] = 0;}}for (int i = 0; i < seq.size() - 1; ++i) {int num1 = seq[i];int num2 = seq[i + 1];if (!graph[num1].count(num2)) {graph[num1].insert(num2);inDegree[num2]++;}}}// 初始化队列queue<int> que;int index = 0;for (int i = 1; i < inDegree.size(); ++i) {if (inDegree[i] == 0) {// 存在唯一入度为 0 的节点，且与 org[0] 相等if (que.size() == 0 && org[index++] == i) {que.push(i);}else {return false;}}}// BFSwhile (!que.empty()) {int node = que.front();que.pop();for (auto& n : graph[node]) {inDegree[n]--;if (inDegree[n] == 0) {// 每次只存在唯一入度为 0 的节点，且与 org[index] 相等if (que.size() == 0 && org[index++] == n) {que.push(n);}else {return false;}                    }}}return index == org.size();}
};