【Permutation Sequence】cpp

题目：

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 (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

代码：

class Solution {

public:

    string getPermutation(int n, int k)

    {

        std::stringstream result;

        // if the digit has been used

        int flag[];

        for(int i = ; i<; ++i) flag[i]=;

        // calculate each digit

        int factorical,quotient,remaind=k-;

        for (int i = ; i<=n; ++i)

        {

             factorical = Solution::getFactorical(n-i);

            quotient = remaind/factorical;

            int tmp = ;

            for(int j=; j<=; ++j){

                tmp = tmp + flag[j];

                if ( tmp==(quotient+) ){

                    quotient = j;

                    break;

                }

            }

            result << quotient;

            flag[quotient] = ;

            remaind = remaind%factorical; // update remaind

        }

        return result.str();

    }

    static int getFactorical(int n){

        int result = ;

        for (int i = ; i <= n; ++i){

            result = result * i;

        }

        return result;

    }

};

Tips:

1. 主要思路是康托编码，具体什么是康托编码（http://blog.sina.com.cn/s/blog_4bf7b6580100l2zs.html）

2. 把计算阶乘的代码单独列出来

3. 对于c++如何将int转为字符不太懂，因此用了sstream的这个方法，后面遇到其他的方法再改进一下。

======================================================

第二次过这道题，对康托编码的算法有些生疏了，参考了blog才回忆起来。然后扫了一些细节，形成了自己的代码。

class Solution {

public:

        string getPermutation(int n, int k)

        {

            vector<char> ret;

            vector<bool> visit(,false);

            k = k-;

            for ( int i=n-; i>=; --i)

            {

                int factor = Solution::factorial(i);

                int num_less = k / factor;

                // find num less

                int j=;

                int count = ;

                for ( ; j<; ++j )

                {

                    if ( !visit[j] )

                    {

                        if ( count==num_less ) break;

                        count++;

                    }

                }

                visit[j] = true;

                ret.push_back(j+'');

                k = k % factor;

            }

            return string(ret.begin(),ret.end());

        }

        static int factorial(int n)

        {

            if ( n== || n== ) return ;

            int ret = ;

            for ( int i = ; i<=n; ++i) ret = ret * i;

            return ret;

        }

};

巴特西

【Permutation Sequence】cpp

最新文章

热门文章