• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

尺取法/双指针法

开发技术 开发技术 8小时前 3次浏览

//瞎写的

尺取法:通过保存一组下标,根据条件交替挪动以求最终解。

一般用于求取有一定限制的区间个数或最短的区间,有时能把一些枚举问题从O(nlogn)(二分)优化到O(n)。

例题:

Subsequence POJ3061

题意:给定长度为n的都是正整数的数列以及整数S。求出总和不小于S的连续子序列的长度的最小值,不存在则输出0。

思路:先记录下标b1=1,找到最小的下标b2使得b1->b2的子序列总和不小于S(不存在则输出0)并记录长度。然后将b1增加一,重复前一个过程寻找新的最小b2并计算长度,与原长度比较记录最小值。

分析,在重复过程中我们不难发现,(b1+1)->b2序列的总和必定小于S,故我们没有必要重新枚举(b1+2)->b2的点,可以保证新的下标b2大于原先的b2。

思路代码表现:

void solve()
{
    int l=1,r=n,ans=n+1,sum=0;
    while(1)
    {
        while(r<=n&&sum<S)sum+=a[r++];
        if(sum<S)break;
        ans=min(ans,r-l);//r在递归时会到最小情况+1的位置
        sum-=a[l++];
    }
    if(ans>n)ans=0;
    cout<<ans<<endl;
}

Jessica’s Reading Problem POJ3320

题意:给定长度为n的数列,数列值可能有重复。求出现过所有元素值的子序列的最小长度。

思路:其实相同,只是判断的条件变成了所有元素是否都出现过。

思路代码表现:

void solve()
{
    int l=1,r=n,cnt=0,ans=n+1;
    map<int,int>mp;
    while(1)
    {
        while(r<=n&&sum<n)
        {
            if(!mp[a[r++]])
            {
                mp[a[r++]]++;
                cnt++;
            }
        }
        if(cnt<n)break;
        ans=min(ans,r-l);
        if(mp[a[l++]]==1)
        {
            mp[a[l++]]--;
            cnt--;
        }
    }
    cout<<ans<<endl;
}

//水了一篇


程序员灯塔
转载请注明原文链接:尺取法/双指针法
喜欢 (0)