九日集训day5【刷题】【九日集训】

前言

今天是第5天，后面两题有点难搞，耽误了点时间，英雄哥解法真是妙啊。

912. 排序数组

int cmp(const void* e1, const void* e2){    return *(int*)e1 - *(int*)e2;}int* sortArray(int* nums, int numsSize, int* returnSize){    qsort(nums, numsSize, sizeof(int), cmp);    *returnSize = numsSize;    return nums;}

169. 多数元素

排序一下，多数元素一定在中间位置。

int CmpByInt(const void* e1, const void* e2){    return *(int*)e1 - *(int*)e2;}//排序,返回中间的数int majorityElement(int* nums, int numsSize){    qsort(nums,numsSize,sizeof(nums[0]),CmpByInt);    int left = 0;    int right = numsSize-1;    int mid = (right-left)/2 + left;    return nums[mid];}

217. 存在重复元素

如果存在，排序完毕之后，必然相邻

int CmpByInt(const void* e1, const void* e2){    return *(int*)e1 - *(int*)e2;}bool containsDuplicate(int* nums, int numsSize){    qsort(nums,numsSize,sizeof(nums[0]),CmpByInt);    //注意要比较前一个，避免越界    for(int i = 1; i < numsSize; i++)    { if(nums[i] == nums[i-1])     return true;    }    return false;}

164. 最大间距

int CmpByInt(const void* e1, const void* e2){    return *(int*)e1 - *(int*)e2;}int maximumGap(int* nums, int numsSize){    if(sizeof(nums)/sizeof(nums[0]) < 2) return 0;    qsort(nums, numsSize, sizeof(int), CmpByInt);    int max = 0;    //i从1开始，避免越界    for(int i = 1; i < numsSize; i++)    { if(nums[i]-nums[i-1] > max)     max = nums[i]-nums[i-1];    }    return max;}

905. 按奇偶排序数组

int CmpByEven(const void* e1, const void* e2){    return (*(int*)e1)%2 - (*(int*)e2)%2;}int* sortArrayByParity(int* nums, int numsSize, int* returnSize){    qsort(nums, numsSize, sizeof(int), CmpByEven);    *returnSize = numsSize;    return nums;}

539. 最小时间差

int cmp(const void *a, const void *b) {    return *(int *)a - *(int *)b;}int min(int a, int b) {    return a < b ? a : b;}int findMinDifference(char ** timePoints, int timePointsSize){    int* ret = (int*)malloc( sizeof(int)*timePointsSize);    int i, ans = 1440;    int a, b;    //sscanf 从一个字符串中提取(转化)出格式化的数据    for(i = 0; i < timePointsSize; i++)    { sscanf(timePoints[i], "%d:%d", &a, &b);ret[i] = a*60 + b;//转换成分钟    }    qsort(ret, timePointsSize, sizeof(int), cmp);    //再找出最小值    for(i = 1; i < timePointsSize; i++)     { ans = min(ans, ret[i] - ret[i-1]);    }    //考虑首尾时间差    ans = min(ans, ret[0]-ret[timePointsSize-1] + 1440);    return ans;}

976. 三角形的最大周长

利用两边之和大于第三边的性质即可

从最大的三个数开始判断，如果满足，那必然是最大的周长了。

int cmp(const void *a, const void *b){    return *(int *)a - *(int *)b;}int largestPerimeter(int *nums, int numsSize){    int i;    qsort(nums, numsSize, sizeof(int), cmp);    for (i = numsSize - 1; i >= 2; --i)    { if (nums[i - 2] + nums[i - 1] > nums[i])     return nums[i - 2] + nums[i - 1] + nums[i];    }    return 0;}

881. 救生艇

考虑最重的那个人能不能和最轻的人一起坐船，如果不能表示最重的人只能单独坐船。

只剩一个人，直接一个人坐船即可

int cmp(const void *a, const void *b){    return *(int *)a - *(int *)b;}int numRescueBoats(int* people, int peopleSize, int limit){    int left = 0, right = peopleSize-1;    int count = 0;    //先排序    qsort(people, peopleSize, sizeof(people[0]), cmp);    while(left <= right)    { if(left == right) {     count++;//单独坐船     break;//没人时要结束循环 } else if(people[left] + people[right] > limit)     count++, right--; else     count++, right--, left++;    }    return count;}