LeetCode 题解一

LeetCode 题解一。

621 Task Scheduler

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

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

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

javascript

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

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

javascript

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

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

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

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

javascript

const newLeftNode, newRightNode;

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

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

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

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

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

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

有各种 Corner Case 要处理..

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

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

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

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

这样就 ok 了。