算法训练营第三周作业

[GeekUniversity]

本周重点学习知识点

递归树、堆和排序、图、深度和广度优先搜索、字符串匹配

要求

1. 每周至少完成给定题目中的两道算法题
2. 围绕每周重点学习的算法知识点，撰写一篇有观点和思考的技术文章（字数不限）

注意事项

1. 下面列出的题目中，按照知识点进行了简单分类，但并不意味着使用相应的数据结构或算法一定是解决该题目的最优解，这样分类只是为了方便大家有针对性的练习；
2. 有的题目可能需要结合多个算法或数据结构进行求解。

第三周题目

图

简单：https://leetcode-cn.com/problems/find-the-town-judge/ 中等：https://leetcode-cn.com/problems/course-schedule-ii 困难：https://leetcode-cn.com/problems/minimize-malware-spread-ii/

堆和排序

简单：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/ 中等：https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/ 困难：https://leetcode-cn.com/problems/find-median-from-data-stream/

DFS

简单：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/ 中等：https://leetcode-cn.com/problems/number-of-islands/ 中等：https://leetcode-cn.com/problems/find-eventual-safe-states/ 困难：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/ 困难：https://leetcode-cn.com/problems/making-a-large-island/

BFS

简单：https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/ 中等：https://leetcode-cn.com/problems/minesweeper/ 中等：https://leetcode-cn.com/problems/minimum-height-trees/ 困难：https://leetcode-cn.com/problems/bus-routes/

作业提交规则

1. 在提交作业之前，请先阅读这里的 README 文档：https://github.com/algorithm001/algorithm/blob/master/README.md
2. 然后在此 Issues 下按照如下格式回复:

1. 学号 + GitHub Username
2. 作业代码的 GitHub 链接（填写自己仓库下对应的作业链接即可，同时记得给本仓库提交 pull request）
3. 发表自己本周的学习感言 issues，并提交链接，issues 标题格式：“【学号后三位-week2】+文章标题”，格式参考：https://github.com/algorithm001/algorithm/issues/9

[hapiman]

学号：038 Username：jianghaoyuan2007 第三周作业链接：https://github.com/jianghaoyuan2007/algorithm/tree/master/Week_03/id_38 学习感言： #531

对做过的题目都做好总结,值得学习;

[hapiman]

学号：028 Username：myrichhub 第三周作业链接：https://github.com/myrichhub/algorithm/tree/master/Week_03/id_28 学习感言： #479

997写的好简洁，学习了

学号：028 Username：myrichhub 第三周作业链接：https://github.com/myrichhub/algorithm/tree/master/Week_03/id_28 学习感言： #479

997写的好简洁，学习了

确实,简洁

[otkinlife]

学号：64 Username：李路 第三周作业链接：https://github.com/tidelgl/algorithm/tree/week-3/Week_03/id_64 学习感言： #503

js里 let关键字是指整型吗

[otkinlife]

学号：024 GitHub UserName：lglove 第三周作业链接：https://github.com/lglove/algorithm/tree/master/Week_03/id_24 学习感言：#525

感觉Ruby读起来果然还是比较困难啊。手动实现堆很赞

[otkinlife]

学号：99 Username：bitwei 第三周作业链接：https://github.com/bitwei/algorithm/tree/master/Week_03/id_99 学习感言： #506

我也是现去学的priority_queue。如果时间允许想自己动手实现一个

[JYSDeveloper]

学号：103 Username：JYSDeveloper 第三周作业链接：代码 学习感言： 链接

[GradyWong]

学号：069 Username: GradyWong 第三周作业链接：https://github.com/GradyWong/algorithm/tree/master/Week_03/id_69 学习感言：https://github.com/algorithm001/algorithm/issues/547

[ellie88]

学号：094 Username：ellie88 第三周作业链接：https://github.com/ellie88/algorithm/tree/master/Week_03/id_94 学习感言： #548 编程语言：Java

[speng975]

https://github.com/otkinlife/algorithm/tree/master/Week_03/id_61

赞，定义两个数组好理解，不过out[trust[i][0]]++和in[trust[i][0]]++好像可以合并在一个循环里面;

[speng975]

1. 学号：074 Username：isnotnull
2. 第三周作业链接：https://github.com/isnotnull/algorithm/tree/master/Week_03/id_74
3. 学习感言： #491

leetcode_200这题刚好没做，思路清晰，代码简洁，学习了。

[yimeng]

学号：128 Username: yimeng 第三周作业链接：https://github.com/yimeng/algorithm/tree/master/Week_03/id_128 学习感言：#552

[speng975]

学号：128 Username: yimeng 第三周作业链接：https://github.com/yimeng/algorithm/tree/master/Week_03/id_128 学习感言：#552

go语言实现LeetCode_703，学习了。

[speng975]

