首页 > 代码库 > LeetCode - Longest Consecutive Sequence
LeetCode - Longest Consecutive Sequence
题目描述:
给一个数组,找出其中连续的最长是: 如 -1 1 20 0 3 100 2 最长连续是 -1 0 1 2 3 返回 5
做法:用字典树标记数字是否出现过。起到hash作用。然后在遍历 拓展左右两个端点。讲道理,特地用了字典树就是在查询的时候 能顺手删除元素,防止 1 - 10000 这样的数据 搜寻N^2次,结果。。题目TM数据太弱。评论区 一堆用 map,set直接过的人。。。简直了,还完全无视 0 作为分界点可能出现的bug 。咦!
class Solution {
public:
struct node{
int cnt;
node *next[10];
node(){
memset(next,0,sizeof(next));
cnt = 0;
}
};
struct fuck{
node *fu[2];
fuck(){
memset(fu,0,sizeof(fu));
fu[1] = new node();
fu[0] = new node();
}
};
node* p;
void inst(int fs,fuck *fk){
node *root ;
if(fs<0){
fs*=-1;
root = fk->fu[0];
}else{
root = fk->fu[1];
}
int i,k;
for( i = 0,p = root; fs ; i++){
k = fs%10;
fs/=10;
if(!p->next[k])
p->next[k] = new node();
p = p->next[k];
}
p ->cnt++;
return ;
}
int sear(int fs,fuck *fk){
node *root ;
if(fs<0){
fs*=-1;
root = fk->fu[0];
}else{
root = fk->fu[1];
}
int i,k;
for(i= 0,p = root;fs;i++){
k = fs%10;
fs/=10;
if(!p->next[k])
return 0;
p = p ->next[k];
}
if(p->cnt){
p->cnt--;
return 1;
}
return 0;
}
int longestConsecutive(vector<int>& nums) {
fuck *root = new fuck();
for(int i = 0 ; i < nums.size(); i ++){
inst(nums[i],root);
}
int vmax = 0;
for(int i = 0 ; i < nums.size(); i ++){
if(sear(nums[i],root)){
int ans = 1;
int l = nums[i]-1;
int r = nums[i]+1;
while(1){
if(sear(l,root)){
ans++;
l--;
}else{
break;
}
}
while(1){
if(sear(r,root)){
ans++;
r++;
}else{
break;
}
}
vmax = max(ans,vmax);
}
}
return vmax;
}
};
LeetCode - Longest Consecutive Sequence