12380网站建设情况汇报,企业邮箱格式怎么注册,重庆推广网站排名,wordpress会员积分任务调度器
https://leetcode.cn/problems/task-scheduler/
描述 给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行#xff0c;并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间#…任务调度器
https://leetcode.cn/problems/task-scheduler/
描述 给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间CPU 可以完成一个任务或者处于待命状态。 然而两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间因此至少有连续 n 个单位时间内 CPU 在执行不同的任务或者在待命状态。 你需要计算完成所有任务所需要的最短时间。
示例 1
输入tasks [A,A,A,B,B,B], n 2
输出8
解释A - B - (待命) - A - B - (待命) - A - B在本示例中两个相同类型任务之间必须间隔长度为 n 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 1 0 4 10^4 104tasks[i] 是大写英文字母n 的取值范围为 [0, 100]
算法实现
1 方案 1
function leastInterval(tasks: string[], n: number): number {let result // 最终队列执行的结果const dict {} // 对归类进行存储tasks.forEach((item) {dict[item] ? (dict[item] ) : (dict[item] 1)})while(true) {// 任务清单const keys Object.keys(dict)// 任务处理完毕跳出if (!keys.length) {break}// 正常处理过程let tmp [] // 用于存储 1 n个任务单元for (let i 0; i n; i) {let max:number 0 // 找到最大的任务let key:stringlet pos:number// 遍历任务清单keys.forEach((item, idx) {// 当前任务数量大于maxif (dict[item] max) {max dict[item] // 存储更新maxkey item // 存储更新当前任务pos idx // 存储更新当前任务下标索引用于后续的删除操作}})// 没有匹配到key, 直接跳出此次循环if (!key) {break}// 找到了keytmp.push(key) // 临时队列添加当前的keykeys.splice(pos, 1) // 将当前key从任务队列中删除dict[key] -- // 更新key的长度已消费完成删除来更新剩余个数// 当全部消费完成移除当前的任务if (dict[key] 1) {delete dict[key]}}result tmp.join().padEnd(n 1, -) // 如果不全补充冷却时间}// 边界的处理, 最后不要出现冷却时间result result.replace(/-$/, )return result.length
}关键需求分析 两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间因此至少有连续 n 个单位时间内 CPU 在执行不同的任务或者在待命状态。要求完成所有任务的最短时间 从上面的描述和示例中可见 队列中有A,B,C,…, 现在开启了一个任务如果当前开启了A任务那接下来n个的任务中不能有A了如果其他任务不够n的长度那么要冷却等待只要现在队列中还有任务我就要处理任务本身和n个任务冷却时间的 n1 的任务也就是从队列中取出这些任务来存放求最短的存放时间 如何做到最短考虑使用最多的任务优先处理尽量不会有剩余交叉着来少的来进行插缝作业这样即保证少的任务使用了又保证多的任务不会用冷却时间处理来占用更多资源 这个算法在实现上效率不高
2 方案 2
function leastInterval(tasks: string[], n: number): number {// 初始化一个矩阵用于存储给定任务的数量的字典const cnts Array(26).fill(0);for(const c of tasks) {cnts[c.charCodeAt(0) - A.charCodeAt(0)];}// 统计出任务中对多的数量let max 0, tot 0;for (let i 0; i 26; i) {max Math.max(max, cnts[i]);}// 更新tot变量的值用于统计具有最多执行次数的任务数量for (let i 0; i 26; i) {tot max cnts[i] ? 1 : 0;}// 这里是最核心的算法return Math.max(tasks.length, (n 1) * (max - 1) tot)
};这是官方示例效率很高这里用到charCodeAt() 方法可返回指定位置的字符的 Unicode 编码后续有时间再研究下https://leetcode.cn/problems/task-scheduler/solution/ren-wu-diao-du-qi-by-leetcode-solution-ur9w/ 中的方法二构造
