UVA11527Unique Snowflakes(滑动窗口 + set判重 | | map)

题意:输入长度为n的序列a,找到一个尽量长的连续子序列a[l] - a[r],使该序列中没有相同的元素

紫薯P239

序列元素从0开始编号,l 和 r 分别表示子序列左右端点,初始化为0,固定 l,判断加入 a[r] 是否重复,如不重复,加入,同时r++,若重复,l++,然后再判断加入a[r]是否重复..

时间复杂度:r从0到n,判重由set来处理lgn,总O(nlgn)

 #include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
using namespace std;
int main()
{
int t, n;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
int *a = new int[n]; //动态分配
for (int i = ; i < n; i++)
scanf("%d", &a[i]);
int l, r, maxL;
maxL = l = r = ;
set<int> s;
while (r < n)
{
while (r < n && s.count(a[r]) == ) //判断加入r是否重复
{
s.insert(a[r]);
r++;
}
maxL = max(maxL, r - l);
s.erase(a[l]); // 将l处的移除set
l++;
}
printf("%d\n", maxL);
}
return ;
}

用map来求

last[i] = x表示第i各位置的数上一次出现是在第x位置,故对于 r 位置的数来说,如果他上次出现在 l 位置之前,则 r 是可以扩展的,否则 l++;

记录每个位置上一次出现的位置可以用map来映射。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
using namespace std;
int main()
{
int t, n;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
int *a = new int[n];
int *last = new int[n];
map<int, int> m;
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
if ( m.count(a[i]) == 0 )
{
last[i] = -1; // 如果上次没有出现,设为-1
}
else
{
last[i] = m[ a[i] ]; // 如果上次出现,找到上次出现的位置
}
m[ a[i] ] = i; // 这次出现的位置
}
int l, r, maxL;
l = r = maxL = 0;
while (r < n)
{
while (r < n && last[r] < l) // 一定是last[r] < l时,r才加一
r++;
maxL = max(maxL, r - l);
l++;
}
printf("%d\n", maxL);
delete[] a;
delete[] last;
}
return 0;
}

  

上一篇:linux内核参数调优,缓冲区调整,tcp/udp连接管理,保持,释放优化,gossary,terms


下一篇:机器学习技法课之Aggregation模型