学号：011 Username：Water-DD 第三周作业链接：https://github.com/Water-DD/algorithm/tree/master/Week_03/id_11 学习感言： #536

LeetCode_703_011源代码格式有点问题，没有后缀。

[speng975]

学号：014 Username:aiter 第三周作业链接：https://github.com/aiter/algorithm/tree/master/Week_03/id_14 学习感言：#537

学习总结写的很赞！

[smz198181]

学号：141 Username：smz198181 第三周作业链接：https://github.com/smz198181/algorithm/tree/master/Week_03/id_141 学习感言：555

[IMC666]

学号：082 Username:IMC666 第三周作业链接：https://github.com/IMC666/algorithm/tree/master/Week_03/id_82 学习感言：#556

[suncen0505]

学号：044 Username：yxs354 第三周作业链接：https://github.com/yxs354/algorithm/tree/master/Week_03/id_44 学习感言： #483 很赞同，图的中等题我竟然两次都没有把全部的case通过，我觉得我现在需要重新温习下老师的课，重新理解下有关图的知识，然后再继续回来做图的中等题。 图的那道简单题，感觉也是用了比较笨的思路去求解的，不过第一次以能解出来为目的，后续再优化

[suncen0505]

学号：023 Username：ericyang89 第三周作业链接：https://github.com/ericyang89/algorithm/tree/master/Week_03/id_23 学习感言： #480 编程语言：JavaScript

刻意练习让大脑形成固化思维，说实话，在真正学习算法之前，我也打开过leetcode，但是打开题目，看了看之后又关掉了，感觉没有思路，即使有思路，也感觉好乱呀，但是真正得上完线下课后，两位老师讲了解题的一般套路，再次打开leetcode，感觉瞬间就有了

[yuanyunxu]

学号：122 Username：yuanyunxu 第三周作业链接：https://github.com/yuanyunxu/algorithm/tree/master/Week_03/id_122 学习感言： https://github.com/algorithm001/algorithm/issues/558

[suncen0505]

学号：99 Username：bitwei 第三周作业链接：https://github.com/bitwei/algorithm/tree/master/Week_03/id_99 学习感言： #506

这次没有做堆的题，你总结的大顶堆，小顶堆，重新提醒了我，递归问题这次做了一道，感觉简单的做起来越来越顺手了

[suncen0505]

学号：087 Username：gebitang 第三周作业链接：https://github.com/gebitang/algorithm/tree/master/Week_03/id_87 学习感言： ##514 语言：java

210题表示目前做的题里最让我头疼的，分两次用了不同思路都没有通过全部case，准备继续学习图相关知识再回来挑战

[zjg23]

学号：027 Username：zjg23 第三周作业链接：https://github.com/zjg23/algorithm/tree/master/Week_03/id_27 学习感言： #559

[suncen0505]

学号：120 Username：zhangtianwang 第三周作业链接：https://github.com/zhangtianwang/algorithm/tree/master/Week_03/id_120 学习感言：#516

210题我没有解出来，你的索引下标对我有点启发，哈哈，一会忙完重新再挑战下210题

[GUOSF]

学号：030 Username:GUOSF 第三周作业链接：https://github.com/GUOSF/algorithm/tree/master/Week_03/id_30 学习感言：https://github.com/algorithm001/algorithm/issues/554

[GUOSF]

学号：088 Username：Hermancg 第三周作业链接：https://github.com/Hermancg/algorithm/tree/master/Week_03/id_88 学习感言： #534

有的地方写的不一样，学习到了

[GUOSF]

学号：014 Username:aiter 第三周作业链接：https://github.com/aiter/algorithm/tree/master/Week_03/id_14 学习感言：#537

每道题都用2中写法，学习到了，总结的很好。

[yuzewang]

学号：136 Username：yuzewang 第三周作业链接：https://github.com/yuzewang/algorithm/tree/master/Week_03/id_136 学习感言：#551

[GUOSF]

学号：027 Username：zjg23 第三周作业链接：https://github.com/zjg23/algorithm/tree/master/Week_03/id_27 学习感言： #559 暴力

[GUOSF]

学号：118（李颜翎） 第三周作业链接：https://github.com/yanlingli3799/algorithm/tree/master/Week_03/id_118 学习感言： #508 题目：207、210、924、928、997（Java）

有几个题没写，没看你的答案。。。，回头我写不出来，在来膜拜

[GUOSF]

学号：136 Username：yuzewang 第三周作业链接：https://github.com/yuzewang/algorithm/tree/master/Week_03/id_136 学习感言：#551

生活实例有意识

[hfcc8685]

学号: 071 UserName: hfcc8685 第三周作业链接: https://github.com/hfcc8685/algorithm/tree/master/Week_03/id_71 学习感言: #562

[MrWang5200]

