444. 序列重建

Difficulty
Medium
Tags
拓扑排序
图
URL
https://leetcode.cn/problems/sequence-reconstruction/
Star
给定一个长度为 n 的整数数组 nums ，其中 nums 是范围为 [1，n] 的整数的排列。还提供了一个 2D 整数数组 sequences ，其中 sequences[i] 是 nums 的子序列。 检查 nums 是否是唯一的最短 超序列 。最短 超序列 是 长度最短 的序列，并且所有序列 sequences[i] 都是它的子序列。对于给定的数组 sequences ，可能存在多个有效的 超序列 。
例如，对于 sequences = [[1,2],[1,3]] ，有两个最短的 超序列 ，[1,2,3] 和 [1,3,2] 。 而对于 sequences = [[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]的子序列。
因为 nums 不是唯一最短的超序列，所以返回false。
示例 2：
输入：nums = [1,2,3], sequences = [[1,2]]
输出：false
解释：最短可能的超序列为 [1,2]。
序列 [1,2] 是它的子序列：[1,2]。
因为 nums 不是最短的超序列，所以返回false。
示例 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 是唯一最短的超序列，所以返回true。
提示：
  • n == nums.length
  • 1 <= n <= 104
  • nums 是 [1, n] 范围内所有整数的排列
  • 1 <= sequences.length <= 104
  • 1 <= sequences[i].length <= 104
  • 1 <= sum(sequences[i].length) <= 105
  • 1 <= sequences[i][j] <= n
  • sequences 的所有数组都是 唯一 的
  • sequences[i] 是 nums 的一个子序列

法 1 拓扑排序 + 构造

思路 为了方便，我们令 sequences 为 ss。
根据题意，如果我们能够利用所有的 ss[i] 构造出一个唯一的序列，且该序列与 nums 相同，则返回 True，否则返回 False。
将每个 ss[i] 看做对 ss[i] 所包含点的前后关系约束，我们可以将问题转换为拓扑排序问题。
利用所有 ss[i] 构造新图：对于 ss[i] = [A_1, A_2, ..., A_k]，我们将其转换为点 A_1-> A_2-> ... -> A_k的有向图，同时统计每个点的入度情况。
然后在新图上跑一遍拓扑排序，构造对应的拓扑序列，与 nums 进行对比。
实现上，由于拓扑排序过程中，出点的顺序即为拓扑序，因此我们并不需要完整保存整个拓扑序，只需使用一个变量 loc 来记录当前拓扑序的下标，将出点 tt 与 nums[loc]nums[loc] 做比较即可。
在拓扑序过程中若有 tt 不等于 nums[loc]nums[loc]（构造出来的方案与 nums 不同） 或某次拓展过程中发现队列元素不止 11 个（此时可能的原因有 :「起始入度为 00 的点不止一个或存在某些点根本不在 ssss 中」或「单次拓展新产生的入度为 00 的点不止一个，即拓扑序不唯一」），则直接返回 False，
题解
class Solution:
    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        # 建 图  & 入度表
        in_degree = [0 for _ in range(len(nums)+1)]
        in_degree[0] = float("inf")
        graph = collections.defaultdict(list)

        for seq in sequences:
            for i in range(1, len(seq)):
                graph[seq[i-1]].append(seq[i])
                in_degree[seq[i]] += 1
        
        # 找入度为0的为起点
        queue = deque()
        for i in range(0, len(in_degree)):
            if in_degree[i] == 0:
                queue.append(i)

        loc = 0
        while queue:
            
            if len(queue) > 1:
                return False

            cur_num = queue.popleft()
            if cur_num != nums[loc]:
                return False
            loc += 1

            for nxt_num in graph[cur_num]:
                in_degree[nxt_num] -= 1
                if in_degree[nxt_num] == 0:
                    queue.append(nxt_num)

        return True

法2 技巧

思路
条件构成一棵树，就是在树中找是否存在一条路径是 nums。
题解
class Solution:
    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:

        # 记录每个数的先后关系
        tree = defaultdict(set)
        for seq in sequences:
            for i in range(1, len(seq)):
                tree[seq[i-1]].add(seq[i])
      
        for i in range(1, len(nums)):
            if nums[i] not in tree[nums[i-1]]: 
                return False
        return True