专栏首页爬蜥的学习之旅常用算法之贪心算法

常用算法之贪心算法

思路:求解问题时,总是选当前最好的选择,不从整体上考虑。因而选用贪心算法必须保证当前选的最好的必定是整体最好的

示例

分发饼干

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i ,都有一个胃口值 gi ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j ,都有一个尺寸 sj 。如果 sj >= gi ,我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。 假设输入[1,2], [1,2,3],那么输出为2。分析如下

  • 要尽可能的满足更多的小孩,那么最小尺寸的饼干应该分给最小胃口的那个人,这样才不至于后面胃口大的小孩吃不到,儿胃口大的小孩吃小的肯定无法满足。这种选择恰好也是全局最佳的选择
public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i=0;
        int j=0;
        int num=0;
        while(i<g.length && j<s.length){
            if(s[j]>=g[i]){
                num++;
                i++;
                j++;
            }else{
                j++;
            }
        }
        return num;
    }
复制代码

任务调度器

给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行,并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务,或者在待命状态。

然而,两个相同种类的任务之间必须有长度为 n 的冷却时间,因此至少有连续 n 个单位时间内 CPU 在执行不同的任务,或者在待命状态。

你需要计算完成所有任务所需要的最短时间。 假如输入 tasks = ['A','A','A','B','B','B'], n = 2 输出为8,执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B。分析如下

  • 为了使得整体时间最短,那么冷却时间肯定是最少的,因此要尽可能保证两个相同的任务之间的执行间隔为n。换句话说就是贪心的选择执行n个不一样的任务,使得CPU能够充分利用
  • 要选择先执行的任务,得考虑如何使得当前选择整体是最优的,加入随便选择一个任务A执行,当存在一个任务B它的任务数比选择的任务数要多时,这意味着B之间少了一次执行A的机会,也就是增加了要冷却的风险,因而每次选择任务数最多的来执行
public int leastInterval(char[] tasks, int n) { 
        int[] taskArr=new int[26];
        for(char c:tasks){
            taskArr[c-'A']++;
        }
        int maxLength=n;
        int interval=0;
        while (havaTask(taskArr)){
            //先执行任务数最多的任务
            int top = getTopTaskNotExecute(taskArr,Collections.emptyList());
            interval++;
            List<Integer> list = new ArrayList<>();
            list.add(top);
            for (int i=0;i<maxLength;i++)
            {
                //贪心的选择没有执行过的‘n’个任务最多而且没有执行过的任务
                Integer nextTop = getTopTaskNotExecute(taskArr, list);
                if (nextTop==-1){
                    maxLength=list.size()-1;
                    break;
                }
                interval++;
                list.add(nextTop);
            }
            if (list.size()-1!=n && havaTask(taskArr)){
                interval+=n-list.size()+1;
            }
        }
        return interval;
    }
    
    public boolean havaTask(int[] tasks){
        for(int i=0;i<tasks.length;i++){
            if(tasks[i]>0){
                return true;
            }
        }
        return false;
    }
    
    public Integer getTopTaskNotExecute(int[] tasks,List<Integer> executeTasks){
        int maxTaskNums=0;
        int maxNumsTaskIndex=-1;
        for(int i=0;i<tasks.length;i++){
            if(!executeTasks.contains(i) && tasks[i]>maxTaskNums){
                maxTaskNums=tasks[i];
                maxNumsTaskIndex=i;
            }
        }
        if(maxNumsTaskIndex!=-1){
          tasks[maxNumsTaskIndex]--;  
        }
        return maxNumsTaskIndex;
    }
}
复制代码

当然如果只要解决问题,可以直接计算出结果

还是使用贪心的策略来作为逻辑考虑的

  • 假设只有1个任务数最多,而且是k个,共需要至少间隔数为 k-1 个间隔,那么间隔消耗时间为 n*(k-1),k个任务本身执行时间为 k,总共时间至少为 n*(k-1)+k
  • 假设最多的任务数一样的不止1个有m个,当执行完一遍最多任务数一个时,还有剩余的 m-1 个任务,而且他们的数量肯定都是1,且各不相同,所以总共时间为 n*(k-1)+k+(m-1)=(n+1)*(k-1)+m
  • 上述假设只是从单个任务的最多量来看的,没有考虑独立的任务数,有多少个任务肯定至少要执行多少的时间,最终取最大值即可
public int leastInterval(char[] tasks, int n) { 
int[] taskArr=new int[26];
for(char c:tasks){
    taskArr[c-'A']++;
}
Arrays.sort(taskArr);
int m=0;
for(int i=25;i>-1;i--){
    if(taskArr[i]==taskArr[25]){
        m++;
    }else{
        break;
    }
}
return Math.max(tasks.length,(taskArr[25]-1)*(n+1)+m);
}
复制代码

附录

贪心算法思路

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 初识Storm

    爬蜥
  • 从java的NIO版hello world看java源码,我们能看到什么?

    SelectorProvider提供的所有provider都是同一个对象。如果没有,它会通过AccessController.doPrivileged来给获取p...

    爬蜥
  • Netty中的ChannelHander详解

    channelHandler是用来做什么的?ChannelHandler用来处理组件之间的交互,结合它的状态做各种业务,通过ChannelPipelinel来连...

    爬蜥
  • 刷题打卡:在两个长度相等的排序数组中找到上中位数

    给定两个有序数组arr1和arr2,已知两个数组的长度都为N,求两个数组中所有数的上中位数。要求时间复杂度O(logN),空间复杂度O(1)

    帅地
  • 几种设计良好结构以提高.NET性能的方法

    设计良好的系统,除了架构层面的优良设计外,剩下的大部分就在于如何设计良好的代码,.NET提供了很多的类型,这些类型非常灵活,也非常好用,比如List,Dicti...

    Edison.Ma
  • 矩阵求逆的几种方法总结(C++)

    文内程序旨在实现求逆运算核心思想,某些异常检测的功能就未实现(如矩阵维数检测、矩阵奇异等)。

    xiaoxi666
  • C语言第三讲,基本数据类型

            C语言第三讲,基本数据类型 一丶基本数据类型讲解 在C语言当中,有四种基本数据类型 分别是: 整形 浮点型 指针 聚合类型(数组和结构) 整型家...

    IBinary
  • 干货|十分钟快速get蚁群算法(附代码)

    之前分享了TSP的动态规划解法,本期来介绍它的另一种解法——蚁群算法。 什么?不知道?次元壁?高大上? 小编接下来这套 素质三连 攻略三连...

    用户1621951
  • BZOJ2194: 快速傅立叶之二(NTT,卷积)

    attack
  • 干货 | 十分钟快速搞懂什么是蚁群算法(Ant Colony Algorithm, ACA)(附代码)

         小编接下来这套 素质三连 攻略三连 会帮你十分钟快速搞定蚁群算法是什么、怎么用、注意啥,从零开始突破次元壁!!!

    短短的路走走停停

扫码关注云+社区

领取腾讯云代金券