Số theo thứ tự từ điển trong C++

Cho số nguyên n, trả về danh sách các số từ 1 đến n theo thứ tự từ điển (lexicographical order).

Ví dụ: n = 13 → [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9].

Thuật toán giải quyết (Duyệt tiền tố - DFS lặp)

Xây dựng dãy số bằng cách mở rộng tiền tố: từ curr thử curr*10 (con sâu hơn), nếu vượt quá n thì tăng curr và loại bỏ các số kết thúc bằng 0.

1. Khởi tạo mảng kết quả ret kích thước n, curr = 1.
2. Lặp i = 0 .. n-1:
   • ret[i] = curr.
   • Nếu curr * 10 <= n → curr *= 10 (đi sâu).
   • Ngược lại:
     • Nếu curr >= n → curr /= 10 (lùi lại).
     • curr++ (sang tiền tố tiếp theo).
     • Trong khi curr % 10 == 0 → curr /= 10 (bỏ qua các số như 20, 30... khi đã hết nhánh).
3. Trả về ret.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<auto> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> ret(n);
        int curr = 1;
        for (int i = 0; i < n; i++) {
            ret[i] = curr;
            if (curr * 10 <= n) curr *= 10;
            else {
                if (curr >= n) curr /= 10;
                curr++;
                while (curr % 10 == 0) curr /= 10;
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    print_vector(ob.lexicalOrder(20));
}

Đầu vào

20

Đầu ra

[1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 3, 4, 5, 6, 7, 8, 9, ]