day27 贪心算法

这篇具有很好参考价值的文章主要介绍了day27 贪心算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.什么是贪心?
比如10张钞票,有1,5,20,100等面额,取五张,如何取得到数额最多的钱?每次取面额最大的那张钞票;就是每个阶段的局部最优;全局最优就是最后拿到的钞票数最大;局部最优推出全局最优;
题目描述
day27 贪心算法,贪心算法,算法

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 right1 = gSize-1;
    int right2 = sSize-1;
    int count = 0;//记录投喂的孩子
    while(right1 >= 0 && right2 >= 0)
    {
        if(s[right2] >= g[right1])
        {
            count++;
            right1--;
            right2--;
        }
        else
        {
            right1--;
        }
    }
    return count;
}

题目描述
day27 贪心算法,贪心算法,算法

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){

    // 下标 0  1  2  3  4
    // gas  1  2  3  4  5
    // cos  3  4  5  1  2
    // cur -2 -2 -2  4  3 (净增) 如果是负数,不可能走完一圈只能从下标3(不是负数)开始才能跑完一圈
    int cur = 0; //每一站剩余的油量
    int totalSum = 0;//所有剩余油量之和 < 0 不可能跑完一圈
    int start = 0;// 记录cur不是负数的下标
    for(int i = 0;i< gasSize;i++){
        cur += (gas[i] - cost[i]);
        totalSum += (gas[i] - cost[i]);
        if(cur < 0){
            start = i+1;
            cur = 0;//新起点,剩余油量归0.重新统计
        }
    }
    if (totalSum < 0){
        return -1;
    }
    return start;
}

题目描述
day27 贪心算法,贪心算法,算法
分析:摆动序列,就是前后相减保证一正一负;对于复杂的序列,比如:1,17,5,10,13,15,10,5,16,8
day27 贪心算法,贪心算法,算法
对于这种,我们只需要记录坡顶和坡底元素;中间的10,13,10可以忽略;
prediff = nums[i] - nums[i-1]; 表示前一个坡度;
curdiff = nums[i+1] - nums[i];;表示后一个坡度;
如果 prediff 和 curdiff 一正一负(prediff > 0 && curdiff < 0 || prediff < 0 && curdiff > 0)表示找到了一个峰值;计数++;
细节分析:
1)上下坡有平坡:1 2 2 2 1 摆动长度应该是3 (1 2 1)前面加上prediff 或者 curdiff 加等于号即可(prediff > =0 && curdiff < 0 || prediff < = 0 && curdiff > 0);
2)首尾元素,首尾元素默认都算,但是长度为2的时候,需要前面加一个元素,使有prediff,符合我们上面判断逻辑;末尾元素我们当作是一个摆动,所以res = 1,就是末尾的一个;
day27 贪心算法,贪心算法,算法
3)单调有平坡 1 2 2 4 5 只有两个摆动
day27 贪心算法,贪心算法,算法
每次找到摆动数后,prediff = curdiff ;prediff向前移动;文章来源地址https://www.toymoban.com/news/detail-573134.html

int wiggleMaxLength(int* nums, int numsSize){
    int res = 1;
    if (numsSize == 1) {
        return res;
    }
    
    int prediff = 0; // nums[i] - nums[i-1]
    int curdiff = 0; // nums[i+1] - nums[i]

    for (int i = 0;i < numsSize - 1;i++) {// i遍历到倒数第二个
        curdiff = nums[i+1] - nums[i];
        if ((prediff >= 0 && curdiff < 0) || (prediff <= 0 && curdiff > 0)){
            res++;
           prediff = curdiff;// 只记录变化的坡度,遇到摆动,记录下一个坡,就是遇到平坡不会记录
        }
    }
    return res;
}

