LeetCode 题解一。

621 Task Scheduler

题目大意:CPU 调度,给一串用 Char 表示的任务列表,一个周期运行一个,规定相同两个任务之间的运行间隔不能超过 n,求最少需要多少个周期能跑完。

由于任务之间应该是互相独立的,所以就用贪心算法吧,每次从可以运行的任务中拿一个出来跑,并记下最近一次的运行时间(判断能否运行这个任务时用到),一直循环直到完成所有任务。

需要两张 k-v 表,一张记录最近运行的时间 last,一张记录当前所有任务还剩多少次没完成 remain,每轮循环找可运行的任务:

1
remain[task] > 0 && last[task] + n < current

这样会报 EA,想了一下贪心有点问题,对于一些高频任务应该高优先级执行,跟实际操作系统是类似的,因此在遍历 remain 表的时候应该按剩余次数从大到小遍历:

1
2
3
for(let entry of Object.entries(remain).sort((p, n) => p[1] < n[1])) {
// ...
}

最后判断任务是否做完可以直接查 remain 表看看是否各项都是 0,但可以再额外建一个变量表示实际任务运行的次数,这样每次判断就快多了。

623 Add One Row to Tree

题目大意:给一个二叉树,在第 d 层添加一行节点,每个节点的值为 v

题目其实把算法都写清楚了,对所有在第 d-1 层的非空节点,都新建两个子节点,把原左子树作为新左孩子的左子树;原右子树作为新右孩子的右子树,即:

1
2
3
4
5
6
7
const newLeftNode, newRightNode;

newLeftNode.left = node.left;
newRightNode.right = node.right;

node.left = newLeftNode;
node.right = newRightNode;

因此思路就是用队列做层次遍历,到树高为 d-1 时处理一下,直接把原 root 返回,原地变换。

再处理一下边界条件(d = 1 或树高+1)就可以了。

628 Maximum Product of Three Numbers

题目大意:给一个整数数组,找出三个数,乘积最大

乍一看这不是有点简单吗,遍历一遍找出最大的三个数,乘一下就好了啊,然后就疯狂 WA…

有各种 Corner Case 要处理..

结果三个数的情况

最后选出的结果肯定是三个数,这三个数的符号只有 4 种情况:

  1. 正正正:三个正数只要找最大的三个数相乘就行了
  2. 正正负:这三个数乘积是负的,什么情况下会出现呢?考虑加入一个正数,此时数组里的情况是「正正负正」,那么三个正数的乘积必定比负数要大,不会选出「正正负」;考虑加入一个负数,此时数组里的情况是「正正负负」,那么可以通过选择「正负负」来使最终结果为正数,也不会选出「正正负」。因此选出这三种数的唯一情况是:只有三个数,这三个数的符号分别为「正正负」。
  3. 正负负:乘积为正,找最大的正数和绝对值最大的两个负数就行了
  4. 负负负:乘积为负,同样考虑什么情况出现。考虑加一个正数,此时「负负负正」,不会选出「负负负」;加一个负数,此时「负负负负」,负数需要找绝对值最小(也就是最大)的三个数乘积

所以额外处理 2 和 4,其他情况结果就是 1、3 中的最大值。

0 的处理

这样下来还是不能 AC,对于 [0, 0, 0, 4] 没处理好,这里通过计算非 0 数字个数再来处理:

  1. 3 个或以上非 0 数字,就是前面的情况
  2. 3 个以下非 0 数字,结果必为 0,因为一定会选到 0

这样就 ok 了。