内容简介:假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i ,都有一个胃口值 gi ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j ,都有一个尺寸 sj 。如果 sj >= gi ,我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。假设输入给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行,并且每
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 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个不一样的任务
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); } 复制代码
以上所述就是小编给大家介绍的《常用算法之贪心算法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 贪心算法和分治算法
- 算法小专栏:贪心算法
- 算法基础--贪心策略
- 【LeetCode】贪心算法--分发糖果(135)
- 【LeetCode】贪心算法--划分字母区间(763)
- 【LeetCode】贪心算法--买卖股票的最佳时机 II(122)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。