Xin chào các bạn, Loser1 từ Learning AI with Loser đây! Hôm nay chúng ta tiếp tục series Leetcode Daily Challenge với Day 38. Cùng nhau phân tích một bài toán thú vị về chuỗi số nhé! 🚀

Input: n = 3
Output: [3,1,2,3,2]
Giải thích: 
[2,3,2,1,3] cũng là một dãy hợp lệ, nhưng [3,1,2,3,2] là dãy có thứ tự từ điển lớn nhất.
    

Input: n = 5
Output: [5,3,1,4,3,5,2,4,2]
    

Đề bài: 1718. Construct the Lexicographically Largest Valid Sequence 📝

Cho một số nguyên n, tìm một chuỗi thỏa mãn các điều kiện sau:

• Số 1 xuất hiện một lần trong chuỗi
• Mỗi số từ 2 đến n xuất hiện hai lần trong chuỗi
• Với mỗi số i từ 2 đến n, khoảng cách giữa hai lần xuất hiện của i phải đúng bằng i
• Khoảng cách giữa hai số trong chuỗi là hiệu tuyệt đối của chỉ số của chúng

Trả về chuỗi lớn nhất theo thứ tự từ điển. Luôn tồn tại ít nhất một lời giải cho bài toán này.

Ví dụ:

• Với n = 3, kết quả: [3,1,2,3,2]
• Với n = 5, kết quả: [5,3,1,4,3,5,2,4,2]

Intuition 💡

Khi tôi nhìn bài toán này, điều đầu tiên tôi nghĩ đến là: "Hmm, mình cần xây dựng một chuỗi với các ràng buộc phức tạp và tìm chuỗi lớn nhất có thể". Đây rõ ràng là một bài toán tổ hợp, và backtracking là một phương pháp tự nhiên để thử các khả năng khác nhau.

Ý tưởng cơ bản là:

1. 🏗️ Xây dựng chuỗi từ trái qua phải
2. 🔍 Với mỗi vị trí, thử đặt số lớn nhất có thể (để đảm bảo tính lexicographically largest)
3. 🔄 Nếu không thể đặt được số nào, quay lui và thử lại với cấu hình khác

🧩 → 🔍 → 🔄 → ✅

Approach 🛠️

1. 📊 Khởi tạo một mảng seq có độ dài 2n-1 (vì số 1 xuất hiện 1 lần, mỗi số từ 2 đến n xuất hiện 2 lần)
2. 🚩 Sử dụng một mảng used để đánh dấu những số đã được sử dụng
3. 🚶‍♂️ Bắt đầu từ vị trí 0 và thực hiện backtracking:

• Nếu vị trí hiện tại đã có số, chuyển sang vị trí tiếp theo
• Nếu chưa, thử đặt các số từ n xuống 1 (để đảm bảo tính lớn nhất theo thứ tự từ điển)
• Với mỗi số i:
  • Nếu i = 1, chỉ đặt một lần ☝️
  • Nếu i ≥ 2, đặt hai lần với khoảng cách đúng bằng i ✌️
• Nếu đặt thành công, tiếp tục với vị trí tiếp theo ➡️
• Nếu không thể đặt được, quay lui và thử số khác ⬅️

[0,0,0,0,0] → [3,0,0,3,0] → [3,1,0,3,0] → [3,1,2,3,2] ✓

Complexity 📈

• Time complexity: $$O(n!)$$ - trong trường hợp xấu nhất, chúng ta phải thử tất cả các hoán vị có thể ⏱️
• Space complexity: $$O(n)$$ - cho mảng seq có độ dài 2n-1 và mảng used có độ dài n+1 📦

Code 💻

#include <vector>
using namespace std;

class Solution {
public:
    int n;
    // used[i] = true nếu số i đã được sử dụng (đã đặt đầy đủ các lần xuất hiện của i)
    vector<bool> used;

