Leetcode 一类组合计数问题

Leetcode 一类组合计数问题

引言

很久没有做组合计数的题目了，今天做一道 Leetcode Hard 的组合计数问题，发现花费了不少时间，特地来记录一下。

1643. 第 K 条最小指令

题意: 一个字符串，由 $h$ 个 'H' 和 $v$ 个 'V' 组成，求第 $k$ 小的字符串。

错解: 二进制 or DFS 枚举前 $k$ 个 ($k$ 可能很大，会超时)。

正解: 从前往后填 'H' 和 'V'。假设第 1 位填 'V'，那么它至少是第 $C_{h+v-1}^{h} + 1$ 个字符串，因为以 'H' 开头的有 $C_{h+v-1}^{h}$ 个。

• 如果 $k \lt C_{h+v-1}^{h} + 1$，说明假设错误，第 1 位应该填 'H';
• 反之，第 1 位必定为 'V'，只需向后找第 $k - C_{h+v-1}^{h}$ 个字符串就行。

依次类推即可。时间复杂度 $O((h+v)max(h, v))$

using ll = long long;
const int N = 30;
ll dp[N][N];

class Solution {
public:
    void init() {
        dp[0][0] = 1;
        for (int i = 1; i < N; ++i) {
            dp[i][0] = 1;
            for (int j = 1; j <= i; ++j) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
    }

    string kthSmallestPath(vector<int> &destination, int k) {
        init();
        int v = destination[0];
        int h = destination[1];

        string ans(h + v, ' ');
        for (int i = 0; i < ans.size(); ++i) {
            if (k <= dp[h + v - 1][v]) {
                ans[i] = 'H';
                --h;
            } else {
                ans[i] = 'V';
                k -= dp[h + v - 1][v];
                --v;
            }
        }
        return ans;
    }
};

60. 排列序列

这道题其实是很类似的，更简单，就不再赘述了。

class Solution {
public:
    string getPermutation(int n, int k) {
        auto dp = vector<int>(n + 1, 1);
        auto nth = vector<int>();
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1] * i;
            nth.emplace_back(i);
        }
        k--;
        string ans;
        for (int i = 1; i <= n; ++i) {
            ans += nth[k / dp[n - i]] + '0';
            nth.erase(nth.begin() + k / dp[n - i]);
            k %= dp[n - i];
        }
        return ans;
    }
};