题目详情

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

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

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

示例:

输入: [‘A’ 5, ‘B’ 4, ‘C’ 4, ‘D’ 2, ‘E’ * 1]， n = 5
输出: 25

思路

  • 题意很简单，可是完全没思路。然后看答案吧，看了半天才看懂，果然只是凡人呐 QAQ
  • 对tasks按照任务进行计数，记数目最多的任务为t，mx
  • 问题转化为在tmax个任务之间的“槽”内尽可能安插别的任务，使idle最小化
  • 本例中，数目最多的任务为t为 ‘A’ ，其间隔数n为5，我们先拟定一个这样的框架
    • A o o o o o A o o o o o A o o o o o A o o o o o A
  • 标记为 ‘o’ 的槽用任务数递减的来插入，也就变为
    • A B o o o o A B o o o o A B o o o o A B o o o o A
    • A B C o o o A B C o o o A B C o o o A B C o o o A
    • A B C D o o A B C D o o A B C o o o A B C o o o A
    • A B C D E o A B C D o o A B C o o o A B C o o o A
  • 当n为2的时候
    • A o o A o o A o o A o o A
    • A B o A B o A B o A B o A
    • A B C A B C A B C A B C A
    • A B C A B C A B C A B D A C D E

具体代码

  1. /**
  2.  * @param {character[]} tasks
  3.  * @param {number} n
  4.  * @return {number}
  5.  */
  6. var leastInterval = function(tasks, n) {
  7.     let arr = [], obj = {}
  8.     let mx = 0, mxCnt = 0
  9.     let len = tasks.length
  10.     for(let i = 0; i < len; i++) {
  11.         if(obj[tasks[i]]) obj[tasks[i]]++
  12.         else obj[tasks[i]] = 1
  13.     }
  14.     for(let key in obj) {
  15.         arr.push({type: key, num: obj[key]})
  16.     }
  17.     arr.sort(function(a, b) {
  18.         return b.num - a.num
  19.     })
  21.     let i = 0
  22.     mx = arr[0].num
  23.     while(i < arr.length && arr[i].num === mx) i++
  25.     return Math.max(len, (mx - 1) * (n + 1) + i)
  27. };

Array - 48. 旋转图像

题目详情

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明：

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例:

给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
]

原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

思路

  • 先沿右下对角线进行交换，然后再以水平线进行交换

具体代码

  1. /**
  2.  * @param {number[][]} matrix
  3.  * @return {void} Do not return anything, modify matrix in-place instead.
  4.  */
  5. var rotate = function(mat) {
  6.     let xLen = mat[0].length,
  7.         yLen = mat.length
  9.     for(let y = 0; y < xLen - 1; y++) {
  10.         for(let x = 0; x < xLen - 1 - y; x++) {
  11.             [mat[y][x], mat[xLen - 1 - x][yLen - 1 - y]] = [mat[xLen - 1 - x][yLen - 1 - y], mat[y][x]]
  12.         }
  13.     }
  14.     for(let y = 0; y < yLen / 2; y++) {
  15.         for(let x = 0; x < xLen; x++) {
  16.             [mat[y][x], mat[yLen - 1 - y][x]] = [mat[yLen - 1 - y][x], mat[y][x]] 
  17.         }
  18.     }
  19. };