☘前言☘
今天是九日集训第六天，我会记录一下学习内容和题解，争当课代表0.0.
链接：《LeetCode零基础指南》(第七讲) 贪心
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
⏳全文大约阅读时间： 20min
全文目录
☘前言☘
🎁主要知识点梳理
📝1.贪心算法
🍗课后习题
1913. 两个数对之间的最大乘积差
976. 三角形的最大周长
561. 数组拆分 I
881. 救生艇
324. 摆动排序 II
455. 分发饼干
1827. 最少操作使数组递增
945. 使数组唯一的最小增量
945. 使数组唯一的最小增量
611. 有效三角形的个数
🎁主要知识点梳理
📝1.贪心算法
所谓贪心就是总是做出**当前状态看来最好的选择。**也就是不从整体上最优考虑，只从局部最优解来考虑，最终达到全局最优。
比如：对于一个全是正整数的数组，我要找到其中两个数，使得他们的乘积最大，毫无疑问，一定是取最大和次大的两个数据相乘，得到结果最大。
🍗课后习题
1913. 两个数对之间的最大乘积差
1913. 两个数对之间的最大乘积差
题目描述
两个数对 (a, b) 和 (c, d) 之间的 乘积差 定义为 (a * b) - (c * d) 。
例如，(5, 6) 和 (2, 7) 之间的乘积差是 (5 * 6) - (2 * 7) = 16 。
给你一个整数数组 nums ，选出四个 不同的 下标 w、x、y 和 z ，使数对 (nums[w], nums[x]) 和 (nums[y], nums[z]) 之间的 乘积差 取到 最大值 。
返回以这种方式取得的乘积差中的 最大值 。
思路
其实就是例子中的方法，但是也不需要去排序，找最大和次大值我给一个通用的方式，减少复杂度0.0
int maxProductDifference(int* nums, int numsSize){ int max1 = 1, max2 = 1, min1 = 1e4, min2 = 1e4; for(int i = 0;i < numsSize;i++){ if(nums[i] > max1){max2 = max1; max1 = nums[i];} else if(nums[i] > max2) max2 = nums[i];//防止一开始就是最大值 if(nums[i] < min1){min2 = min1; min1 = nums[i];} else if(nums[i] < min2) min2 = nums[i];//防止一开始就是最小值 } return max1 * max2 - min1 * min2; }
976. 三角形的最大周长
976. 三角形的最大周长
题目描述
给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。
如果不能形成任何面积不为零的三角形，返回 0。
思路
先排序，然后从后往前找第一个满足条件的解就好了
int cmp(int *a,int *b){return *a > *b;} int largestPerimeter(int* nums, int numsSize){ qsort(nums,numsSize,sizeof(int),cmp); int i; for(i = numsSize - 1;i > 1;i--){ if(nums[i] < nums[i-1] + nums[i - 2]) break; } if(i == 1) return 0; else return nums[i] + nums[i - 1] + nums[i-2]; }
561. 数组拆分 I
561. 数组拆分 I
题目描述
给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该 最大总和 。
思路
先排序，然后就是两两组合 其实就是输出偶数下标的数组元素和。
int cmp(int *a, int *b){return *a > *b ? 1 : -1;} int arrayPairSum(int* nums, int numsSize){ int ans = 0; qsort(nums, numsSize, sizeof(int), cmp); for(int i = 0;i < numsSize; i+=2) ans += nums[i]; return ans; }
881. 救生艇
881. 救生艇
题目描述
给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该 最大总和 。
思路
看昨天的题解：【解题报告】《LeetCode零基础指南》(第六讲) C排序API
