所谓贪心，总是做出在当前看来是最好的选择。也就是说，不从整体最优上进行考虑，算法得到的是某种意义的局部最优解
1.两个数对之间的最大乘积差
两个数对 (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]) 之间的 乘积差 取到 最大值 。返回以这种方式取得的乘积差中的 最大值 。
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);
return nums[numsSize - 1] * nums[numsSize - 2] - nums[0] * nums[1];
}
//先将元素进行排序
//用两个最大减去两个最小的
2.三角形的最大周长
给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。如果不能形成任何面积不为零的三角形，返回 0。
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 >= 2; i--){
if(nums[i - 1] + nums[i - 2] > nums[i]){
return nums[i - 1] + nums[i - 2] + nums[i];
}
}
return 0;
}
//先将所有的元素从小到大排序，若最大的一个值小于两个较小的值的和，则能构成三角形，此时为最大的周长
//若不大于，则将三个元素向小的方向移动一个位置，
//若全部走遍后，任然没有，则不能构成三角形
3.数组拆分 I
给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该 最大总和 。
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 sum = 0;
for(int i = 0; i < numsSize - 1; i += 2){
sum += nums[i];
}
return sum;
}
//将这些元素两两配成一对，取每一对中的最小值，让他们的和最大
//先将元素进行排序，要使和最大，就是每一组的最小值都是最大，
//最大的那个取不到，当他和次大的结合是，最小的是次大，
//然后将这两个去掉，再重复上面的操作，
//最后可得，将下标为偶数的加起来的和最大
4.救生艇
第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
int cmp(const void *a, const void *b){
return *(int *)a - *(int *)b;
}
int numRescueBoats(int* people, int peopleSize, int limit){
qsort(people, peopleSize, sizeof(int), cmp);
int l = 0, r = peopleSize - 1, count = 0;
while(l <= r){
if(l == r){
count++;
l++;
}
else if (people[l] + people[r] > limit){
count++;
r--;
}
else {
count++;
r--;
l++;
}
}
return count;
}
//先将人的体重按从小到大排列
//若最大的那个人的体重比最大承重量大，则船的个数加1，将目标向前移动
//若最大的那个人的体重与最小的人的体重之和大于承重量，则船的个数加1，后面的目标向前移动一
//若最大的那个人的体重与最小的人的体重之和小于称重量，船的个数加1，后面的目标向前移动一位，前面的目标向后移动一位
//若只剩下一个人之后，船加一，
//l是体重最小的，r是体重的最大，当体重最小的小于等于最大的时，还有人未上船，当体重最小大于体重最大时，人全部上完。
5.摆动排序 II
给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。你可以假设所有输入数组都可以得到满足题目要求的结果。
int cmp(const void *a, const void *b){
return *(int *)a - *(int *)b;
}
void wiggleSort(int* nums, int numsSize){
int i = 0, r;
qsort(nums, numsSize, sizeof(int), cmp);
int *ret = (int *)malloc(numsSize * sizeof(int));
for(i = 0; i < numsSize; i++){
ret[i] = nums[i];
}
r = numsSize - 1;
for(i = 1; i
6.分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
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 i = gSize - 1, j = sSize - 1, count = 0;
while(i >= 0 && j >= 0){
if(s[j] >= g[i]){
i--;
j--;
count++;
}
else{
i--;
}
}
return count;
}
//每个人最多只有一个饼干，求能被喂饱的最多人数
//先将饼干的尺寸和胃口值进行排序
//将最大的饼干喂给胃口最大的孩子，若能喂饱，则将这块饼干喂给这个孩子
//若喂不饱，则将这块饼干与下一个比较，直到饼干喂完或孩子们都有饼干
7.最少 *** 作使数组递增
给你一个整数数组 nums （下标从 0 开始）。每一次 *** 作中，你可以选择数组中一个元素，并将它增加 1 。比方说，如果 nums = [1,2,3] ，你可以选择增加 nums[1] 得到 nums = [1,3,3] 。请你返回使 nums 严格递增 的 最少 *** 作次数。我们称数组 nums 是 严格递增的 ，当它满足对于所有的 0 <= i < nums.length - 1 都有 nums[i] < nums[i+1] 。一个长度为 1 的数组是严格递增的一种特殊情况。
int minOperations(int* nums, int numsSize){
int i = 0, count = 0, pre = nums[0] + 1;
for(i = 1; i < numsSize; i++){
if(pre < nums[i]){
pre = nums[i] + 1;
}
else{
count += pre - nums[i];
pre++;
}
}
return count;
}
//对数组的每一个元素递增1，使这个数组成为递增数组，求最少的操作次数
//若使一个数比一个目标值大于，每次只能加一，进行的最小操作是目标值-这个数+1
//先令第一个元素加一，如果这个值小于后一个数，则符合条件，不需要操作
//若这个值大于等于后一个数，
// 当等于时,需要变化的次数是0，pre++等于后一个数加1
// 当大于时,需要变化的次数是前面的那个数+1-后面的那个数
//当全部元素都访问过一次后，退出
int minOperations(int* nums, int numsSize){
int i = 0, count = 0;
for( i = 1 ; i < numsSize; i++){
if(nums[i] > nums[i -1]){
;
}
else{
count += nums[i - 1] + 1 - nums[i];
nums[i] = nums[i - 1] + 1;
}
}
return count;
}
//直接比
8.使数组有唯一的最小增量
给你一个整数数组 nums 。每次 move *** 作将会选择任意一个满足 0 <= i < nums.length 的下标 i，并将 nums[i] 递增 1。返回使 nums 中的每个值都变成唯一的所需要的最少操作次数。
int cmp(const void *a, const void *b){
return *(int *)a - *(int *)b;
}
int minIncrementForUnique(int* nums, int numsSize){
qsort(nums, numsSize, sizeof(int), cmp);
int count = 0;
for(int i = 0; i < numsSize - 1; i++){
if(nums[i] >= nums[i + 1]){
count += nums[i] + 1 - nums[i + 1];
nums[i + 1] = nums[i] + 1;
}
}
return count;
}
//向将数组进行排序
//然后比较相邻元素的大小，若左边的大于等于右边的，则右边的值为左边的值加1
//可能存在连续的几个相同的数，当第二个相同数的增加后，第二就大于第三个
9.有效三角形的个数
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
int cmp(const void *a, const void *b){
return *(int *)a - *(int *)b;
}
int triangleNumber(int* nums, int numsSize){
qsort(nums, numsSize, sizeof(int), cmp);
int i, j, k, count = 0;
for(i = 0; i < numsSize; i++){
j = i + 1;
k = j + 1;
while(j < numsSize){
while(k < numsSize){
if(nums[i] + nums[j] <= nums[k]){
break;
}
else{
k++;
}
}
count += k - j - 1;
j++;
if(k == j){
k++;
}
}
}
return count;
}
//求有效三角形的个数，若两个小的边之和小于第三条边，则不是三角形
//先将所有的元素进行排序
//设置三个变量，i,j,k;一个变量指向一条边
//先让k移动，再让j移动，最后让i移动
//开始时，将i设置为第一个元素，j设置为第二个元素，k设置为第三个元素
//当三条边满足三角形的条件时，k向后移动一位，在进行比较，k移动的次数就是前两个不动时能满足的三角形的个数（k-j-1）初始时k比j大1
//当k移动到不满足条件时，此时移动j，若满足条件，则继续移动k，若不满足条件，移动j，计算出移动的次数（k-j-1）
//当k和j相等时；k加一，三组元素不能相同，此时相当于又回到了初始位置，
//当k和j到达末尾不符合条件时，开始移动i，重复上次操作
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）