贪心算法练习day.1

理论基础

贪心算法是一种常见的解决优化问题的方法，其基本思想就是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部的最优决策，以此得到全局的最优解，例如在十张面额不同的钞票，让我们去取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

贪心思路：

我们在遍历数组时，需要一个变量不断去累加数组元素，如果当前的连续和是负数，，继续不断的相加只能让连续和变小，此时不如将我们新的数组元素作为连续和新的开始，因此我们就得出我们的局部最优，当求得连续和为负数，则直接抛弃它，并选择数组的下一个元素作为新的连续和起点，当我们得到连续和是正数，则进行保留，因为无论这个整数是大还是小，对数组后面的元素都只有增大的作用（遇到正数增大，遇到负数抵消部分影响），并且将这个值再进行记录，大致过程就如下所示

连续和为负数，则抛弃，连续和为正数，则进行最大连续和记录，一直遍历到数组为空

代码实现：

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;
}