拼多多笔试第三题（AB字符串排列组合）

事先说明，本人并未参加拼多多笔试，只是听室友参加了的感觉很难，我对第三题有点感兴趣。
这里我尝试给出第三题的一点想法，希望和牛友们探讨一下～

题目：给定m,n . 最多由m个a,n个b组成一个字符串，求所有字符串中排序为K的那个字符串。

我的思路是，这道题等价于构造一个二叉前缀树（并不需要真的构造，只是方便说明），左孩子就是添加A字母，右孩子就是添加B字母，而每个节点代表的串就是它从根结点（null）到本节点的路径。

那么按照字典序排列，就是给树上的节点编号，其实等价于前序遍历给所有节点编号。
好，那么问题就在于如何确定编号了！

对根结点，编号是0，根结点表示空字符串。
对根节点的左节点，编号是1，这个也没有问题。
关键在于对根结点的右节点怎么编号。

如果要知道右节点编号，我们必须知道左子树的大小，所以问题在于求树的大小。
树的大小其实就是指“最多n个A字符，最多m个B字符，最多能够组成几种串”，这个定义为count[n][m]。

其实可以用dp的思路解决。
状态转移方程：树大小=1*根节点+左子树大小+右子树大小。
其实就是count[n][m] = 1 + count[n - 1][m] + count[n][m - 1]。
dp过程是O(nm)的复杂度。

好了，现在求出了子树大小，就可以开始算K下标对应的节点了。
很简单，从根结点开始找，结果字符串为空；
如果左子树的大小比当前节点下标和K的差还大，那么就在左子树找，此时结果字符串添加A字符；
否则，在右子树找，此时结果字符串添加B字符。

这样应该是O(lg K)的时间复杂度（二叉搜索树的查找）。

所以总体时间复杂度为O(mn+lg K)，且空间复杂度为O(mn)。按理说是不会超时和超空间的吧（逃

代码不一定对，下面的table就是count数组，记录有n个A字符和m个B字符对应的树的size。

// Get the Kth string of the list of alphabetic order of strings, each containing at most n 'A's and m 'B's.
// 1 <= m, n <= 50
// K is a number in long
#include <iostream>
using namespace std;

// My idea: think of this permutation list as a tree.
// where alphabetic order means pre-order traversal order.
// The tree goes like this, with each node represents a string
// (the path from root to this node, e.g., the node indexed 2 stands for 'AA'):
/*
             null(0)
            /       \
          'A'(1)    'B'(...)
          /   \      \   \
        'A'(2)'B'(...)... ...
 */
// The size of left subtreee could be calculated using dp, which is O(mn) time complexity,
// with transfer equation: count[n, m] = 1 + count[n - 1, m] + count[n, m - 1];
// and then we calculate the node whose index is K, which is O(lg K).

int table[51][51];

void dp(int n, int m) {
    for (int i = 0; i <= n; i++)
        table[i][0] = i + 1;
    for (int i = 0; i <= m; i++)
        table[0][i] = i + 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            table[i][j] = table[i][j - 1] + table[i - 1][j] + 1;
}

int main() {
    int n, m;
    long long k, curr = 0;
    string res;
    cin >> n >> m >> k;
    dp(n, m);
    while (curr < k) {
        if ((n > 0 && table[n - 1][m] + curr < k) || n < 1) {
            // choose B
            if (n > 0)
                curr += table[n - 1][m] + 1;
            else
                curr += 1;
            res += 'B';
            m--;
        } else {
            // choose A
            curr += 1;
            res += 'A';
            n--;
        }
    }
    cout << res << endl;
    return 0;
}

#笔试题目##拼多多##校招#