題目資訊

題目編號: 1718
題目連結: Construct the Lexicographically Largest Valid Sequence
主題: Array, Backtracking

題目敘述

給定一個整數 $n$，找到一個符合以下所有條件的序列：

整數 $1$ 在序列中出現一次。
每個介於 $2$ 到 $n$ 之間的整數在序列中出現兩次。
對於每個介於 $2$ 和 $n$ 之間的整數 $i$，$i$ 的兩次出現之間的距離正好是 $i$。

數列中兩個數字 $a[i]$ 和 $a[j]$ 的距離是它們索引的絕對差 $|j - i|$。

返回 按字典序最大的序列。在給定的限制條件下，可保證總是有解。

若序列 $a$ 比序列 $b$ （長度相同）字典序大，則在 $a$ 和 $b$ 不同的第一個位置，序列 $a$ 的數字大於 $b$ 中對應的數字。例如，$[0,1,9,0]$ 比 $[0,1,5,6]$ 字典序大，因為它們在第三個數字不同，且 $9$ 大於 $5$。

範例 1:

輸入: n = 3
輸出: [3,1,2,3,2]
解釋: [2,3,2,1,3] 也是一個有效的序列，但 [3,1,2,3,2] 是字典序最大有效序列。

範例 2:

輸入: n = 5
輸出: [5,3,1,4,3,5,2,4,2]

限制條件:

$1 \leq n \leq 20$

直覺

這個問題要求構造一個序列，該序列必須包含介於 $1$ 到 $n$ 之間的整數，並且滿足特定的出現和位置約束。主要挑戰在於找到字典序最大的有效序列。由於每個整數從 $2$ 到 $n$ 必須在序列中出現兩次且相隔的距離為該整數的值，因此這個問題本質上是個排列挑戰。透過利用回溯法，我們可以探索每個整數的潛在放置位置，確保滿足約束，同時追求最大可能的序列。

解法

解決此問題的方法涉及使用回溯法。我們的目標是系統性地探索所有可能的整數放置，從 $n$ 到 $1$ 依次放在初始大小為 $2n-1$ 的序列陣列中。具體步驟如下：

初始化：
- 建立一個序列陣列，初始填上 -1 以表示空位。此陣列的大小為 $2n-1$，考慮到最大整數 $n$ 所需的距離。
- 使用一個布林陣列 used 來追蹤從 $1$ 到 $n$ 的每個數是否已經被放置在序列中。
回溯函數：
- 從第一個索引開始，嘗試將整數從 $n$ 到 $1$ 放入序列。以降序嘗試數字可以讓序列滿足字典序最大化。
- 跳過已經被填充的索引。
- 對於每個數字，確保如果不是 1，那麼必須有足夠的空間以滿足正確的距離約束（即可以放置在位置 i 和 i + currentNum）。
- 將該數字標記為已使用，並將其放在序列的正確位置上。
- 以遞迴方式調用回溯函數以處理下一個索引。
- 如果在任何時刻，放置某個數字未能導致一個完整且有效的序列，則撤銷更改（回溯），並嘗試下一個可能的數字。
解的驗證：
- 如果回溯完成後所有位置都正確填滿，則序列是完整的。
- 如果所有數字都被成功放置且滿足約束，則返回該序列。

此演算法有效地利用了回溯原則，通過考慮約束並以遞迴方式嘗試完成它們，並且總是首先選擇最大的數字，以確保滿足字典序的要求。

程式碼

C++

