1913. 两个数对之间的最大乘积差 - 力扣（LeetCode） (leetcode-cn.com)
使用qsort函数进行排序，取出最大数和次大数，最小数和次小数 相乘进行比较。
intcmp(constvoid* a,constvoid* b) { return *(int*)a- *(int*)b; } intmaxProductDifference(int* nums, intnumsSize){ qsort(nums,numsSize,sizeof(int),cmp); returnnums[numsSize-1] * nums[numsSize-2] - nums[0] * nums[1]; }
976. 三角形的最大周长 - 力扣（LeetCode） (leetcode-cn.com)
976. 三角形的最大周长 - 力扣（LeetCode） (leetcode-cn.com)
三角形的三边需要满足两边之和大于第三条边，由这一特性可得：
我们可以先将数组进行排序，然后逆序依次枚举出最大的那一条边c，如果比c小的最大边和次大边能够满足的话，则为最优解，反正则继续枚举至倒数第三条边为止结束。
intcmp(constvoid *a, constvoid *b) { return *(int *)a- *(int *)b; } intlargestPerimeter(int* nums, intnumsSize){ inti; qsort(nums, numsSize, sizeof(int), cmp); for(i = numsSize-1; i >= 2; --i) { if(nums[i-2] + nums[i-1] > nums[i]) { returnnums[i-2] + nums[i-1] + nums[i]; } } return0; }
561. 数组拆分 I - 力扣（LeetCode） (leetcode-cn.com)
561. 数组拆分 I - 力扣（LeetCode） (leetcode-cn.com)
利用贪心算法，我们先对数组进行排序，可以得到
a1 <= a2 <= a3 <= .... <= an
由于a1是最小的，那么所有与a1搭档的数都将会被剔除，如果要满足题意，达到所有组的和最大的结果的话，我们需要让a1帮我剔除一个较小的数 ——> 即a2,以此类推 
intcmp(constvoid *a, constvoid *b) { return *(int *)a- *(int *)b; } intarrayPairSum(int* nums, intnumsSize){ inti,ans = 0; qsort(nums,numsSize,sizeof(int),cmp); for(i = 0;i < numsSize;i += 2) ans += nums[i]; returnans; }
881. 救生艇 - 力扣（LeetCode） (leetcode-cn.com)
intcmp(constvoid *a, constvoid *b) { return *(int *)a- *(int *)b; } intnumRescueBoats(int* people, intpeopleSize, intlimit){ inti; intl = 0, r = peopleSize-1; intans = 0; qsort(people, peopleSize, sizeof(int), cmp); // (1) while(l <= r) { if(l == r) { ++ans; break; // (2) } elseif(people[l] + people[r] > limit) { // (3) ++ans, r--; } else // (4) ++ans, ++l, --r; } returnans; }
- 按照重量从小到大排序
- 如果只剩一个人，那么直接加上一条船，并且跳出循环
- 如果最重的那个人和最轻的那个人加起来不能坐一条船，那么最重的那个人就只能自己乘坐一条船了，其他人不可能和他一起。转变成了n - 1 的子问题
- 如果最重的那个人能和最轻的人一起坐一条船，那就顺带捎上，转变成 n - 2 的子问题
324. 摆动排序 II - 力扣（LeetCode） (leetcode-cn.com)
先将数组进行排序，然后不断进行插孔操作，先插奇数位，再插偶数位。
intcmp(constvoid *a, constvoid *b) { return *(int *)a- *(int *)b; } voidwiggleSort(int* nums, intnumsSize){ inti; intl , r; int* ret = (int*)malloc(sizeof(int) * numsSize); for(i = 0;i < numsSize;i++) ret[i] = nums[i]; qsort(ret,numsSize,sizeof(int),cmp); r = numsSize-1; for(i = 1;i < numsSize;i += 2) nums[i] = ret[r--]; for(i = 0;i < numsSize;i += 2) nums[i] = ret[r--]; }
455. 分发饼干 - 力扣（LeetCode） (leetcode-cn.com)
intcmp(constvoid *a, constvoid *b) { return *(int *)a- *(int *)b; } intfindContentChildren(int* g, intgSize, int* s, intsSize){ qsort(g,gSize,sizeof(int),cmp); qsort(s,sSize,sizeof(int),cmp); inti = 0; intj = 0; while(i < gSize && j < sSize) { if(s[j] >= g[i]) { i++; } j++; } returni; }
贪心的思想是，用尽量小的饼干去满足小需求的孩子，所以需要进行排序先
饼干只能用一次，如果饼干没有比当前孩子需要的大的话，则跳过；
如果饼干大于等于当前孩子所需要的，则孩子标记++；
1827. 最少操作使数组递增 - 力扣（LeetCode） (leetcode-cn.com)
intminOperations(int* nums, intnumsSize){ inti; intans = 0,pre = nums[0] + 1; for(i = 1;i < numsSize;++i) { if(pre < nums[i]) pre = nums[i] + 1; else { ans += pre-nums[i]; ++pre; } } returnans; }
945. 使数组唯一的最小增量 - 力扣（LeetCode） (leetcode-cn.com)
classSolution{ public: intminIncrementForUnique(vector<int>& nums){ intres=0; sort(nums.begin(),nums.end()); for(inti=1;i<nums.size();i++){ if(nums[i-1]>=nums[i]){ res+=(nums[i-1]+1-nums[i]); nums[i]=nums[i-1]+1; } } returnres; } };
贪心算法在于每个子问题的局部最优解会指向全局最优解。
显然在对数组排序之后，可以通过保证数组的最后一个元素，经过+1操作后比前面所有元素大即可,此时子问题的最优解会收敛于全局最优解
有效三角形的个数 - 有效三角形的个数 - 力扣（LeetCode） (leetcode-cn.com)
intcmp(constvoid *a, constvoid *b) { return *(int *)a- *(int *)b; } inttriangleNumber(int* nums, intnumsSize){ inti, j, k; intans = 0; qsort(nums, numsSize, sizeof(int), cmp); // (1) for(i = 0; i < numsSize; ++i) { j = i + 1; k = j + 1; // (2) while(j < numsSize) { while(k < numsSize) { if(nums[i] + nums[j] <= nums[k]) { break; // (3) } ++k; } ans += k-j-1; // (4) ++j; // (5) if(k == j) k++; } } returnans; }
