2019-10-15 123 views 评论

[leetcode]题目解析（191015）

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出现次数相同），那么就会出现：

0	1	2	3	4	5	6
A			A			A

然后开始安排B

0	1	2	3	4	5	6	7
A	B		A	B		A	B

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

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

代码实现

typedef pair&lt;char, int&gt; PAIR;
bool cmp(const PAIR &amp;left, const PAIR &amp;right)
{
    return right.second &lt; left.second;
}
    int leastInterval(vector&lt;char&gt;&amp; tasks, int n) {
    if (tasks.empty())
        return 0;
    int lenoft = tasks.size();
    map&lt;char, int&gt;mymap;
    for (int i = 0; i &lt; tasks.size(); i++)
    {
        if (mymap.find(tasks[i]) != mymap.end())//如果在map中找到这个字符，则将字符对应的次数+1
        {
            mymap[tasks[i]]++;
        }
        else//如果没有找到这个字符，则在map中添加这个字符，出现次数设置为1
        {
            char tt = tasks[i];
            mymap.insert(pair&lt;char, int&gt;(tt, 1));
        }
    }
    vector&lt;PAIR&gt; vec(mymap.begin(), mymap.end());
    sort(vec.begin(), vec.end(), cmp);


    int lenofbig = 0;
    for (int i = 0; i &lt; vec.size(); i++)
    {
        if (vec[i].second == vec[0].second)
            ++lenofbig;
        else
            break;
    }
    int houxuan = (n + 1) * (vec[0].second - 1) + lenofbig;
    return ((houxuan &gt; lenoft) ? houxuan: lenoft);

}

typedef pair<char, int> PAIR;

bool cmp(const PAIR &left, const PAIR &right)

{

return right.second < left.second;

}

int leastInterval(vector<char>& tasks, int n) {

if (tasks.empty())

return 0;

int lenoft = tasks.size();

map<char, int>mymap;

for (int i = 0; i < tasks.size(); i++)

{

if (mymap.find(tasks[i]) != mymap.end())//如果在map中找到这个字符，则将字符对应的次数+1

{

mymap[tasks[i]]++;

}

else//如果没有找到这个字符，则在map中添加这个字符，出现次数设置为1

{

char tt = tasks[i];

mymap.insert(pair<char, int>(tt, 1));

}

vector<PAIR> vec(mymap.begin(), mymap.end());

sort(vec.begin(), vec.end(), cmp);

int lenofbig = 0;

for (int i = 0; i < vec.size(); i++)

{

if (vec[i].second == vec[0].second)

++lenofbig;

else

break;

}

int houxuan = (n + 1) * (vec[0].second - 1) + lenofbig;

return ((houxuan > lenoft) ? houxuan: lenoft);

}

Leetcode 617：合并二叉树

题目描述

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

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

题目思想

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

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

代码实现

    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1==nullptr)
            return t2;
        if(t2==nullptr)
            return t1;
        t1-&gt;val+=t2-&gt;val;
        t1-&gt;left=mergeTrees(t1-&gt;left,t2-&gt;left);
        t1-&gt;right=mergeTrees(t1-&gt;right,t2-&gt;right);
        return t1;
    }