    // Hàm đệ quy backtracking: pos là chỉ số hiện tại cần điền trong seq
    bool backtrack(vector<int>& seq, int pos) {
        // Nếu đã điền hết các vị trí trong seq, trả về true
        if(pos == seq.size())
            return true;
        // Nếu vị trí hiện tại đã có số, chuyển sang vị trí tiếp theo
        if(seq[pos] != 0)
            return backtrack(seq, pos + 1);

        // Duyệt các số từ n xuống 1 để đảm bảo tính lexicographically largest
        for (int i = n; i >= 1; i--) {
            if(used[i]) continue; // bỏ qua nếu số i đã được đặt

            // Nếu i == 1, chỉ cần đặt một lần duy nhất
            if(i == 1) {
                seq[pos] = 1;
                used[1] = true;
                if(backtrack(seq, pos + 1))
                    return true;
                // Backtrack
                seq[pos] = 0;
                used[1] = false;
            } 
            // Với i >= 2, cần đặt hai lần và khoảng cách giữa hai lần xuất hiện phải đúng bằng i
            else {
                // Kiểm tra xem vị trí thứ hai có hợp lệ không
                if(pos + i < seq.size() && seq[pos + i] == 0) {
                    seq[pos] = i;
                    seq[pos + i] = i;
                    used[i] = true;

                    if(backtrack(seq, pos + 1))
                        return true;

                    // Nếu không thành công, quay lại trạng thái ban đầu (backtrack)
                    seq[pos] = 0;
                    seq[pos + i] = 0;
                    used[i] = false;
                }
            }
        }
        return false;
    }

    vector<int> constructDistancedSequence(int n) {
        this->n = n;
        // Độ dài dãy: 2 * n - 1, vì số 1 xuất hiện 1 lần và các số từ 2 đến n xuất hiện 2 lần
        int len = 2 * n - 1;
        vector<int> seq(len, 0);
        used.assign(n + 1, false);

        backtrack(seq, 0);
        return seq;
    }
};

Trực quan hóa với ví dụ n=3 🎬

Hãy cùng nhau theo dõi cách thuật toán hoạt động với n=3:

1. 🎯 Khởi tạo seq = [0,0,0,0,0], used = [false,false,false,false]
2. 🎲 Bắt đầu với pos=0, thử đặt số 3:

• Đặt seq[0]=3, seq[3]=3, used[3]=true
• seq = [3,0,0,3,0] ✍️

1. 🎲 Chuyển đến pos=1, thử đặt số 2:

• Đặt seq[1]=2, seq[3]=2… ❌ Ồ không, seq[3] đã có số 3!
• Thử lại với số 1:
• Đặt seq[1]=1, used[1]=true
• seq = [3,1,0,3,0] ✍️

1. 🎲 Chuyển đến pos=2, thử đặt số 2:

• Đặt seq[2]=2, seq[4]=2, used[2]=true
• seq = [3,1,2,3,2] ✍️✅

1. 🎉 Tất cả các vị trí đã được điền, trả về true

Kết quả cuối cùng: [3,1,2,3,2] 🎯

Bước 1: [0,0,0,0,0]
Bước 2: [3,0,0,3,0]
Bước 3: [3,1,0,3,0]
Bước 4: [3,1,2,3,2]

Tổng kết 🌟

Bài toán này là một ví dụ điển hình của kỹ thuật backtracking trong lập trình. Chúng ta xây dựng chuỗi từng bước một, luôn ưu tiên các số lớn trước để đảm bảo tính "lexicographically largest".

Điểm mấu chốt là phải hiểu rõ các ràng buộc của bài toán và cách áp dụng chúng trong quá trình backtracking. Việc luôn thử các số từ lớn đến nhỏ đảm bảo chúng ta sẽ tìm được chuỗi lớn nhất có thể.

🔑 Tóm tắt thuật toán:

1. ➡️ Xây dựng từ trái qua phải
2. ⬇️ Thử số lớn nhất trước
3. 🔄 Backtrack khi cần thiết
4. ✅ Kết thúc khi điền đầy đủ

Backtracking 101:
📝 Thử từng khả năng
🔍 Kiểm tra tính hợp lệ
🔄 Quay lui nếu không thành công
✅ Lưu lại kết quả khi tìm thấy

Các bạn thấy bài toán này thế nào? Hãy để lại comment chia sẻ suy nghĩ của mình nhé! 💬

Hẹn gặp lại các bạn trong bài tiếp theo của series Leetcode Daily Challenge! 📚

Loser1 from Learning AI with Loser 🚀

CODE EDITOR

📌 Hashtags:
#leetcode #leetcodedaily #coding #datastructures #algorithms #learningwithlosers #leetcode 3066 # leetcodedaily38