Holy Shit

Holy Shit这样一系列的题：我完全不知道怎么做，即便想采用BF的方法，无奈只能看答案，结果答案还看不懂，分类都不知道如何分类的这样一系列的题。

1. Permutation Sequence The set [1,2,3,...,_n_] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

2. "123"

3. "132"
4. "213"
5. "231"
6. "312"
7. "321"

Given n and k, return the k permutation sequence.

Note:

• Given n will be between 1 and 9 inclusive.
• Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3

Output: “213”

Example 2:

Input: n = 4, k = 9

Output: “2314”

评论区的一个C++的答案)

class Solution {
public:
    string getPermutation(int n, int k) {
          int i, j, f=1;
        string s(n,'0');
        for(i = 1; i <= n; i++)
        {
            f *= i;
            s[i - 1] += i;
        }
        for(i=0,k--; i < n; i++)
        {
            f /= n - i;
            j = i + k/f;
            char c=s[j];
            for(;j>i;j--)
                s[j]=s[j-1];
            k%=f;
            s[i]=c;
        }
        return s;
    }
};