理论基础
贪心算法是一种常见的解决优化问题的方法,其基本思想就是在问题的每个决策阶段,都选择当前看起来最优的选择,即贪心地做出局部的最优决策,以此得到全局的最优解,例如在十张面额不同的钞票,让我们去取5张,那如何拿到最多的钱呢?那我们每次取钞票时只需要取出面额最大的一张(局部最优),最后拿到的就是最多的钱(全局最优),这就是贪心的策略
贪心算法优点和局限性:
优点:操作直接,实现简单,效率高
局限性:有时候并不能找到最优解,即无法保证能找到最优解,可能找到较差的解
贪心算法主要适用于以下两种情况
1.可以保证找到最优解:在这种情况下贪心算法是最优选择,因为它比回溯算法,动态规划更加高效
2.可以找到近似最优解:贪心算法在这种情况下也可以使用,对于很多问题而言,找到最优解很难,那么能够高效的查找到次优解也很不错
贪心算法的解决流程:
1.对问题进行分析
2.确定贪心的策略
3.证明正确性
455.分发饼干
链接:. - 力扣(LeetCode)
题目描述:
相关标签
相关企业
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子
i
,都有一个胃口值g[i]
,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干j
,都有一个尺寸s[j]
。如果s[j] >= g[i]
,我们可以将这个饼干j
分配给孩子i
,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。示例 1:
输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。 虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。 所以你应该输出1。示例 2:
输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出2.提示:
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1
思路:
因为饼干不能分开,因此我们不能用大饼干去喂喂口小的孩子,会造成饼干的浪费,因此我们的局部最优应该是每次找到一个大饼干,尽量去喂胃口大的孩子,全局最优就是可以喂饱最多的孩子,投喂过程如下图所示
我们需要先对孩子和饼干进行排序,便于我们找到胃口最多的小孩已经最大的饼干,因为我们的局部最优是拿最大的饼干喂胃口最大的孩子,所以只有当我们投喂成功时,才能进行下一块饼干的投喂,即如图所示,大小为9的饼干喂不了胃口为10的孩子,我们只有把大小为9的饼干喂给大小为7的孩子,才能进行下一次饼干的投喂,即大小为5的饼干
代码如下:
int cmp(int *a, int *b) { return *a - *b; } int findContentChildren(int* g, int gSize, int* s, int sSize) { if(gSize == 0) return 0; qsort(g, gSize,sizeof(int), cmp); qsort(s, sSize,sizeof(int), cmp); int child = 0; int index = sSize - 1; for(int i = gSize - 1; i >= 0 ; --i) { while( index >= 0 && s[index] >= g[i] ) { child++; index--; break; } } return child; }
376.摆动序列
链接:. - 力扣(LeetCode)
题目描述:
如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如,
[1, 7, 4, 9, 2, 5]
是一个 摆动序列 ,因为差值(6, -3, 5, -7, 3)
是正负交替出现的。- 相反,
[1, 4, 7, 2, 5]
和[1, 7, 4, 5, 5]
不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。
给你一个整数数组
nums
,返回nums
中作为 摆动序列 的 最长子序列的长度 。示例 1:
输入:nums = [1,7,4,9,2,5] 输出:6 解释:整个序列均为摆动序列,各元素之间的差值为 (6, -3, 5, -7, 3) 。示例 2:
输入:nums = [1,17,5,10,13,15,10,5,16,8] 输出:7 解释:这个序列包含几个长度为 7 摆动序列。 其中一个是 [1, 17, 10, 13, 10, 16, 8] ,各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。示例 3:
输入:nums = [1,2,3,4,5,6,7,8,9] 输出:2提示:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
思路:
我们可以根据题目进行分析,如下图所示,有三种情况,以第一种为例,上下坡
红色所标注的就是摆动,蓝色所标注的摆动的最长子序列,即为7,根据图形我们可以看出,我们的每一个峰值都是一个摆动序列,因此我们可以将不是峰值的数值进行删除,即删除单调坡上的元素,即其中蓝色X表示标注的元素,这就是局部最优,剩下的数组元素的个数就是我们摆动的序列的最长子序列,这就是全局最优
注意:因为题目要求返回的是摆动序列的最长子序列的长度,因此我们不需要实际进行删除的操作,只需要在遇到摆动时将其记录就可以
第二种情况,上下坡带有平坡
第三种情况,单调坡有平坡
代码如下:
int wiggleMaxLength(int* nums, int numsSize){ // 如果数组只有一个元素,则返回1,因为一个元素本身就构成了一个摆动序列 if(numsSize == 1) return 1; // 如果数组只有两个元素且两个元素不相等,则返回2,因为两个不相等的元素构成了一个摆动序列 if(numsSize == 2 && nums[0] != nums[1]) return 2; int cur = 0, pre = 0; int result = 1; // 遍历数组,计算相邻元素之间的差值,根据差值的符号确定摆动序列 for(int i = 0; i < numsSize - 1; i++) { // 当前元素与下一个元素的差值 cur = nums[i + 1] - nums[i]; // 如果前一个差值为非负数且当前差值为负数,或者前一个差值为非正数且当前差值为正数, // 则说明出现了摆动,摆动序列长度加一,并更新前一个差值 if((pre >= 0 && cur < 0) || (pre <= 0 && cur > 0)) { result++; pre = cur; } } return result; }
53.最大子数组和
链接:. - 力扣(LeetCode)
题目描述:
给你一个整数数组
nums
,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。子数组
是数组中的一个连续部分。示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4] 输出:6 解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。示例 2:
输入:nums = [1] 输出:1示例 3:
输入:nums = [5,4,-1,7,8] 输出:23提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
贪心思路:
我们在遍历数组时,需要一个变量不断去累加数组元素,如果当前的连续和是负数,,继续不断的相加只能让连续和变小,此时不如将我们新的数组元素作为连续和新的开始,因此我们就得出我们的局部最优,当求得连续和为负数,则直接抛弃它,并选择数组的下一个元素作为新的连续和起点,当我们得到连续和是正数,则进行保留,因为无论这个整数是大还是小,对数组后面的元素都只有增大的作用(遇到正数增大,遇到负数抵消部分影响),并且将这个值再进行记录,大致过程就如下所示
连续和为负数,则抛弃,连续和为正数,则进行最大连续和记录,一直遍历到数组为空文章来源:https://www.toymoban.com/news/detail-859403.html
代码实现:文章来源地址https://www.toymoban.com/news/detail-859403.html
int maxSubArray(int* nums, int numsSize) { int result = INT_MIN; int sum = 0; for(int i = 0; i < numsSize ;i++) { sum += nums[i]; result = sum > result ? sum : result; sum = sum < 0 ? 0 : sum; } return result; }
到了这里,关于贪心算法练习day.1的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!