今日题目

https://leetcode.com/problems/construct-the-lexicographically-largest-valid-sequence/description/

思路

本题要求按照给定条件构造出满足要求的序列。

方法

注意到 $N \le 20$，因此可以用暴力搜索来找到答案。

复杂度

  • 时间复杂度：$O(N^N)$，其中 N 的定义与题目一致。

  • 空间复杂度：$O(N)$，其中 N 的定义与题目一致。

代码

普通 DFS 解法

class Solution:
    def dfs(self, pos, n, vis, pls):
        if pos == 2 * n - 1:
            return pls
        # if we enumerate to the end of the sequence, then we can return the answer.

        if pls[pos] != 0:
            return self.dfs(pos + 1, n, vis, pls)
        # if we place a number in the current position, then we can move to the next position.
        for i in range(n, 1, -1):
        # we enumerate from large to small so that we can get the largest sequence.
            if vis[i]:
                continue
            # if we use this number, then pass.
            if pos + i < 2 * n - 1 and pls[pos + i] == 0:
                pls[pos] = i
                pls[pos + i] = i
                vis[i] = True
                # put the number into the slot if it is available.
                ret = self.dfs(pos + 1, n, vis, pls)
                if ret is not None:
                    return ret
                vis[i] = False
                pls[pos] = 0
                pls[pos + i] = 0

        if vis[1]:
            return None
        vis[1] = True
        pls[pos] = 1
        ret = self.dfs(pos + 1, n, vis, pls)
        if ret is not None:
            return ret
        vis[1] = False
        pls[pos] = 0
        # special check for 1 becuase 1 only puts into one slot.

        return None

    def constructDistancedSequence(self, n: int) -> List[int]:
        pls = [0] * (2 * n - 1)
        # pls is the sequence that we place numbers        
        vis = [0] * (n+1)
        # visit is the sequence we test whether a number exists in the current sequence or not.
        return self.dfs(0, n, vis, pls)

更快的解法（备用）

注意到对于相同的输入，答案不会发生变化，因此可以直接将预先计算好的答案存储起来，对每次查询直接返回对应结果。

class Solution:
    def constructDistancedSequence(self, n: int) -> List[int]:
        ans = [
            [1],
            [2,1,2],
            [3,1,2,3,2],
            [4,2,3,2,4,3,1],
            [5,3,1,4,3,5,2,4,2],
            [6,4,2,5,2,4,6,3,5,1,3],
            [7,5,3,6,4,3,5,7,4,6,2,1,2],
            [8,6,4,2,7,2,4,6,8,5,3,7,1,3,5],
            [9,7,5,3,8,6,3,5,7,9,4,6,8,2,4,2,1],
            [10,8,6,9,3,1,7,3,6,8,10,5,9,7,4,2,5,2,4],
            [11,9,10,6,4,1,7,8,4,6,9,11,10,7,5,8,2,3,2,5,3],
            [12,10,11,7,5,3,8,9,3,5,7,10,12,11,8,6,9,2,4,2,1,6,4],
            [13,11,12,8,6,4,9,10,1,4,6,8,11,13,12,9,7,10,3,5,2,3,2,7,5],
            [14,12,13,9,7,11,4,1,10,8,4,7,9,12,14,13,11,8,10,6,3,5,2,3,2,6,5],
            [15,13,14,10,8,12,5,3,11,9,3,5,8,10,13,15,14,12,9,11,7,4,6,1,2,4,2,7,6],
            [16,14,15,11,9,13,6,4,12,10,1,4,6,9,11,14,16,15,13,10,12,8,5,7,2,3,2,5,3,8,7],
            [17,15,16,12,10,14,7,5,3,13,11,3,5,7,10,12,15,17,16,14,9,11,13,8,6,2,1,2,4,9,6,8,4],
            [18,16,17,13,11,15,8,14,4,2,12,2,4,10,8,11,13,16,18,17,15,14,12,10,9,7,5,3,6,1,3,5,7,9,6],
            [19,17,18,14,12,16,9,15,6,3,13,1,3,11,6,9,12,14,17,19,18,16,15,13,11,10,8,4,5,7,2,4,2,5,8,10,7],
            [20,18,19,15,13,17,10,16,7,5,3,14,12,3,5,7,10,13,15,18,20,19,17,16,12,14,11,9,4,6,8,2,4,2,1,6,9,11,8]
        ]
        return ans[n - 1]