LeetCodePermutation Summary

7月 23 2014

这里把leetcode里面permutation的题目总结一下，记得一开始看的时候，发现心里很不清楚，next_permutation也是调用库的，看了邹博的PPT
之后加上之前看的permutation基本思路理清楚了。

我直接在leetcode上coding，为了模拟纸上coding的效果

普通的permutation，如果换成字符串的话也是一样的：

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > permutationvec;
        permutation(num,0,num.size()-1,permutationvec);
        return permutationvec;
    }

    void permutation(vector<int> num, int from, int to, vector<vector<int> >& permutationvec)
    {
        if(from>to)
        {
            vector<int> eachpervec;
            for(int i=0;i<=to;i++)
                eachpervec.push_back(num[i]);
            permutationvec.push_back(eachpervec);
        }
        else
        {
            for(int i=from;i<=to;i++)
            {
                swap(num[from],num[i]);
                permutation(num,from+1,to, permutationvec);
                swap(num[from],num[i]);
            }
        }
    }
};

按照邹博的函数参数风格写，感觉自己萌萌哒！！！

然后是带有重复数的permutation，只要加一个函数，判断里面是否a[from,i-1] 中是否有数等于a[i] 就可以了。

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > permutationvec;
        permutation(num,0,num.size()-1,permutationvec);
        return permutationvec;
    }
    bool IsSwap(vector<int> num, int from, int i)
    {
        for(int j=from;j<=i-1;j++)
        {
            if(num[i]==num[j])
                return false;
        }
        return true;
    }
    void permutation(vector<int> num, int from, int to, vector<vector<int> >& permutationvec)
    {
        if(from>to)
        {
            vector<int> eachpervec;
            for(int i=0;i<=to;i++)
                eachpervec.push_back(num[i]);
            permutationvec.push_back(eachpervec);
        }
        else
        {
            for(int i=from;i<=to;i++)
            {
                if(!IsSwap(num,from,i)) continue;
                swap(num[from],num[i]);
                permutation(num,from+1,to, permutationvec);
                swap(num[from],num[i]);
            }
        }
    }
};

然后返回kth 排列，由于邹博所说的，next_permutation可以天然的去除里面有重复数的case，但是我已开始用next_permutation发现TLE了，显然每次都调用这个然后n!次调用非常费时间，还是普通permutation然后
记录下第k次的permutation的结果！

这里面我定义了一下类的成员，减少递归函数的参数，避免潜在的栈溢出情况，递归有一点很不好，就是如果我中间找到了结果想返回时返回不了的，因为栈已经压到这么深了，而迭代则可以通过break来达到目的。

class Solution {
public:
    string result;
    int kth;

    string getPermutation(int n, int k) {
        kth=k;
        string str="";
        for(int i=1;i<=n;i++)
            str+=char(i+'0');

        permutation(str,0,str.size()-1);
        return result;
    }

    void permutation(string num, int from, int to)
    {
        if(from>to)
        {

            //string eachpervec;
            //for(int i=0;i<=to;i++)
                //eachpervec.push_back(num[i]);
            //    eachpervec+=num[i];
            kth--;
            if(kth==0)
                result=num;
            //permutationvec.push_back(eachpervec);
        }
        else
        {
            for(int i=from;i<=to;i++)
            {
                swap(num[from],num[i]);
                permutation(num,from+1,to);
                swap(num[from],num[i]);
            }
        }
    }
};

还是TLE了o(╯□╰)o，所以还是需要非递归算法来剪枝达到减少不必要的继续递归了，但是非递归的都忘记了o(╯□╰)o

Posted by richard爱闹 - 7月 23 2014
如需转载，请注明：本文来自 Richard

留言