剑指 Offer II 115. 重建序列
1 题目描述
给定一个长度为 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：
[maybe_some_pic_here]
输入: 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。
2 思路
说到底，其实sequences数组中，每一个元素都包含有若干个前后关系，也就是拓扑排序中所要遵循的要求，而这题的意思就是求sequences是不是存在且只存在一种有效的拓扑排序，如果是，那么这个排序是否与nums一样，如果一样那么就是对的，返回true，否则返回false.
对于一个有向无环图，它的拓扑排序实际上可能存在多种，什么情况下才只存在一种呢？答案就是有且仅有一个入度为0的顶点且只有一个出度为0的顶点，如果满足这个条件，那么这个图就只存在一种有效的拓扑排序。因此，按照拓扑排序模板进行排序即可，但在排序前先进行判断，判断出度为0的顶点和入度为0的顶点是不是都只有一个，如果不是说明存在多种拓扑排序，那么不用进行排序直接返回false即可。因此，按拓扑排序模板，我们要加入一个记录顶点出度的数组，记为outdegree,在建完图后扫描出度和入度数组，将入度为0的顶点入队，并记录出度为0的顶点数，二者只要有一个大于1那么就返回false，否则进行拓扑排序。
排序后判断长短是否和nums一致，并进行遍历，如果有一位不相同，那么说明nums不是超序列，返回false。
注意，数字是1-n，所以下标都是从1开始，而不是0，否则代码里老是要-1麻烦。
DFS实现
class Solution { vector<vector<int>> edges; // 邻接表 vector<int> indegree, outdegree; // 入度和出度数组 int n; void dfs(vector<int>& res, int index) { --indegree[index]; res.emplace_back(index); for(auto next: edges[index]) if(!--indegree[next]) dfs(res, next); } public: bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) { n = nums.size(); edges.resize(n+1); indegree = vector<int> (n+1, 0); outdegree = vector<int> (n+1, 0); // 建图 for(auto vec: sequences) { for(int i = 1; i < vec.size(); ++i) { edges[vec[i-1]].emplace_back(vec[i]); ++indegree[vec[i]]; ++outdegree[vec[i-1]]; } } int in = 0, out = 0; for(int i = 1; i <= n; ++i){ if(indegree[i]==0) ++in; if(outdegree[i]==0) ++out; } if(in!=1 || out!=1) return false; vector<int> res; // 存放拓扑排序结果 // 拓扑排序 for(int i = 1; i <= n; ++i) { if(indegree[i] == 0) { dfs(res, i); } } // 与nums数组进行比较 if(res.size() != n) return false; for(int i = 0; i < n; ++i) if(res[i] != nums[i]) return false; return true; } };BFS实现
class Solution { public: bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) { int n = nums.size();; vector<int> indegree(n+1, 0), outdegree(n+1, 0); // 入度和出度数组 vector<vector<int>> edges(n+1); // 邻接表 // 建图 for(auto vec: sequences) { for(int i = 1; i < vec.size(); ++i) { edges[vec[i-1]].emplace_back(vec[i]); ++indegree[vec[i]]; // 下标1开始到size-1的顶点才有入度 ++outdegree[vec[i-1]]; // 下标0到size-2开始的顶点才有出度 } } int cnt = 0; queue<int> q; for(int i = 1; i <= n; ++i){ if(indegree[i]==0) // 将入度为0的顶点入队 q.emplace(i); if(outdegree[i]==0) ++cnt; } if(q.size()!=1 || cnt!=1) return false; vector<int> res; // 存放拓扑排序结果 // 拓扑排序 while(!q.empty()) { int cur = q.front(); res.emplace_back(cur); q.pop(); for(int next: edges[cur]) if(!(--indegree[next])) q.emplace(next); } // 与nums数组进行比较 if(res.size() != n) return false; for(int i = 0; i < n; ++i) if(res[i] != nums[i]) return false; return true; } };
