Tái tạo trình tự trong C ++

Giả sử chúng ta phải kiểm tra xem tổ chức trình tự ban đầu có thể được tạo lại duy nhất từ các trình tự trong seqs hay không. Dãy ban đầu là một hoán vị của các số nguyên từ 1 đến n và n trong phạm vi 1 ≤ n ≤ 10 ^ 4. Ở đây, việc tái tạo có nghĩa là tạo ra một siêu đoạn chung ngắn nhất của các trình tự trong seqs. Chúng tôi phải kiểm tra xem chỉ có một trình tự có thể được tạo lại từ các seq và đó là trình tự ban đầu.

Vì vậy, nếu đầu vào giống như org =[1,2,3], seqs =[[1,2], [1,3]], thì đầu ra sẽ là false, vì [1,2,3] không trình tự duy nhất có thể được tạo lại, vì [1,3,2] cũng là một trình tự hợp lệ có thể được tạo lại.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàm ok (), điều này sẽ lấy v1, v2,
nếu kích thước của v1 không bằng kích thước của v2, thì -
- trả về false
để khởi tạo i:=0, khi tôi
- nếu v1 [i] không bằng v2 [i] thì -
  - trả về false
trả về true
Từ phương thức chính, hãy làm như sau
n:=kích thước của chuỗi gốc
Xác định đồ thị mảng có kích thước (n + 1)
Xác định một bản đồ không có thời hạn
idx:=0
để khởi tạo i:=0, khi tôi
- nếu kích thước của seqs [i]> =1 và (seqs [i, 0]> n hoặc seqs [i, 0] <1), thì -
  - trả về false
- nếu kích thước của seqs [i]> =1 và không phải số lượng cuộc gọi (seqs [i, 0]) của người không xác định, thì -
  - indgree [seqs [i, 0]]:=0
- để khởi tạo j:=1, khi j
  - u:=seqs [i, j - 1]
  - v:=seqs [i, j]
  - chèn v vào cuối biểu đồ [u]
  - (tăng thời hạn [v] lên 1)
  - nếu u> n hoặc v> n hoặc u <1 hoặc v <1, thì -
    - trả về false
Xác định một hàng đợi
để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
- nếu tôi đang ở trong tình trạng không có nợ và không có thời hạn [i] bằng 0, thì -
  - chèn tôi vào q
while (không phải q trống), do -
- nếu kích thước của q> 1, thì -
  - trả về false
- nếu idx giống với kích thước của tổ chức, thì -
  - trả về false
- node:=phần tử đầu tiên của q
- xóa phần tử khỏi q
- nếu org [idx] không bằng nút, thì -
  - trả về false
- (tăng idx lên 1)
- để khởi tạo i:=0, khi i
  - v:=graph [node, i]
  - (giảm thời hạn [v] đi 1)
  - nếu hệ số [v] bằng 0, thì -
    - chèn v vào q
trả về true khi idx giống với kích thước của tổ chức

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

{1,2,3}, {{1,2},{1,3}}

Tái tạo trình tự trong C ++

Ví dụ

Đầu vào

Đầu ra