本文主要是介绍444. 序列重建，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
验证原始的序列 org 是否可以从序列集 seqs 中唯一地重建。序列 org 是 1 到 n 整数的排列，其中 1 ≤ n ≤ 104。重建是指在序列集 seqs 中构建最短的公共超序列。（即使得所有 seqs 中的序列都是该最短序列的子序列）。确定是否只可以从 seqs 重建唯一的序列，且该序列就是 org 。
示例 1：
输入：org: [1,2,3], seqs: [[1,2],[1,3]]
输出：false
解释：[1,2,3] 不是可以被重建的唯一的序列，因为 [1,3,2] 也是一个合法的序列。
示例 2：
输入：org: [1,2,3], seqs: [[1,2]]
输出：false
解释：可以重建的序列只有 [1,2]。示例 3：
输入：org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]
输出：true
解释：序列 [1,2], [1,3] 和 [2,3] 可以被唯一地重建为原始的序列 [1,2,3]。示例 4：
输入：org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]
输出：true
思路：这个题目比较晦涩，我看了好半天才看明白：
1、用一个一维数组pos来记录org中每个数字对应的位置，然后再遍历子序列中的每一个数字，看看前后位置对不对。
2、题目要求重建序列唯一，所以org中每一对前后数字必须都得出现过。test case1中没有出现[2, 3], 导致不唯一。可以冗余出现，按照前后顺序重复出现也行，按照前后顺序跨越出现也行。
有两个坑需要注意：
1、子序列seqs中不能出现其他的数字，就是说必须都是原序列中的数字。要判断是否越界。
2、设置 bool existed，防止org=[1], seqs=[[ ],[ ]]这种bad case，也就是说seqs必须得进去，否则会造成cnt=n=1，错误地返回true。虽然进入seqs后，也可能在cnt为1的时候返回true，但那个时候的true是真的true，如org=[1], seqs=[[1]]。也就是cnt可以为1，但是必须是经过计数过程之后仍然得到的1，而不是初始化时的那个1.
class Solution {
public:bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {int n=org.size(), cnt=1;//用来统计前后顺序对的次数，判断唯一bool existed=false;//seqs必须得进去vector<int>po(n+1), flag=po;//po存位置，flag作为标记数组，判断是会否唯一//初始化pofor(int i=0; i<n; ++i){po[org[i]]=i;}for(auto x: seqs){for(int i=0; i<x.size(); ++i){existed=true;if(x[i]<1 || x[i]>n) return false;//判断是否越界if(i==0) continue;if(po[x[i]]<= po[x[i-1]]) return false;//要有等号，防止org=[1], seqs=[[1, 1]]这种bad caseif(flag[x[i]]==0 && po[x[i]]== po[x[i-1]]+1) {//只有首次出现，cnt才计数cnt++;flag[x[i]]=1;}}}return cnt==n && existed;}
};
这篇关于444. 序列重建的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
