資料結構
網路
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 次檢視
