小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. Leetcode
  6. 正文

[leetcode]题目解析(191015)

2019年10月15日 857点热度 0人点赞 0条评论

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<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)思想是一样的。我们可以想都把所有的数据加到第一个二叉树上。类似于那个题目,有这样几个情况:

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

代码实现

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

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

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode
最后更新:2019年10月15日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
2010 S.V Beijing Travel 2:最懒的一天 2010 S.V Beijing Travel -1:北京之行前一天 《鸟哥的Linux私房菜》(基础篇)笔记整理(第6章)Part.2 『超决战!奥特英雄传说』新版官方网站正式启用! 安装IIS报错(0X80240022)的问题解决方案 Python chapter 7 learning notes
标签聚合
Python 鸟哥的linux私房菜 生活 linux 学习 算法 leetcode python学习 高中 Java
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号