📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3008| 回复: 5
跳转到指定楼层
上一主题 下一主题
收起左侧

Amazon : 最大递增子序列

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
就是求一个数组的最大递增子序列 (不要求连续) 因该有多种方法

上一篇:facebook : 实现开方函数
下一篇:google : 最小窗口问题
🔗
Imbalism 2011-5-7 00:45:45 | 只看该作者
全局:
先把这个数组排序, 然后用转化为最长公共子序列问题, O(n^2) . 应该有更好的, 恩
回复

使用道具 举报

🔗
法兰天蝎 2011-5-7 00:53:44 | 只看该作者
全局:
返回值是长度还是子数组元素在原数组内的下标啊?
LS讲的不太明白,可以用DP解,也是O(n^2)
回复

使用道具 举报

🔗
darksteel 2011-5-7 01:53:33 | 只看该作者
全局:
经典的LIS问题有n^2的dp做法,还有一种优化的nlogn的做法。2L说的方法我也听人说过,觉得是一种挺新颖的思路
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-9 12:25:18 | 只看该作者
全局:
那个把每步为n的化为log(n)的方法大致为:
设每个以i结尾的a[i]最大地=递增子序列长度分别为f(n) (0<= i = n)
用一个数组B记录f(i)->a[i],它是一个bitmap.

难点有两个, 一个是这样记录下来的数组B是递增的,另外一个是B[f(i)]上新覆盖的数不影响后续计算的结果,逻辑很难也很巧妙,证明算法的正确性都不是一会半会能证明的,更不用说别人当初是怎么想到的。感兴趣的可以在网上搜索一下这个nlogn的解法。
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-11 12:31:05 | 只看该作者
全局:
//nlogn solution to get the length of the LIS
int BinarySearchLess(int a[], int n, int nVal)
{
        assert(a && n>0);

        int nBeg = 0;
        int nEnd = n-1;
        int nMinIndex = -1;
        while (nBeg <= nEnd)
        {
                int nMid = (nEnd + nBeg)/2;


                if (a[nMid] <= nVal)
                {
                        nMinIndex = nMid;
                        nBeg = nMid+1;
                }
                else
                        nEnd = nMid - 1;
        }

        return nMinIndex;
}

//Two points make the nlogn solution clear:
// 1. The array pDP is naturally sorted
// 2. Make sure the value of certain index is the smallest one
int GetLISLen(int a[], int n)
{
        assert(a);
        assert(n>0);

        int* pDP = new int[n];
        pDP[0] = a[0];
        int nCurLen = 1;

        for (int i = 1; i < n; i++)
        {
                int nRes = BinarySearchLess(pDP, nCurLen, a);
                if (nRes < -1) nRes = -1;
               
                if (nRes+1 >= nCurLen)
                {
                        nCurLen++;
                        pDP[nRes+1] = a[i];
                }
                else if (a[i] < pDP[nRes+1])
                        pDP[nRes+1] = a[i];
        }

        delete []pDP;

        return nCurLen;
}
[/i][/i][/i]
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表