Leetcode 621:任务调度器

题目描述

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

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

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

示例

示例 1:

输入: tasks = ["A","A","A","B","B","B"], n = 2
输出: 8
执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.

题目思想

利用贪心算法,首先统计出现的各个字母的次数,然后按照由大到小排序。然后选择其中出现次数最多的字母开始安放。例如例子中,我们假设先安排A(因为例子中A、B出现次数相同),那么就会出现:

0123456
AAA

然后开始安排B

01234567
ABABAB

其实这样可以总结为一个公式:
(n+1) * (count-1)+m
其中n为题目给定的冷却时间,count为字母出现最多的次数,m为出现最多次数的字母的个数。

当然,若单个字母的数量远远大于重复字母的种类数时,实际上所求结果就是这个vector的长度。所以这个时候只需要在最后做过判断即可,即求两者的最大值。

代码实现

Leetcode 617:合并二叉树

题目描述

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

题目思想

其实这个题的思想和另一个合并两个排序的二叉树(
http://www.yushuai.xyz/2019/03/04/4258.html)思想是一样的。我们可以想都把所有的数据加到第一个二叉树上。类似于那个题目,有这样几个情况:

  1. 若第一个链表为空,则直接返回第2个;
  2. 若第二个链表为空,则直接返回第1个;
  3. 其实若两个链表都为空的话,在第一个if语句判断的时候返回了第二个链表,而第2个链表为空,所以正好也是返回了NULL。
  4. 若两个二叉树都有值,则将第二个二叉树的值加到第一个上。
  5. 然后递归调用左树和右树的计算。
  6. 最后返回第一个二叉树。

代码实现

若代码出现错误,可查看:http://tech.yushuai.xyz/2019/10/15/leetcode191015/