数据结构 day 1

LeetCode数据结构day1算法题学习

题217. 存在重复元素

1）思路：

2）代码：

int compFunc(void* p,void* q){
    int* node_1 = (int*)p;
    int* node_2 = (int*)q;

    return (*node_1-*node_2);
}

bool containsDuplicate(int* nums, int numsSize){
    int flag,i;
    qsort(nums, numsSize, sizeof(int), compFunc);//快排算法对输入数组排序
    flag = nums[0];
    for (i = 1; i < numsSize; i++)
    {
        if (flag == nums[i])
        {
            return  true;
        }
        flag = nums[i];
    }

    return false;
}

还可以优化一下：

bool containsDuplicate(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), compFunc);
    for (int i = 0; i < numsSize-1; i++)
    {
        if (nums[i] == nums[i+1]){
            return  true;
        }
    }
    
    return false;
}

题53. 最大子数组和

1）思路：

2）代码：

int maxSubArray(int* nums, int numsSize){
    int pre = 0, maxAns = nums[0];//初始前驱设为0
    for (int i = 0; i < numsSize; i++) {
        pre = fmax(pre + nums[i], nums[i]);//取max（pre+nums[i],nums[i]），并赋值给pre
        maxAns = fmax(maxAns, pre);
    }
    return maxAns;
}
//上述代码摘自官方