剑指OfferII115.重构序列：拓扑排序结构题

剑指OfferII115.重构序列：拓扑排序结构题这是剑指OfferII115.重构序列，难度中等。标签：“图论”、“拓扑排序”、“图构造”、“图论BFS”给定一个长度为n的整数数组nums，其中nums是范围为1,n[1,n]的整数数组。还提供了一个二维整数数组sequences，其中sequences[i]是nums的子序列。检查nums是否是唯一的最短超序列。最短超序列是长度最短的序列，所有序列sequences[i]都是它的子序列。对于给定的数组序列，可能存在多个有效的超序列。例如，对于sequences=[[1,2],[1,3]]，有两个最短的超序列[1,2,3]和[1,3,2]。对于序列=[[1,2],[1,3],[1,2,3]]，唯一可能的最短超序列是[1,2,3]。[1,2,3,4]是一个可能的超序列，但不是最短的。如果nums是序列的唯一最短超序列，则返回true，否则返回false。子序列是可以从另一个序列中删除某些元素或不删除任何元素而不改变其他元素顺序的序列。示例1：输入：nums=[1,2,3],sequences=[[1,2],[1,3]]输出：false解释：有两种可能的超序列：[1,2,3]和[1,3,2]。序列[1,2]是[1,2,3]和[1,3,2]的子序列。序列[1,3]是[1,2,3]和[1,3,2]的子序列。返回false，因为nums不是唯一的最短超序列。复制代码示例2：输入：nums=[1,2,3],sequences=[[1,2]]输出：false解释：可能的最短超序列是[1,2]。序列[1,2]是它的子序列：[1,2]。返回false，因为nums不是最短的超序列。复制代码示例3：输入：nums=[1,2,3],sequences=[[1,2],[1,3],[2,3]]输出：true解释：可能的最短超序列是[1,2,3]。序列[1,2]是它的子序列：[1,2,3]。序列[1,3]是它的子序列：[1,2,3]。序列[2,3]是它的子序列：[1,2,3]。返回真，因为nums是唯一的最短超序列。复制代码提示：n==nums.lengthn==nums.lengthn==nums.length1<=n<=1041<=n<=1041<=n<=104numsis[1,n][1,n][1,n]范围内所有整数的排列1<=sequences.length<=1041<=sequences.length<=10^41<=sequences.length<=1041<=sequences[i].length<=1041<=sequences[i].length<=1041<=sequences[i].length<=1041<=sum(sequences[i].length)<=1051<=sum(sequences[i].length)<=10^51<=sum(序列[i].length)<=1051<=序列[i][j]<=n1<=序列[i][j]<=n1<=序列[i][j]<=nsequencesAllarraysareuniquesequences[i]是一个子序列拓扑排序+nums的结构为了方便，我们让sequences为ss。根据题意，如果我们可以用所有的ss[i]ss[i]ss[i]构造一个唯一的序列，且序列与nums相同，则返回True，否则返回False。将每个ss[i]ss[i]ss[i]视为对ss[i]ss[i]ss[i]中包含的点的上下文约束，我们可以将问题转化为拓扑排序问题。应用所有ss[i]ss[i]ss[i]结构新图：在ss[i]=[A1,A2,...,Ak]ss[i]=[A_1,A_2,...,A_k]ss[i]=[A1,A2,...,Ak]，我们将其转化为点A1A_1A1->A2A_2A2->...->AkA_kAk的有向图，并统计每个点的点的入度状态。然后对新图进行拓扑排序，将结构对应的拓扑序列与nums进行比较。在实现上，因为在拓扑排序的过程中，出口点的顺序就是拓扑序，所以我们不需要保持整个拓扑序不变。我们只需要用一个变量loc记录当前拓扑序的下标，设置出口点ttt和nums[loc]nums[loc]nums[loc]即可。拓扑排序过程中，如果ttt不等于nums[loc]nums[loc]nums[loc]（结构出来的plan和nums不一样）或者某个展开过程中发现队列元素超过111个（此时可能的原因是：：“初始入度为000的点不止一个或者有些点基本不在ssssss”或者“新入度为000的点不止一个”由单次展开生成，即拓扑顺序不唯一")，则直接返回False，Java代码：classSolution{intN=10010,M=N,idx;int[]he=newint[N],e=newint[M],ne=newint[M],in=newint[N];voidadd(inta,intb){e[idx]=b;ne[idx]=he[a];他[a]=idx++;在[b]++中；}publicbooleansequenceReconstruction(int[]nums,int[][]ss){intn=nums.length;Arrays.fill(he,-1);for(int[]s:ss){for(inti=1;id=newArrayDeque<>();对于(inti=1;i<=n;i++){if(in[i]==0)d.addLast(i);}诠释位置=0;while(!d.isEmpty()){如果(d.size()!=1)返回false;intt=d.pollFirst();如果(nums[loc++]!=t)返回假；对于(inti=he[t];i!=-1;i=ne[i]){intj=e[i];如果(--in[j]==0)d.addLast(j);}}返回真；}}复制代码TypeScript代码：constN=10010,M=Nconsthe:number[]=newArray(N).fill(-1),e=newArray(N).fill(0),ne=newArray(N).fill(0),ind=newArray(N).fill(0);letidx=0functionadd(a:number,b:number):void{e[idx]=bne[idx]=he[a]he[a]=idx++ind[b]++}functionsequenceReconstruction(nums:number[],ss:number[][]):boolean{he.填充（-1）；ind.fill(0)idx=0constn=nums.lengthfor(constsofss){for(leti=1;i()lethead=0,tail=0for(leti=1;i<=n;i++){if(ind[i]==0)stk[tail++]=i}让loc=0while(head1)returnfalseconstt=stk[head++]if(nums[loc++]!=t)returnfalsefor(leti=he[t];i!=-1;i=ne[i]){constj=e[i]if(--ind[j]==0)stk[tail++]=j}}returntrue};复制代码时间复杂度：图构造复杂度为O(∑i=0n?1ss[i].length)O(\sum_{i=0}^{n-1}ss[i].length)O(∑i=0n?1ss[i].length);运行拓扑排序的复杂度为O(n+∑i=0n?1ss[i].length)O(n+\sum_{i=0}^{n-1}ss[i].length)O(n+∑i=0n?1ss[i].length)整体复杂度为O(n+∑i=0n?1ss[i].length)O(n+\sum_{i=0}^{n-1}ss[i].length)O(n+∑i=0n?1ss[i].length)空间复杂度：O(n+∑i=0n?1ss[i]。length)O(n+\sum_{i=0}^{n-1}ss[i].length)O(n+∑i=0n?1ss[i].length)最后这是第一个offer在我们的系列文章《刷LeetCode》II115篇中。该系列于2021/01/01开始。截至开课之日，LeetCode共有1916题，其中部分为锁题。我们将首先清除所有无锁问题。本系列文章除了讲解解题思路外，会尽量给出最简单的代码。如果涉及通用方案，会有相应的代码模板。