目录
贪心算法
概念定义
所谓贪心，总是做出在当前看来是最好的选择。也就是说，不从整体最优上进行考虑，算法得到的是在某种意义上的局部最优解。
比如，对于一个全是正整数的数组，我要找到其中两个数，使得它们的乘积最大，毫无疑问，一定是取最大和次大的两个数进行相乘，得到的结果最大。这个就是贪心思想。
那么接下来，让我们做几道例题，来真正了解一下贪心。
1. 两数对之间的最大乘积差
int cmp(const void *a,const void *b){
return *(int*)a-*(int*)b;
}
int maxProductDifference(int* nums, int numsSize){
qsort(nums,numsSize,sizeof(int),cmp);//排序
int n=numsSize;
return abs(nums[n-1]*nums[n-2]-nums[0]*nums[1]);//贪心，直接取最前最后两个乘积差
}
/*
//直接找最大的两个数ab和最小的两数cd
int maxProductDifference(int* nums, int numsSize) {
int a = 0, b = 0, c = 10001, d = 10001, i, t;
for (i = 0; i < numsSize; i++) {
t = nums[i];
if (t > a)
b = a, a = t;
else if (t > b)
b = t;
if (t < d)
c = d, d = t;
else if (t < c)
c = t;
}
return a * b - c * d;
}
*/2.三角形的最大周长
//遇到数组题目的第一件事就是先排序！！！
int cmp(const void *a,const void *b){
return *(int*)a-*(int*)b;
}
//有些时候不要想太复杂了
int largestPerimeter(int* nums, int numsSize) {
qsort(nums,numsSize,sizeof(int),cmp);
//贪心找出边长最大的三个边
for(int i=numsSize-1;i>1;i--){
if(nums[i]<nums[i-1]+nums[i-2]){
return nums[i]+nums[i-1]+nums[i-2];
}
}
return 0;
}3.数组拆分
//想想思路，在数对中取min后之和要最大，
//是不是感觉直接排序后取欸者的两个为一对就可以了
//直接试试（贪心）
//为什么证明过程相当复杂，
int cmp(const void*a,const void*b){
return *(int*)a-*(int*)b;
}
int arrayPairSum(int* nums, int numsSize) {
qsort(nums,numsSize,sizeof(int),cmp);
int ans=0;
for(int i=0;i<numsSize;i=i+2){//数对左边的是较小的min
ans=ans+nums[i];
}
return ans;
}4.救生艇
int cmp(const void *a,const void *b){
return *(int*)a-*(int*)b;
}
//贪心算法，两个人一条船，船少，
/*
方法一：贪心
要使需要的船数尽可能地少，应当使载两人的船尽可能地多。
设 people\textit{people}people 的长度为 nnn。考虑体重最轻的人：
若他不能与体重最重的人同乘一艘船，那么体重最重的人无法与任何人同乘一艘船，
此时应单独分配一艘船给体重最重的人。从 people 中去掉体重最重的人后，
我们缩小了问题的规模，变成求解剩余 n−1个人所需的最小船数，将其加一即为原问题的答案。
若他能与体重最重的人同乘一艘船，那么他能与其余任何人同乘一艘船，
为了尽可能地利用船的承载重量，选择与体重最重的人同乘一艘船是最优的。
从people 中去掉体重最轻和体重最重的人后，
我们缩小了问题的规模，变成求解剩余 n−2个人所需的最小船数，将其加一即为原问题的答案。
*/
int numRescueBoats(int* people, int peopleSize, int limit) {
qsort(people,peopleSize,sizeof(int),cmp);
int ans=0;
int light=0,heavy=peopleSize-1;
for(;light<=heavy;){
if(people[heavy]+people[light]<=limit){//可以坐下最重的一个人+一个人
ans++;
light++;
heavy--;
}else{//坐不下
ans++;
heavy--;
}//我看谁能和现在最轻的人一起
}
return ans;
}5.发送饼干
//不管不管，拿到数组先排序
int cmp(const void*a,const void *b){
return *(int *)a-*(int*)b;
}
int findContentChildren(int* g, int gSize, int* s, int sSize) {
qsort(g,gSize,sizeof(int),cmp);
qsort(s,sSize,sizeof(int),cmp);
int ans=0,i=0,j=0;
while(i<gSize&&j<sSize){
if(g[i]<=s[j]){
ans++;
i++;
j++;
}else{
j++;
}
}
return ans;
}6.摆动数组
// 1 2 3 4 5 6 7 8
//4 3 2 1
// 8 7 6 5
static int cmp(const void *pa, const void *pb) {
return *(int *)pa - *(int *)pb;
}
void wiggleSort(int* nums, int numsSize) {
int * arr = (int *)malloc(sizeof(int) * numsSize);
memcpy(arr, nums, sizeof(int) * numsSize);
qsort(arr, numsSize, sizeof(int), cmp);
int x = (numsSize + 1) / 2;
for (int i = 0, j = x - 1, k = numsSize - 1; i < numsSize; i += 2, j--, k--) {
nums[i] = arr[j];
if (i + 1 < numsSize) {
nums[i + 1] = arr[k];
}
}
free(arr);
}
这题相当复杂，原理就是把前一半数重大到小插入偶数位，后一半的数重大到小插入奇数位，然后可以实现中间的数大于左右两边的数。具体为什么我也不晓得，证明过程太复杂不想看
