การสร้างลำดับใหม่ใน C ++

สมมติว่าเราต้องตรวจสอบว่า org ของซีเควนซ์ดั้งเดิมนั้นสามารถสร้างขึ้นมาใหม่อย่างเฉพาะตัวจากซีเควนซ์ใน seqs ได้หรือไม่ ลำดับเดิมคือการเรียงสับเปลี่ยนของจำนวนเต็มตั้งแต่ 1 ถึง n และ n ในช่วง 1 ≤ n ≤ 10^4 ในที่นี้ การสร้างใหม่หมายถึงการสร้างลำดับลำดับที่สั้นที่สุดในลำดับ เราต้องตรวจสอบว่ามีลำดับเดียวเท่านั้นที่สามารถสร้างใหม่จาก seqs ได้หรือไม่และเป็นลำดับดั้งเดิม

ดังนั้น หากอินพุตเป็นเหมือน org =[1,2,3], seqs =[[1,2],[1,3]] ผลลัพธ์จะเป็นเท็จ เพราะ [1,2,3] ไม่ใช่ ลำดับเดียวเท่านั้นที่สามารถสร้างใหม่ได้ เนื่องจาก [1,3,2] เป็นลำดับที่ถูกต้องที่สร้างใหม่ได้

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน ok() ซึ่งจะใช้เวลา v1, v2,

• ถ้าขนาดของ v1 ไม่เท่ากับขนาดของ v2 ดังนั้น −

  • คืนค่าเท็จ

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาด v1 อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • ถ้า v1[i] ไม่เท่ากับ v2[i] ดังนั้น −

    • คืนค่าเท็จ

• คืนความจริง

• จากวิธีหลักให้ทำดังนี้

• n :=ขนาดของลำดับดั้งเดิม

• กำหนดกราฟขนาดอาร์เรย์ (n + 1)

• กำหนดหนึ่งแผนที่ในองศา

• idx :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ seqs ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • ถ้าขนาดของ seqs[i]>=1 และ (seqs[i, 0]> n หรือ seqs[i, 0] <1) แล้ว −

    • คืนค่าเท็จ

  • ถ้าขนาดของ seqs[i]>=1 และไม่นับจำนวนการเรียก (seqs[i, 0]) ของ indegree ดังนั้น −

    • indegree[seqs[i, 0]] :=0

  • สำหรับการเริ่มต้น j :=1 เมื่อ j <ขนาดของ seqs[i] อัปเดต (เพิ่ม j โดย 1) ให้ทำ -

    • u :=seqs[i, j - 1]

    • v :=seqs[i, j]

    • แทรก v ที่ส่วนท้ายของกราฟ[u]

    • (เพิ่มขึ้น indegree[v] โดย 1)

    • ถ้า u> n หรือ v> n หรือ u <1 หรือ v <1 แล้ว −

      • คืนค่าเท็จ

• กำหนดหนึ่งคิว

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • ถ้าฉันอยู่ใน indegree และ indegree[i] เท่ากับ 0 แล้ว −

    • แทรก i ลงใน q

• ในขณะที่ (ไม่ใช่ q ว่างเปล่า) ทำ -

  • ถ้าขนาดของ q> 1 แล้ว −

    • คืนค่าเท็จ

  • ถ้า idx เท่ากับขนาดของ org แล้ว −

    • คืนค่าเท็จ

  • โหนด :=องค์ประกอบแรกของ q

  • ลบองค์ประกอบออกจาก q

  • หาก org[idx] ไม่เท่ากับโหนด ดังนั้น −

    • คืนค่าเท็จ

  • (เพิ่ม idx ขึ้น 1)

  • สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของกราฟ[โหนด] อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

    • v :=กราฟ[โหนด ผม]

    • (ลดลง indegree[v] โดย 1)

    • ถ้า indegree[v] เท่ากับ 0 แล้ว −

      • แทรก v ลงใน q

• คืนค่า true เมื่อ idx เท่ากับขนาดของ org

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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