kangtuo

9月 12 2014

今天写了一道kth permutation 如果递归进去记录第k个时间复杂度是O(n!), 然后之前TLE其实本质是WA

现在写了一个基于选择的permutation，昨天去网易游戏宣讲会小炒肉写给我看，我很吃惊，因为一直写的是基于swap的，
然后和战神讨论，发现啊哈算法也是这种的，其实机遇swap的字典序输出也有思路，但是代码一直调不出不知是不是风水不好。

然后想起来逆康拓展开，瞿神提到过，但是没细看，后来和ahdoc大神吃饭，大神说到了具体的细节，于是看到伟哥写了一个非递归的算法，有点难写。

我决定第一次写逆康拓展开发现还挺好写的，时间复杂度O(n^2), 需要注意的是:

k— 因为除和取余都是0-based,
同时算出来的商也是0-based, 因此cnt++ 与curnum+1比
然后记住循环是n-1轮，最后遍历一遍把最后一个元素加进去。

1.2 的两次— ++ 不能合并消掉，因为例如n=3, k=6 第一次就算出3，后面0就没法弄了。因为涉及到去摸都是0-based，k—是必须的，同时商也是0based, 因此cnt++ 与curnum+1(curnum=k/(n-i)!)

class Solution
{
public:
    bool used[100000];
    int f(int n)
    {
        int product=1;
        for(int i=n;i>=1;i--) product*=i;
        return product;
    }
    string getPermutation(int n, int k)
    {
        string kthper;
        int cnt;
        memset(used,0,sizeof(bool)*n);
        int jie=f(n-1);
        k--;
        for(int i=1;i<n;i++)
        {
            int curnum=k/jie;
            k=k%jie;
            jie/=(n-i);
            cnt=0;
            for(int i=0;i<n;i++)
            {
                if(!used[i])
                {
                    cnt++;
                    if(cnt==(curnum+1))
                    {
                        kthper+=char(i+1+'0');
                        used[i]=1;
                    }
                }
            }
        }
        for(int i=0;i<n;i++)
            if(!used[i])
                kthper+=char(i+1+'0');
        return kthper;
    }
};

今天做到一道向量点积最大的题目，有种似曾相识的感觉，但是就是不记得怎么做了。

然后暴搜先用vector存了全排列结果MLE，然后换数组，每次遍历就计算点积，结果TLE，因为n=1000时，是1000的阶乘非常大了，算法肯定不行。

后来小炒肉大神说感觉像是a 增旭排，b降序排，然后对应向量点积，这就是最小，但是不好证明。

后来吃饭的时候，小炒肉大神想到了方法证明，a1b2>…bn 那么当交换a，例如交换a1,ak, 那么乘以b1带来的增加比乘以bk带来的降低要多，导致点积点积增加。
b1(ak-a1)>bk(ak-a1), 每次交换都是增加，后面的排列都比这个的点积大，因此这个点积是最小的。

今天看到C++为啥不是++C，因为后增运算还可以使用原始值，也即C，而C++是C继承过来的，是他的超集，如果++C就不能再沿用C了与实际不符，挺有趣的
http://www.cnblogs.com/maxwellp/archive/2012/02/11/2346844.html

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

留言