【解题报告】《LeetCode零基础指南》(第七讲) 贪心（1）

2022-04-16 123

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【解题报告】《LeetCode零基础指南》(第七讲) 贪心（1）

☘前言☘

今天是九日集训第六天，我会记录一下学习内容和题解，争当课代表0.0.

链接：《LeetCode零基础指南》(第七讲) 贪心

🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人

✨联系方式：2201891280(QQ)

⏳全文大约阅读时间： 20min

全文目录

☘前言☘

🎁主要知识点梳理

📝1.贪心算法

🍗课后习题

1913. 两个数对之间的最大乘积差

976. 三角形的最大周长

561. 数组拆分 I

881. 救生艇

324. 摆动排序 II

455. 分发饼干

1827. 最少操作使数组递增

945. 使数组唯一的最小增量

611. 有效三角形的个数

🎁主要知识点梳理

📝1.贪心算法

所谓贪心就是总是做出**当前状态看来最好的选择。**也就是不从整体上最优考虑，只从局部最优解来考虑，最终达到全局最优。

比如：对于一个全是正整数的数组，我要找到其中两个数，使得他们的乘积最大，毫无疑问，一定是取最大和次大的两个数据相乘，得到结果最大。

🍗课后习题

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. 三角形的最大周长

题目描述

给定由一些正数（代表长度）组成的数组 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

题目描述

给定长度为 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;
}