到了这里,关于day27 贪心算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 贪心算法练习day.1

    贪心算法是一种常见的解决优化问题的方法,其基本思想就是在问题的每个决策阶段,都选择当前看起来最优的选择,即 贪心地做出局部的最优决策,以此得到全局的最优解, 例如在十张面额不同的钞票,让我们去取5张,那如何拿到最多的钱呢?那我们每次取钞票时只需要

    2024年04月27日
    浏览(36)
  • day 34 贪心算法

    1005.K次取反后最大化的数组和 第一步:将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小 第二步:从前向后遍历,遇到负数将其变为正数,同时K– 第三步:如果K还大于0,那么反复转变数值最小的元素,将K用完 第四步:求和 134. 加油站 暴力求解, 从每一个位

    2024年02月11日
    浏览(36)
  • 贪心算法练习day2

    1)初始化最小字母为‘Z’,确保任何字母都能与之比较 2)遍历单词,找到当前未删除字母中的最小字母 3)获取当前位置的字母  current = word.charAt(i); 4)删除最小字母之前的所有字母  word=word.substring(index+1); 5)  将最小字母添加到结果字符,更新剩余可删除字母数量 t -=

    2024年02月20日
    浏览(40)
  • DAY40:贪心算法(九)单调递增的数字(贪心的思路)

    本题暴力解法也需要看一下,虽然暴力解法超时了,但是这种思路是一种很基础的思路,需要了解 数字是没有办法直接采用下标遍历的 ,如果 要for循环遍历每个位置的数字,需要把数字转成字符串string 当且仅当每个相邻位数上的数字 x 和 y 满足 x = y 时,我们称这个整数是

    2024年02月12日
    浏览(50)
  • Day37 贪心算法part06

    前面都想到了,结果最后n[i]给写错了直接写成9了,得把后面的全都改成9才行 摄像头的覆盖范围是上中下 遇到叶子结点,放到叶子结点的父节点 每隔两个空节点放一个摄像头 所以要用后序遍历 把结点分为三个状态:0无覆盖1有摄像头2有覆盖 空节点要设置为有覆盖的状态

    2024年02月19日
    浏览(47)
  • Day28- 贪心算法part02

    题目一:122. 买卖股票的最佳时机II 122. 买卖股票的最佳时机 II 给你一个整数数组  prices  ,其中  prices[i]  表示某支股票第  i  天的价格。 在每一天,你可以决定是否购买和/或出售股票。你在任何时候  最多  只能持有  一股  股票。你也可以先购买,然后在  同一天  

    2024年01月15日
    浏览(48)
  • Day36 贪心算法 part05

    一个字母区间仅有几个字母 前一个字母区间有的字母后面都没有 天才举一反三写出来了

    2024年02月19日
    浏览(58)
  • Day32- 贪心算法part06

    题目一:738. 单调递增的数字  738. 单调递增的数字 当且仅当每个相邻位数上的数字  x  和  y  满足  x = y  时,我们称这个整数是 单调递增 的。 给定一个整数  n  ,返回  小于或等于  n  的最大数字,且数字呈  单调递增  。 从高位到低位遍历整数 n 的每一位数字,当

    2024年01月22日
    浏览(46)
  • Day30- 贪心算法part04

    题目一:860. 柠檬水找零  860. 柠檬水找零 在柠檬水摊上,每一杯柠檬水的售价为  5  美元。顾客排队购买你的产品,(按账单  bills  支付的顺序)一次购买一杯。 每位顾客只买一杯柠檬水,然后向你付  5  美元、 10  美元或  20  美元。你必须给每个顾客正确找零,也就

    2024年01月19日
    浏览(42)
  • Day31- 贪心算法part05

    题目一:453. 无重叠区间  435. 无重叠区间 给定一个区间的集合  intervals  ,其中  intervals[i] = [starti, endi]  。返回  需要移除区间的最小数量,使剩余区间互不重叠  。 主要思想是优先保留结束时间早的区间,这样留给其他区间的空间就更多,从而减少需要移除的区间数量

    2024年01月19日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包