首页 > 其他 > 详细

leetcode.621 任务调度器(砖)

时间:2020-06-03 23:59:34      阅读:97      评论:0      收藏:0      [点我收藏+]

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

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

你需要计算完成所有任务所需要的最短时间。

示例 1:
输入: tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 2
输出: 8
执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
注:
任务的总个数为 [1, 10000]。
n 的取值范围为 [0, 100]。

 

思路: 这题只是想到组合吧,挑选出频率高的字符,然后用其他字符来填充,看看有多少种组合。但由于没搞明白时间是咋算的。。。
大神思路: 分块的计算:将字符分为长度为 n + 1的最高频数-1 块。统计出各个字符出现的频率,然后排序,将频率最高的数作为第一个数,然后将其他频率的数依次填入这些最高频字符的中间,最后计算最后一块的长度。
例如计算AAAABBBEEFFGG 3

1.统计出各字符的频率,按升序排列,
则为:「G,2」「F,2」「E,2」「B,3」「A,4」
2.根据最高频的数为 A,停止等待的时间为 n,那么构建一个以 A 为基字母,长度为 4 的的字符块。
此时为 AXXX-AXXX-AXXX-A (X 代表空位)
3.将第二高频的数加入,则为 ABXX-ABXX-ABXX-A
4.将第三高频的数加入,则变为 ABEX-ABEX-ABEX A
5.将第四高频的数加入,则为:ABEF ABEF ABFG A
6.观察规律,第五步中一共有 A 为首字母的块数为 3(最高频-1)* 4(n+1)=12
此时要注意还有末尾的 A,可以用 25 - i 表示,i 具体看代码的意思。

class Solution {
    public int leastInterval(char[] tasks, int n) {
         // 判空 
        if(tasks.length < 0 || tasks == null) throw new IllegalArgumentException();
        int[] c = new int[26];
        for(char t : tasks){
            c[t-A]++;
        }
        Arrays.sort(c);
        int i = 25;  // 表示 i 的 长度
        //  看块的基准的字母长度,因为有可能是频率一样的字符
        // 此时就需将频率一样的字符看做整体,而 25 - i 就是末尾字母的长度。
        while( i > 0 && c[i] == c[25]) i--;   
        return Math.max(tasks.length,(c[25]-1)*(n+1)+25-i);
    }
}

转自:https://blog.csdn.net/weixin_40904220/article/details/88549205

leetcode.621 任务调度器(砖)

原文:https://www.cnblogs.com/zl1991/p/13040872.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!