สมมติว่าเราต้องตรวจสอบว่าลำดับต้นฉบับ org สามารถสร้างใหม่ได้อย่างเฉพาะเจาะจงจากลำดับย่อยใน seqs ลำดับต้นฉบับเป็นการเรียงสับเปลี่ยนของจำนวนเต็มจาก 1 ถึง n และ n อยู่ในช่วง 1 ≤ n ≤ 10^4 การสร้างใหม่ในที่นี้หมายถึงการทำ shortest common supersequence ของลำดับย่อยใน 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 ถึงขนาดของ v1-1 ทำ −
ถ้า v1[i] ไม่เท่ากับ v2[i] แล้ว −
คืนค่า false
คืนค่า true
จากเมธอดหลักทำดังนี้ −
n := ขนาดของลำดับต้นฉบับ
กำหนดอาร์เรย์ graph ขนาด (n + 1)
กำหนดแมป indegree
idx := 0
ลูป i := 0 ถึงขนาดของ seqs-1 ทำ −
ถ้าขนาดของ seqs[i] >= 1 และ (seqs[i][0] > n หรือ seqs[i][0] < 1) แล้ว −
คืนค่า false
ถ้าขนาดของ seqs[i] >= 1 และไม่มี seqs[i][0] ใน indegree แล้ว −
indegree[seqs[i][0]] := 0
ลูป j := 1 ถึงขนาดของ seqs[i]-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 ถึง n ทำ −
ถ้า i อยู่ใน indegree และ indegree[i] เป็น 0 แล้ว −
แทรก i ลงใน q
ลูป while (q ไม่ว่าง) ทำ −
ถ้าขนาดของ q > 1 แล้ว −
คืนค่า false
ถ้า idx เท่ากับขนาดของ org แล้ว −
คืนค่า false
node := สมาชิกแรกของ q
ลบสมาชิกออกจาก q
ถ้า org[idx] ไม่เท่ากับ node แล้ว −
คืนค่า false
เพิ่ม idx ขึ้น 1
ลูป i := 0 ถึงขนาดของ graph[node]-1 ทำ −
v := graph[node][i]
ลด 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
