胶州做网站的,怎么做推销产品的网站,三年抗疫国库空虚殆尽,甘肃网站建设方案服务至上文章目录1. 题目2. 解题1. 题目
验证原始的序列 org 是否可以从序列集 seqs 中唯一地重建。 序列 org 是 1 到 n 整数的排列#xff0c;其中 1 ≤ n ≤ 104。 重建是指在序列集 seqs 中构建最短的公共超序列。#xff08;即使得所有 seqs 中的序列都是该最短序列的子序列其中 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来源力扣LeetCode 链接https://leetcode-cn.com/problems/sequence-reconstruction 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
class Solution {
public:bool sequenceReconstruction(vectorint org, vectorvectorint seqs) {int n org.size();vectorbool exit(n1, false);//是否存在vectorvectorint g(n1);//图vectorint indegree(n1, 0);//入度for(auto s : seqs){int from -1;for(int i 0; i s.size(); i){if(s[i] 0 || s[i] n) return false;//编号超了exit[s[i]] true;if(from ! -1){g[from].push_back(s[i]);//边indegree[s[i]];//入度1}from s[i];}}queueint q;for(int i 1; i n; i){if(!exit[i]) return false;//有的点不存在if(indegree[i]0)//入度为0的入队q.push(i);}int i 0;while(!q.empty()){if(q.size() ! 1) return false;//选择不唯一int cur q.front();if(cur ! org[i]) return false;//跟序列不匹配q.pop();for(int i 0; i g[cur].size(); i){if(--indegree[g[cur][i]] 0)q.push(g[cur][i]);//入队为0 的入队}}if(i ! n) return false;//有环return true;}
};216 ms 45.2 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
