大学生每天刷leetcode要坚持下去是怎么回事呢?大学生相信大家都很熟悉,但是大学生每天刷leetcode要坚持下去是怎么回事呢,下面就让小编带大家一起了解吧。大学生每天刷leetcode要坚持下去,其实就是刷力扣对提高思维能力很有帮助,大家可能会很惊讶大学生怎么会每天刷leetcode要坚持下去呢?但事实就是这样,小编也感到非常惊讶。
今天小编会带来一条什么题目呢??现在就给大家揭晓题目如下~~
先审题~~
发现这个题目其实很好理解~~题如其名,就是要在乱序的数组里找到最长连续子序列~~~
这题虽然被标注为HARD,但是小编完全不再怕的~~ hard的原因是题目中要求复杂度必须要在O(n)以内,小编现在和大家一起扩展思路~
假如没有复杂度的限制,而仅仅如题目中所说只要找出最长连续子序列,该怎么做呢???
思路一:
暴力解法:对每个数都寻找他接下来的连续的数,然后再一起比较谁最长,这样子的复杂度是O(n^3),显然是太复杂了~~~
思路二:
排序法:先将数组排序再进行子序列长度的度量,选择最长的。酱紫排序的复杂度为O(lgn),总体的复杂度就是O(nlgn),看起来还好~~但是还有很多提升空间,一定要加油哦!!排序法的C代码如下:
#include
int compare(const void* a, const void* b)
{
return *((unsigned int*)a) - *((unsigned int*)b);
}
//以上这个compare函数主要是为了C语言里面的qsort函数啦~~具体想了解这个qsort函数的函数的话呢,小编这里建议百度啦~~~这里面的a,b都采用了(unsigned int*)主要是为了表达位数比int更加多~~~
int longestConsecutive(int* num, int numSize)
{
while(numSize != 0 ){
//这是要判断数组是不是[ ]也就是里面什么都没有~~,区别于[0]哦!
qsort(num, numSize, sizeof(int), compare);
//这个函数就是C语言里面的 qsort啦!
int max = 0, temp = 1;
for(int i = 1; i
{
if(num[i] == num[i-1]) continue;//一样的值就不管他,跳出本次for循环但是temp的值依然记录着~~
if(num[i] == num[i-1]+1)
temp++;
else
{
max = (max> temp)?max:temp;
temp = 1;//一旦途中的连续值断了,这里必须要重置temp的值哦!!!!
}
}
return (max> temp)?max:temp;//最终输出~~
}
return 0;//数组是[ ]的话,输出是0哦~~~
}
好了,以上就是排序法的所有代码了!!小编也非常开心,因为排序法非常好理解,但是复杂度还不够要求,接下来小编就带来本题的最终解法!!
思路三:
哈希表~~哈希表和线性空间的构造(其实可以被看作是思路一暴力法的优化啦!!)
HashMap中的key表示读到的数组中每个元素的值,value对应的是数组中每个key所处的连续序列的长度!
遍历数组nums[i]的时候将数组中每一个元素插入到HashMap去,可能出现以下几种情况:
(1)插入HashMap中该元素已经被插入过,则不插入。
(2)插入HashMap中该元素没有被插入过且该元素没有相邻的元素,则令key=nums[i],value=1,插入到HashMap中去即可。
(3)插入HashMap中某元素key=3时,有比它大的相邻的元素,则一直遍历找到与它相邻序列中最大的那个元素,然后将连续序列的首尾key对应的value更新为连续序列的长度。
key 3 4 5
value 3 2 3
(4)插入HashMap中某元素key=7时,有比它小的且相邻的元素,则一直遍历HashMap找到与它相邻序列中最小的那个元素,然后将连续序列首尾的Key对应的value更新为最新的连续序列的长度个数。
key 5 6 7
value 3 2 3
(5)插入HashMap中某元素key=5时,有比它大的相邻的元素,也有比它小的相邻的元素的时候,我们先遍历HashMap找到与它相邻且比它大的序列中最大的那个元素,然后将连续序列的首尾key对应的value更新为最新的连续序列的长度;然后遍历HashMap找到与它相邻且比它小的序列中最小的那个元素,然后将最长的连续序列的首尾的Key对应的value更新为序列的长度。
key 3 4 5 6 7
value 5 2 3 2 5
以上就是哈希表的构造方法了!是不是很神奇呢!!!小编也很惊讶于程序员的智慧!!!
接下来就是代码实现了~~~~~~
struct mystruct{
int number;
UT_hash_handle hh;
};
struct mystruct *t;
struct mystruct *find(int number) {
struct mystruct *s;
HASH_FIND_INT(t, &number, s);
return s;
}//定义了结构体相关,小编这里不想展开写了,有问题评论区见吧~~~
void add(int num){
struct mystruct *s = (struct mystruct *)malloc(sizeof(struct mystruct));
if(find(num) == NULL){//没被插入的key就存入~
s->number = num;
HASH_ADD_INT(t, number, s);
}
}
int longestConsecutive(int* nums, int numSize){
t = NULL;
int max = 0;
if(numSize == 0)
return numSize;
for(int i = 0; i < numSize; i++){
add(nums[i]);
}
for(int i = 0; i < numSize; i++){
if(find(nums[i] + 1) == NULL){
int tmp, n;//tmp用来保存比该元素大的且连续的最大的那个元素
n = nums[i];
tmp = n;
while(find(n)){
n -= 1;
}
max = ((tmp - n) > max) ? (tmp - n) : max;
}
}
return max;
}
好了~~小编写到这里就已经很困啦~~
先晚安啦~~~
领取专属 10元无门槛券
私享最新 技术干货