题目链接
题目大意:
给n个数, n<=100W,求一个连续子序列,这个子序列中没有重复的数,问这个子序列最长是多少?
思路:
开一个数组pos, pos[ x ] 表示x出现的位置, 这个数组初始化为-1
用一个变量start来记录当前枚举序列的起点,初始为0
然后枚举这个序列,依次记录每个数的位置,
假设当前枚举到i, 在记录这个位置之前,先检查当前这个数的位置pos【 arr【i】 】是否大于等于start,如果大于,说明这个数已经在[start, i-1]中已经出现过了,记下这个满足条件的子序列长度。然后枚举下一个子序列: start = pos[i] + 1. 这个算法总复杂度为O(n)
代码:
/*
* UVa 11572 Unique Snowflakes
*
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long int64;
const int INF = 0x3f3f3f3f;
const int MAXN = 1000010;
int arr[MAXN];
int pos[MAXN];
int main(){
int nCase, m, n;
scanf("%d", &nCase);
while(nCase--){
scanf("%d", &n);
int cnt=0;
for(int i=0; i<n; ++i)
scanf("%d", &arr[i]);
memset(pos, -1, sizeof(pos));
int start = 0;
int maxx = 0;
arr[n] = arr[n-1];
for(int i=0; i<=n; ++i){
if(pos[arr[i]] >= start){
int tmp = i - start;
maxx = max(tmp, maxx);
start = pos[arr[i]]+1;
pos[arr[i]] = i;
}else{
pos[arr[i]] = i;
}
}
printf("%d\n", maxx);
}
return 0;
}
分享到:
相关推荐
JavaScript-雪花该作业基于。 要开始此作业,您应该观看视频。... 该启动器基于弗洛林的代码,但并不完全相同。 您应该花一些时间研究代码,以确保您理解它。 该作业的页面顶部有一些输入,但是现在它们什么也没做。...
北大POJ3349-Snowflake Snow Snowflakes 解题报告+AC代码
1hgj-82-snowflakes:我输入的1hgj#82。 主题:冬季
圣诞雪花-JS Xmas Snow Fall JavaScript Effect - 不需要图像 - Weslley A. Harakawa 只需复制并粘贴到 BODY 中正上方 / BODY 文档化的代码包含在 xmas snowfall_effect.js 文件中。 现场演示: :
),只需在您的项目中包含snowflakes.js和snowflakes.css即可。 然后使用标记内容的整体容器的以及雪花将从其中落下的修改下面的代码: snowflakes.create(someNumber);并将其添加到您的页面以生成雪花。
语言:English 在任何页面上添加雪花效果,营造新年气氛! 在浏览网络时想要生活中的新年气氛吗? 通过此扩展程序,您可以在打开的所有页面上添加飞舞的雪花。 扩展程序弹出窗口中有一个可以启用或禁用扩展程序的开关...
poj 3349 Snowflake Snow Snowflakes.md
npm i magic-snowflakes --save-dev 没有设定 < html > < body > ... < script src =" https://unpkg.com/magic-snowflakes/dist/snowflakes.min.js " > </ script > < script > ...
用法安装模块: npm install --save react-native-snow-bg或者 yarn add react-native-snow-bg将其添加到您应用中的任何视图: import Snow from 'react-native-snowflakes' ;export default function App ( ) { ...
安装“雪花新标签”,并获取冬季雪花的...Snowflakes New Tab Theme是通往美好旅程的门户,您可以根据自己的喜好个性化所有内容,与您的网络共享并通过组织和跟踪待办事项列表来掌握最重要的事情。 支持语言:English
雪花 在您的网页上放置雪的脚本
《Spark快速数据处理》这本书讲解了spark的基本内容及项目实践
在每个新标签页上都包含雪花的高清图像。 对于冬季雪迷来说,圣诞节圣诞老人鲁道夫等等! 在每个新标签页上都包含雪花的高清图像。 对于冬天的雪迷,圣诞节,圣诞老人,鲁道夫等等! 我们始终会更新图像,因此请随时...
雪花雪花算法1.SnowFlake算法,是Twitter开源的分布式id生成算法。其核心思想就是:使用一个64位的长型的数字作为唯一的id。最佳,是保持逐步的。 2.组成:(1)第一个部分,是1个位:0,这个是无意义的。...
添加一个指向snowflakes.js 的脚本标签,然后在你的domready 函数中调用window.snowflakes(); 您还可以传递一个选项对象,您可以在其中配置这个东西的行为。 以下选项可用: amount // int, defaults to 250 ...
雪花 我的 Ludum Dare 31 游戏。
雪花 可以生成名称或词组并将其转换为雪花的雪花生成器。 使用HTML5 canvas和Javascript。 作者 乔·格兰杰