学号: 085 UserName: MrMuddle 第三周作业链接: https://github.com/MrMuddle/algorithm/tree/master/Week_03/id_85 学习感言: #564

[aiter]

学号：030 Username:GUOSF 第三周作业链接：https://github.com/GUOSF/algorithm/tree/master/Week_03/id_30 学习感言：#554

代码简洁~

[aiter]

学号：102 Username：speng975 第三周作业链接：https://github.com/speng975/algorithm/tree/master/Week_03/id_102 学习感言： #485

顺便学习cpp

[aiter]

学号：118（李颜翎） 第三周作业链接：https://github.com/yanlingli3799/algorithm/tree/master/Week_03/id_118 学习感言： #508 题目：207、210、924、928、997（Java）

我就喜欢review这种注释比代码多的，专写难题666

[aiter]

学号：088 Username：Hermancg 第三周作业链接：https://github.com/Hermancg/algorithm/tree/master/Week_03/id_88 学习感言： #534

Hermancg 把你的图和注释全放上来：）

[aiter]

学号：061 Username: otkinlife(贾凯超) 第三周作业链接：https://github.com/otkinlife/algorithm/tree/master/Week_03/id_61 学习感言：#496

这种循环为啥喜欢来2次？

        //初始化
        for (int i = 0; i < trust.size(); i++) {
            out[trust[i][0]]++;
        }
        for (int i = 0; i < trust.size(); i++) {
            in[trust[i][1]]++;
        }

[zsndev]

学号: 129 UserName: zsndev 第三周作业链接: https://github.com/zsndev/algorithm/tree/master/Week_03/id_129 学习感言: #567 语言：java

[zsndev]

学号：088 Username：Hermancg 第三周作业链接：https://github.com/Hermancg/algorithm/tree/master/Week_03/id_88 学习感言： #534

定时短信的方案，想请教几个问题，用户量大的话，应该有不少时间是相同的吧，那么同一时间会连续poll数据，堆会多次再平衡，如果topK中，这个k维护的比较大的话，会不会比较消耗性能。你的k具体多大是怎么定的呀

[xiangfeifei54]

学号： 077
username: xiangfeifei 第三周作业： id_77 学习感言:#569 语言: java

[zsndev]

学号：136 Username：yuzewang 第三周作业链接：https://github.com/yuzewang/algorithm/tree/master/Week_03/id_136 学习感言：#551

生活中真是在无意识中使用了各种算法啊。快递放货架的问题（快递更是对包裹使用了日期+自增id的编号方式），那他的货架得至少有31个吧

[zsndev]

学号：118（李颜翎） 第三周作业链接：https://github.com/yanlingli3799/algorithm/tree/master/Week_03/id_118 学习感言： #508 题目：207、210、924、928、997（Java）

看了你的作业，现在你是我看过的人最佩服的了。画图画成这样真是太厉害了。想问下，你的928草稿，是怎么导出这个效果的呀，就在纸上画，然后拍照，扫描吗？

[zsndev]

学号：99 Username：bitwei 第三周作业链接：https://github.com/bitwei/algorithm/tree/master/Week_03/id_99 学习感言： #506

直接使用系统库中的priority_queue真的简洁很多，一开始我不知道自己撸了一套

[zsndev]

学号：141 Username：smz198181 第三周作业链接：https://github.com/smz198181/algorithm/tree/master/Week_03/id_141 学习感言：555

从更优的解决问题角度思考，引入额外的数据结构来辅助解题的思路很棒。你提到的通过引入测试条件，比如” len(res) == k”来制造限定解的方式，和 在做链表时的哨兵有异曲同工之妙啊

[oxcz]

学号：135 Username：oxcz 第三周作业链接：https://github.com/oxcz/algorithm/tree/master/Week_03/id_135 学习感言 ：#571

[JackZhangDF]

学号：10 Username：JackZhangDF 第三周作业链接：https://github.com/JackZhangDF/algorithm/tree/master/Week_03/id_10 学习感言 ：#572

[gaoshengnan]

学号：101 username：gaoshengnan（seina） 第三周作业链接：https://github.com/gaoshengnan/algorithm-1/tree/master/Week_03/id_101 学习总结：https://github.com/algorithm001/algorithm/issues/573

[gaoshengnan]

学号： 077 username: xiangfeifei 第三周作业： id_77 学习感言:#569 语言: java

总结的很详细，做的题挺多的，我也得加油！

[gaoshengnan]

学号: 071 UserName: hfcc8685 第三周作业链接: https://github.com/hfcc8685/algorithm/tree/master/Week_03/id_71 学习感言: #562

我也是通过专栏学习到了很多，一起加油

[gaoshengnan]

学号：122 Username：yuanyunxu 第三周作业链接：https://github.com/yuanyunxu/algorithm/tree/master/Week_03/id_122 学习感言： #558

有些我感觉难的题都会，真的很厉害~