class Solution {
public:
    // 回溯函數，用來填充序列
    bool backtrack(vector<int>& sequence, vector<bool>& used, int currentIndex, int n) {
        // 如果已經填滿所有需要的位置，則序列已完成
        if (currentIndex >= 2 * n - 1) return true;

        // 跳過已經填好的位置
        if (sequence[currentIndex] != -1) return backtrack(sequence, used, currentIndex + 1, n);

        // 嘗試從 n 到 1 的數字
        for (int currentNum = n; currentNum > 0; currentNum--) {
            // 跳過已經使用過的數字
            if (used[currentNum]) continue;

            // 確保有足夠的空間在要求的距離放置 currentNum
            if (currentNum != 1 && (currentIndex + currentNum >= 2 * n - 1 || sequence[currentIndex + currentNum] != -1)) continue;

            // 將當前數字標記為已使用
            used[currentNum] = true;

            // 在序列中放置當前數字
            if (currentNum == 1) {
                sequence[currentIndex] = currentNum;
            } else {
                sequence[currentIndex] = sequence[currentIndex + currentNum] = currentNum;
            }

            // 繼續對下一個索引進行回溯
            if (backtrack(sequence, used, currentIndex + 1, n)) return true;

            // 如果放置 currentNum 沒有導致解決方案，則回復更改
            if (currentNum != 1) sequence[currentIndex + currentNum] = -1;
            used[currentNum] = false;
            sequence[currentIndex] = -1;
        }
        return false;
    }

    // 主函數來構建字典序最大的序列
    vector<int> constructDistancedSequence(int n) {
        // 用 -1 初始化序列以表示空位置
        vector<int> sequence(2 * n - 1, -1);
        
        // 初始化一個布林數組來追蹤已使用的數字
        vector<bool> used(n + 1, false);
        
        // 從索引 0 開始進行回溯
        backtrack(sequence, used, 0, n);
        
        // 返回構造的序列
        return sequence;
    }
};

Python

class Solution:
    # 回溯函式以填充序列
    def backtrack(self, sequence, used, currentIndex, n):
        # 如果我們已填滿所有必需的位置，則序列已完成
        if currentIndex >= 2 * n - 1:
            return True

        # 跳過已填滿的位置
        if sequence[currentIndex] != -1:
            return self.backtrack(sequence, used, currentIndex + 1, n)

        # 嘗試放置從 n 到 1 的數字
        for currentNum in range(n, 0, -1):
            # 跳過已經使用過的數字
            if used[currentNum]:
                continue

            # 確保有足夠的空間按照要求的距離放置 currentNum
            if currentNum != 1 and (currentIndex + currentNum >= 2 * n - 1 or sequence[currentIndex + currentNum] != -1):
                continue

            # 標記當前數字為已使用
            used[currentNum] = True

            # 在序列中放置當前數字
            if currentNum == 1:
                sequence[currentIndex] = currentNum
            else:
                sequence[currentIndex] = sequence[currentIndex + currentNum] = currentNum

            # 繼續回溯以處理下一個索引
            if self.backtrack(sequence, used, currentIndex + 1, n):
                return True

            # 如果放置 currentNum 沒有導致解決方案，則恢復更改
            if currentNum != 1:
                sequence[currentIndex + currentNum] = -1
            used[currentNum] = False
            sequence[currentIndex] = -1
        return False

    # 主函式以構建字典順序最大的序列
    def constructDistancedSequence(self, n):
        # 使用 -1 初始化序列以表示空位置
        sequence = [-1] * (2 * n - 1)
        
        # 初始化布林陣列以追蹤已使用的數字
        used = [False] * (n + 1)
        
        # 從索引 0 開始回溯
        self.backtrack(sequence, used, 0, n)
        
        # 返回構建的序列
        return sequence

複雜度分析

時間複雜度: $O(n!)$
此解法的時間複雜度由回溯法決定。在最壞的情況下，演算法將嘗試從 $n$ 到 $1$ 的數字，並檢查每個數字的所有可能位置。由於該函數需要探索所有排列以找到一個有效的序列，其複雜度可近似為 $O(n!)$，其中 $n$ 是輸入整數。此複雜度的產生是因為當 $n$ 的值增大時，探索的排列數量以階乘方式增加。
空間複雜度: $O(n)$
空間複雜度主要來自於遞歸調用棧的額外存儲，以及 sequence 和 used 向量所需的存儲空間。sequence 向量需要 $O(2n - 1) \approx O(n)$ 空間，並且 used 向量需要 $O(n)$ 空間。因此，總體空間複雜度為 $O(n)$。

CS Note
En

Leetcode 1718. Construct the Lexicographically Largest Valid Sequence

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析