中国建设银行产品信息网站,58同城网站建设推广排名,雨岑信息科技有限公司做企业型网站做的怎么样_公司规模如何,石家庄免费自助建站模板题目链接#xff1a;leetcode 621
1.题目
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行#xff0c;并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间#xff0c;CPU 可以完成一个…题目链接leetcode 621
1.题目
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间CPU 可以完成一个任务或者处于待命状态。
然而两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间因此至少有连续 n 个单位时间内 CPU 在执行不同的任务或者在待命状态。
你需要计算完成所有任务所需要的 最短时间 。
2.示例
1)示例 1 输入tasks [“A”,“A”,“A”,“B”,“B”,“B”], n 2 输出8 解释A - B - (待命) - A - B - (待命) - A - B 在本示例中两个相同类型任务之间必须间隔长度为 n 2 的冷却时间而执行一个任务只需要一个单位时间所以中间出现了待命状态。
2)示例 2 输入tasks [“A”,“A”,“A”,“B”,“B”,“B”], n 0 输出6 解释在这种情况下任何大小为 6 的排列都可以满足要求因为 n 0 [“A”,“A”,“A”,“B”,“B”,“B”] [“A”,“B”,“A”,“B”,“A”,“B”] [“B”,“B”,“B”,“A”,“A”,“A”] … 诸如此类 示例 3 输入tasks [“A”,“A”,“A”,“A”,“A”,“A”,“B”,“C”,“D”,“E”,“F”,“G”], n 2 输出16 解释一种可能的解决方案是 A - B - C - A - D - E - A - F - G - A - (待命) - (待命) - A - (待命) - (待命) - A 提示 1 task.length 104 tasks[i] 是大写英文字母 n 的取值范围为 [0, 100]
3.分析
我们首先有个直觉为了使得排列的序列长度更小我们需要把数量较多的任务的优先级放得比较高。那么考虑考虑一个样例task[“A”,“A”,“A”,“B”,“B”,“B”,“C”],n2,那么我们优先考虑最多的任务A由AXXAXXA那么对于下一个任务B它可以放置在没有的位置那么就变成了ABXABXAB可以发现这使得任务序列加了1因为B的个数和A的个数是相等的它需要在末尾加一个任务。但对于C来说它可以插到AB后面即可变为AB C ABC AB
4.代码
class Solution {
static bool cmp(int a,int b){return ab;
}
public:mapchar,int map1;vectorint num;int leastInterval(vectorchar tasks, int n) {for(int i0;itasks.size();i)if(map1.count(tasks[i])0) map1[tasks[i]]1;elsemap1[tasks[i]];for(int c0;c25;c){if(map1.count(Ac)) num.push_back(map1[Ac]);} sort(num.begin(),num.end(),cmp);vectorint ans;int lennum[0](num[0]-1)*n;int cnt0;for(int i1;inum.size();i)if(num[i]num[0]) cnt;if(tasks.size()cntlen) return tasks.size();return cntlen;}
};
终于刷完了top1001里所有中等难度的题目orz
