algo-aha

1~n数字的字典序

• https://leetcode.com/problems/lexicographical-numbers/

vector<int> lexicalOrder(int n) {
    // 十叉树的前序遍历
    vector<int> ans;
    for (int i = 1; i <= 9; i++) {
        preorder(i, n, ans);
    }
    return ans;
}

void preorder(int x, int n, vector<int> &ans) {
    if (x > n) return;
    ans.push_back(x);
    for (int i = 0; i <= 9; i++) {
        preorder(x * 10 + i, n, ans);
    }
}

[1,n]中字典序第k小的数

• https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/

int findKthNumber(int n, int k) {
    int curr = 1;
    while (k > 1) {
        int count = countNums(curr, n);
        if (k > count) { // 走右兄弟节点
            curr++;
            k -= count;
        } else { // 走最左子节点
            curr *= 10;
            k--;
        }
    }
    return curr;
}

// 想象十叉树中，以数p为根的子树含多少[1,n]间的数？
// 可累加[p,p+1)、[p*10,(p+1)*10)、[p*100,(p+1)*100)、... 与[1,n]重合的部分
int countNums(int p, long n) {
    int count = 0;
    long start = p, end = p + 1;
    while (start <= n) {
        count += min(end, n + 1) - start;
        start *= 10, end *= 10;
    }
    return count;
}