贪心算法练习day.1

这篇具有很好参考价值的文章主要介绍了贪心算法练习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

思路:

因为饼干不能分开,因此我们不能用大饼干去喂喂口小的孩子,会造成饼干的浪费,因此我们的局部最优应该是每次找到一个大饼干,尽量去喂胃口大的孩子,全局最优就是可以喂饱最多的孩子,投喂过程如下图所示

贪心算法练习day.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

思路:

我们可以根据题目进行分析,如下图所示,有三种情况,以第一种为例,上下坡

贪心算法练习day.1,#算法练习#代码随想录训练营,算法,学习,贪心算法

红色所标注的就是摆动,蓝色所标注的摆动的最长子序列,即为7,根据图形我们可以看出,我们的每一个峰值都是一个摆动序列,因此我们可以将不是峰值的数值进行删除,即删除单调坡上的元素,即其中蓝色X表示标注的元素,这就是局部最优,剩下的数组元素的个数就是我们摆动的序列的最长子序列,这就是全局最优

注意:因为题目要求返回的是摆动序列的最长子序列的长度,因此我们不需要实际进行删除的操作,只需要在遇到摆动时将其记录就可以

第二种情况,上下坡带有平坡

贪心算法练习day.1,#算法练习#代码随想录训练营,算法,学习,贪心算法

第三种情况,单调坡有平坡

贪心算法练习day.1,#算法练习#代码随想录训练营,算法,学习,贪心算法

代码如下:

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

贪心思路:

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

贪心算法练习day.1,#算法练习#代码随想录训练营,算法,学习,贪心算法

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

代码实现:文章来源地址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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录day24 开启回溯算法

    感觉回溯算法其实和递归很像,也是用递归的做法,也有三部曲,但又不太一样的地方是递归中类似二叉树,只有纵向遍历(一层层往下遍历,没有横向遍历),而回溯算法中多的for循环就是横向遍历,说实话这一点我没有理解的太深,只是知道它类似于两个for循环中的第一

    2024年01月16日
    浏览(53)
  • 代码随想录算法训练DAY25|回溯2

    力扣题目链接 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。 说明: 所有数字都是正整数。 解集不能包含重复的组合。 示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]] 示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]

    2024年01月22日
    浏览(63)
  • 代码随想录算法训练day4 | 链表

    目录 24. 两两交换链表节点 19. 删除链表倒数第n个节点 方法一:普通写法 方法二:双指针法 面试题:找链表相交节点 142. 判断环形链表 虚拟头节点的本质意义在于减少了特殊情况的处理。不用判断该节点是否在链表的第一位。 定义快慢两个指针。 fast先走n步,再让fast和s

    2024年02月04日
    浏览(67)
  • 代码随想录算法训练DAY27|回溯3

    力扣题目链接 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明: 所有数字(包括 target)都是正整数。 解集不能包含重复的组合。 示例 1: 输入:candidates = [2,3,6,

    2024年01月23日
    浏览(58)
  • 代码随想录Day20 回溯算法 LeetCode77 组合问题

    以下内容更详细解释来自于:代码随想录 (programmercarl.com) 回溯法也叫回溯搜索法,是搜索法的一种,我们之前在二叉树中也经常使用到回溯来解决问题,其实 有递归就有回溯 ,有的时候回溯隐藏在递归之下,我们不容易发觉,今天我们来详细介绍一下什么是回溯,它能解决哪些问题.

    2024年02月08日
    浏览(54)
  • 【一天三道算法题】代码随想录——Day15(困难题只有一道)

    一. 滑动窗口最大值 题目链接:力扣 思路:         这道题我认为最难的是编程语言本身并没有一个可以让你完全直接开始使用的一个数据结构,也就是说要自己造轮子。并且为了尽可能的减少维护元素的个数我们要学会去在能实现功能的前提下,维护尽可能少的数组元

    2024年02月15日
    浏览(46)
  • 代码随想录day02

    ● 力扣题目链接 ● 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 思路 ● 暴力排序,时间复杂度O(n + nlogn) ● 使用双指针,时间复杂度O(n) 代码 ● 力扣题目链接 ● 给定一个含有 n 个正整数的数组和一个正整

    2024年02月13日
    浏览(50)
  • 代码随想录day11

    20. 有效的括号   思路:这里用模拟栈的方法会更好理解,也就是我们每次遇到朝左方向的三种类型的时候,就加入相反方向的右括号到result栈中。由于栈是一个先进后出的方式,所以我们会有一个判断stack当前为不为空,和stack[-1]是不是和当前循环到的括号相同。如果说相同

    2024年02月13日
    浏览(45)
  • 代码随想录Day58

    昨天因为志愿活动和笔试耽误了一整天,今天继续学习动规解决子序列问题。 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,\\\"ace\\\"是\\\"abcde\\\"的一个子序列,

    2023年04月27日
    浏览(55)
  • 代码随想录day44

    完全背包 其实就是每个物品可以使用无数次,给我们一个容器,装满这个容器的最大价值是多少。 思路: 如果求组合数就是外层for循环遍历物品,内层for遍历背包。 如果求排列数就是外层for遍历背包,内层for循环遍历物品。 完全背包的组合和排序 518. 零钱兑换 II 题目 给你

    2023年04月17日
    浏览(67)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包