周星星

Appearance

题目 ​

给定一个长度为 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。
输入：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。
输入：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。
输入：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 <= 10 的 4 次方
  • nums  是  [1, n]  范围内所有整数的排列
  • 1 <= sequences.length <= 10 的 4 次方
  • 1 <= sequences[i].length <= 10 的 4 次方
  • 1 <= sum(sequences[i].length) <= 10 的 5 次方
  • 1 <= sequences[i][j] <= n
  • sequences  的所有数组都是 唯一 的
  • sequences[i]  是  nums 的一个子序列

理解题目 ​

sequences 是二维数组，nums 是一维数组。校验  sequences 二维数组中组成的最短序列与 nums 是一致的且唯一的，则返回 true ，否则返回 false。

题解 ​

检查每个相邻关系是否都出现过，只有都出现了才是唯一的。

答案 ​

ts
function sequenceReconstruction(nums: number[], sequences: number[][]): boolean {
    const hash = (prev:number,next:number):number=>{
        //1 <= n <= 10的4次方
        return prev << 14 | next
    }
    const s = new Set()
    let len = 0

    for(let seq of sequences){
        for(let i =0;i<seq.length-1;i++){
            s.add(hash(seq[i],seq[i++1]))
        }

        len += seq
    }

    for(let i=0;i<nums.length-1;i++){
        if(!s.has(hash(nums[i],nums[i+1]))){
            return false
        }
    }

    return s.size >0 || len === nums.length
}
function sequenceReconstruction(nums: number[], sequences: number[][]): boolean {
    const hash = (prev:number,next:number):number=>{
        //1 <= n <= 10的4次方
        return prev << 14 | next
    }
    const s = new Set()
    let len = 0

    for(let seq of sequences){
        for(let i =0;i<seq.length-1;i++){
            s.add(hash(seq[i],seq[i++1]))
        }

        len += seq
    }

    for(let i=0;i<nums.length-1;i++){
        if(!s.has(hash(nums[i],nums[i+1]))){
            return false
        }
    }

    return s.size >0 || len === nums.length
}