东莞网站建设 烤活鱼,h5效果展示网站,网站建设cms,建设官方网站企业官网目录
贪心算法
1. 两数对之间的最大乘积差 2.三角形的最大周长
3.数组拆分
4.救生艇 5.发送饼干
6.摆动数组 贪心算法
概念定义 所谓贪心#xff0c;总是做出在当前看来是最好的选择。也就是说#xff0c;不从整体最优上进行考虑#xff0c;算法得到的是在某种…目录
贪心算法
1. 两数对之间的最大乘积差 2.三角形的最大周长
3.数组拆分
4.救生艇 5.发送饼干
6.摆动数组 贪心算法
概念定义 所谓贪心总是做出在当前看来是最好的选择。也就是说不从整体最优上进行考虑算法得到的是在某种意义上的局部最优解。 比如对于一个全是正整数的数组我要找到其中两个数使得它们的乘积最大毫无疑问一定是取最大和次大的两个数进行相乘得到的结果最大。这个就是贪心思想。 那么接下来让我们做几道例题来真正了解一下贪心。
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 nnumsSize;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 inumsSize-1;i1;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 ans0;for(int i0;inumsSize;ii2){//数对左边的是较小的minansansnums[i];}return ans;
} 证明过程如下 . - 力扣LeetCode
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 ans0;int light0,heavypeopleSize-1;for(;lightheavy;){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 ans0,i0,j0;while(igSizejsSize){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);
} 这题相当复杂原理就是把前一半数重大到小插入偶数位后一半的数重大到小插入奇数位然后可以实现中间的数大于左右两边的数。具体为什么我也不晓得证明过程太复杂不想看
