数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的序列重建
假设我们必须检查原始序列 org 是否可以从 seqs 中的序列唯一重建。原始序列是 1 到 n 的整数的排列，并且 n 的范围为 1 ≤ n ≤ 10^4。这里的重建意味着创建 seqs 中序列的最短公共超序列。我们必须检查是否只有一个序列可以从 seqs 中重建，并且它是原始序列。
因此，如果输入类似于 org = [1,2,3]，seqs = [[1,2],[1,3]]，则输出将为 false，因为 [1,2,3] 不是唯一可以重建的序列，因为 [1,3,2] 也是可以重建的有效序列。
为了解决这个问题，我们将遵循以下步骤 -
定义一个函数 ok()，它将接收 v1、v2，
如果 v1 的大小不等于 v2 的大小，则 -
返回 false
对于初始化 i := 0，当 i < v1 的大小，更新（i 增加 1），执行 -
如果 v1[i] 不等于 v2[i]，则 -
返回 false
返回 true
从主方法执行以下操作
n := 原始序列的大小
定义一个大小为 (n + 1) 的数组 graph
定义一个映射 indegree
idx := 0
对于初始化 i := 0，当 i < seqs 的大小，更新（i 增加 1），执行 -
如果 seqs[i] 的大小 >= 1 且 (seqs[i, 0] > n 或 seqs[i, 0] < 1)，则 -
返回 false
如果 seqs[i] 的大小 >= 1 且 indegree 中不包含 seqs[i, 0] 的计数，则 -
indegree[seqs[i, 0]] := 0
对于初始化 j := 1，当 j < seqs[i] 的大小，更新（j 增加 1），执行 -
u := seqs[i, j - 1]
v := seqs[i, j]
将 v 插入到 graph[u] 的末尾
(indegree[v] 增加 1)
如果 u > n 或 v > n 或 u < 1 或 v < 1，则 -
返回 false
定义一个队列
对于初始化 i := 1，当 i <= n，更新（i 增加 1），执行 -
如果 i 在 indegree 中且 indegree[i] 等于 0，则 -
将 i 插入到 q 中
当 (q 不为空) 时，执行 -
如果 q 的大小 > 1，则 -
返回 false
如果 idx 等于 org 的大小，则 -
返回 false
node := q 的第一个元素
从 q 中删除元素
如果 org[idx] 不等于 node，则 -
返回 false
(idx 增加 1)
对于初始化 i := 0，当 i < graph[node] 的大小，更新（i 增加 1），执行 -
v := graph[node, i]
(indegree[v] 减少 1)
如果 indegree[v] 等于 0，则 -
将 v 插入到 q 中
当 idx 等于 org 的大小时返回 true
示例
让我们看看以下实现以获得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(vector <int<& v1, vector <int<& v2){
if (v1.size() != v2.size())
return false;
for (int i = 0; i < v1.size(); i++) {
if (v1[i] != v2[i])
return false;
}
return true;
}
bool sequenceReconstruction(vector<int<& org, vector<vector<int<>& seqs){
int n = org.size();
vector<int< graph[n + 1];
unordered_map<int, int> indegree;
int idx = 0;
for (int i = 0; i < seqs.size(); i++) {
if (seqs[i].size() >= 1 && (seqs[i][0] > n || seqs[i][0] < 1))
return false;
if (seqs[i].size() >= 1 && !indegree.count(seqs[i][0])) {
indegree[seqs[i][0]] = 0;
}
for (int j = 1; j < seqs[i].size(); j++) {
int u = seqs[i][j - 1];
int v = seqs[i][j];
graph[u].push_back(v);
indegree[v]++;
if (u > n || v > n || u < 1 || v < 1)
return false;
}
}
queue<int< q;
for (int i = 1; i <= n; i++) {
if (indegree.count(i) && indegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
if (q.size() > 1) {
return false;
}
if (idx == org.size()) {
return false;
}
int node = q.front();
q.pop();
if (org[idx] != node) {
return false;
}
idx++;
for (int i = 0; i < graph[node].size(); i++) {
int v = graph[node][i];
indegree[v]--;
if (indegree[v] == 0) {
q.push(v);
}
}
}
return idx == org.size();
}
};
main(){
Solution ob;
vector<int< v = {1,2,3};
vector<vector<int<> v1 = {{1,2},{1,3}};
cout << (ob.sequenceReconstruction(v, v1));
}输入
{1,2,3}, {{1,2},{1,3}}输出
0
184 次查看
