算法训练营第二周作业

[GeekUniversity]

本周重点学习知识点

跳表、散列表、哈希算法、二叉树、红黑树

要求

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

注意事项

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

第二周题目

哈希表

简单：https://leetcode-cn.com/problems/valid-anagram/ 中等：https://leetcode-cn.com/problems/top-k-frequent-words 中等：https://leetcode-cn.com/problems/find-duplicate-file-in-system/ 困难：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/ 困难：https://leetcode-cn.com/problems/number-of-atoms/

二叉树

简单：https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/ 中等：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/ 中等：https://leetcode-cn.com/problems/all-nodes-distance-k-in-binary-tree/ 困难：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/ 困难：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

二叉搜索树

简单：https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 中等：https://leetcode-cn.com/problems/range-sum-of-bst/ 中等：https://leetcode-cn.com/problems/contains-duplicate-iii/ 困难：https://leetcode-cn.com/problems/count-of-range-sum/ 困难：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/

作业提交规则

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

[isnotnull]

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

[lglove]

学号：024 Username: lglove(李戈) 第二周作业链接：https://github.com/lglove/algorithm/tree/master/Week_02/id_24 学习总结：#373

[aiter]

学号: 044 UserName : yxs354 第二周作业链接:https://github.com/yxs354/algorithm/tree/master/Week_02/id_44 学习总结: #330

没学过 java ，能说一下使用 PriorityQueue 结构 的用意跟用法么

用PriorityQueue主要还是用来统计完词频后，对单词的排序。主要还是利用优先队列内部使用堆的实现，可以构造大顶堆，top k，就从堆顶取k次。

//优先队列的比较器，先比较词频，相等的话再比较word字符串
PriorityQueue<Map.Entry<String, Integer>> pp = new PriorityQueue<>((x, y) -> {
            if (x.getValue() < y.getValue()) return 1;
            else if (x.getValue() > y.getValue()) return -1;
            else return x.getKey().compareTo(y.getKey());
        });

不知道yxs354的这个实现，在LeetCode上实际的测试耗时如何？第一次遍历，统计词频。第一次遍历，构建大顶堆。取top k时，删除堆顶后，还需要堆化。

[aiter]

学号：084 Username：daodaoshao 第二周作业链接：https://github.com/daodaoshao/algorithm/tree/master/Week_02/id_84 学习总结：#361

• lowestCommonAncestor 这题自己没做，看实现，清晰明了，不过自己实现估计得踩几次坑。
• top k这题，看了几题，统计词频，基本都是hash表。排序就有所不同：优先队列(堆)、集合排序、双向链表 ：）

[aiter]

学号：090 username：xuyunbo 第二周作业链接：https://github.com/algorithm001/algorithm/tree/master/Week_02/id_90 学习感言：#356

LeetCode_267_90.java 这题用queue存比大小的值，用stack记录遍历树时分叉时的回溯点？ 看着就很烧脑，不容易想到这解法，666!

结果对吗？队列操作那里没太看明白

[aiter]

学号：028 username：myrichhub 第二周作业链接：https://github.com/myrichhub/algorithm/tree/master/Week_02/id_28 学习感言：[总结](【028-Week2】学习总结 #369)

map使用getOrDefault方法，优雅，是加分项啊 ：） 学习总结的链接有点问题

[aiter]

学号：082 Username：IMC666 第二周作业链接：https://github.com/IMC666/algorithm/tree/1f6a3c49e18c16cf273a9a90850d8f8228c570a9/Week_01/id_82/%E4%BA%8C%E5%8F%89%E6%A0%91 学习感言：#321

写着267，找了半天没看到题目 :(

[renzhongxing]

学号：098 Username: renzhongxing 第二周作业链接:https://github.com/renzhongxing/algorithm/tree/master/Week_02/id_98 学习感言:#375

[aiter]

学号：042 username：linear063 第二周作业链接：https://github.com/linear063/algorithm/tree/master/Week_02/id_42 学习感想：#344

leecode_671_042.java 为啥使用TreeMap? 统计词频时，利用TreeMap按word先字母顺序排序，然后在sort部分，就只对词频排序？ 哇~~~

[SherryShi0108]

学号：086 username：SherryShi0108 第二周作业链接：https://github.com/SherryShi0108/algorithm/tree/master/Week_02/id_86 学习感言：#295

我这有个疑问，就是为什么要减少return 呢？我倒觉得没必要的时候，直接return ,省去后续的处理，不是更好吗

• 这好像是C语言的遗留问题，没有RAII或其他自动内存管理那么必须要清理每次返回，所以要有尽量少的return。但是针对于C#或其他自动管理内存的语言就可以只看可读性。代码大全上17.1讲在增加可读性上可以使用多个return。

• 但是我的理解是单个return可以便于理解调试，而且如果需要过多return的话那说明这个方法可以重构更小更通用更易理解的方法。

对这个问题没有找到一个固定的标准答案，在Stackoverflow上有讨论，可以参考一下。

[otkinlife]

学号：014 Username: aiter 第二周作业链接(java)：https://github.com/aiter/algorithm/tree/master/Week_02/id_14 学习感言： #318

看了大佬的学习总结，觉得对二叉树的总结非常全面。有很多之前我没有想到过的点

[otkinlife]

学号：028 username：myrichhub 第二周作业链接：https://github.com/myrichhub/algorithm/tree/master/Week_02/id_28 学习感言：[总结](【028-Week2】学习总结 #369)

如果code的注释多一点就更好了。阅读代码的时候能更容易理解一点

[otkinlife]

学号：064 Username：李路 第一周作业链接（JavaScript）：https://github.com/tidelgl/algorithm/tree/week-2/Week_02/id_64 学习感言：#358

是JS本身的特性吗，为什么map要用const关键字呢？

[HongChao6]

了解了，多谢 用 PriorityQueue 实现的确很方便，跟你想的一样，我也怀疑耗时如何

liuhongchao_00@126.com

发件人： aiter 发送时间： 2019-04-28 07:16 收件人： algorithm001/algorithm 抄送： 红桃六; Comment 主题： Re: [algorithm001/algorithm] 算法训练营第二周作业 (#52) 学号: 044 UserName : yxs354 第二周作业链接:https://github.com/yxs354/algorithm/tree/master/Week_02/id_44 学习总结: #330 没学过 java ，能说一下使用 PriorityQueue 结构 的用意跟用法么 用PriorityQueue主要还是用来统计完词频后，对单词的排序。主要还是利用优先队列内部使用堆的实现，可以构造大顶堆，top k，就从堆顶取k次。 //优先队列的比较器，先比较词频，相等的话再比较word字符串 PriorityQueue<Map.Entry<String, Integer>> pp = new PriorityQueue<>((x, y) -> { if (x.getValue() < y.getValue()) return 1; else if (x.getValue() > y.getValue()) return -1; else return x.getKey().compareTo(y.getKey()); });

不知道yxs354的这个实现，在LeetCode上实际的测试耗时如何？第一次遍历，统计词频。第一次遍历，构建大顶堆。取top k时，删除堆顶后，还需要堆化。 — You are receiving this because you commented. Reply to this email directly, view it on GitHub, or mute the thread.

[otkinlife]

学号：062 username：shimmer236 第二周作业链接：https://github.com/shimmer236/algorithm/tree/qq/Week_02/id_62 学习感言：#304

总结的很细致，到位。之前对于闲散列和开散列并没有概念。学习一下

[HongChao6]

的确，不限制 return 的使用 但，一定要保证代码的可读性高，必须让别人去读代码 比让别人去理解代码 更优雅

liuhongchao_00@126.com

发件人： SherryShi0108 发送时间： 2019-04-28 09:11 收件人： algorithm001/algorithm 抄送： 红桃六; Comment 主题： Re: [algorithm001/algorithm] 算法训练营第二周作业 (#52) 学号：086 username：SherryShi0108 第二周作业链接：https://github.com/SherryShi0108/algorithm/tree/master/Week_02/id_86 学习感言：#295 我这有个疑问，就是为什么要减少return 呢？我倒觉得没必要的时候，直接return ,省去后续的处理，不是更好吗 这好像是C语言的遗留问题，没有RAII或其他自动内存管理那么必须要清理每次返回，所以要有尽量少的return。但是针对于C#或其他自动管理内存的语言就可以只看可读性。代码大全上17.1讲在增加可读性上可以使用多个return。 但是我的理解是单个return可以便于理解调试，而且如果需要过多return的话那说明这个方法可以重构更小更通用更易理解的方法。 对这个问题没有找到一个固定的标准答案，在Stackoverflow上有讨论，可以参考一下。 — You are receiving this because you commented. Reply to this email directly, view it on GitHub, or mute the thread.

[HongChao6]

赞同

如何写出一个优雅的、具有可读性的代码 是我们所要考虑的事情

让写代码变成一个艺术工作

liuhongchao_00@126.com

发件人： aiter 发送时间： 2019-04-28 07:47 收件人： algorithm001/algorithm 抄送： 红桃六; Comment 主题： Re: [algorithm001/algorithm] 算法训练营第二周作业 (#52) 学号：028 username：myrichhub 第二周作业链接：https://github.com/myrichhub/algorithm/tree/master/Week_02/id_28 学习感言：[总结](【028-Week2】学习总结 #369) map使用getOrDefault方法，优雅，是加分项啊 ：） 学习总结的链接有点问题 — You are receiving this because you commented. Reply to this email directly, view it on GitHub, or mute the thread.

[otkinlife]

学号：013 username : fishLite 第二周作业链接：https://github.com/fishLite/algorithm/tree/master/Week_02/id_13 学习感言：#340

242题中，有两个map比较的库函数，在算时间复杂度的时候应该把他的算上吧。我不是做java的，对equals这个方法的实现不太了解。但感觉不是O(1).

[otkinlife]

学号：013 username : fishLite 第二周作业链接：https://github.com/fishLite/algorithm/tree/master/Week_02/id_13 学习感言：#340

242题中，有两个map比较的库函数，在算时间复杂度的时候应该把他的算上吧。我不是做java的，对equals这个方法的实现不太了解。但感觉不是O(1).

[oxcz]

学号：135 username : oxcz 第二周作业链接：https://github.com/oxcz/algorithm/tree/master/Week_02/id_135 学习感言：#339

[yulongz]

学号: 067 UserName:yulongz 第一周作业链接：https://github.com/yulongz/algorithm/tree/master/Week_02/id_67 学习感言 #376 语言: Java

[Lugyedo]

学号：036 UserName：Lugyedo 第二周作业链接：https://github.com/Lugyedo/algorithm/tree/master/Week_02/id_36 学习感言：https://github.com/algorithm001/algorithm/issues/379

[Fanlu91]

学号：026 UserName：Fanlu91 第二周作业链接：https://github.com/Fanlu91/algorithm/tree/master/Week_02/id_26 学习感言：https://github.com/algorithm001/algorithm/issues/380

[hapiman]

学号：117
Username：hapiman(彭建) 第二周作业链接：https://github.com/hapiman/algorithm/tree/master/Week_02/id_117 学习感言：https://github.com/algorithm001/algorithm/issues/384 编程语言: Golang

[GUOSF]

学号: 030 UserName:GUOSF 第一周作业链接：https://github.com/GUOSF/algorithm/tree/master/Week_02/id_30 学习感言 https://github.com/algorithm001/algorithm/issues/386 语言: Java

[zhaowende]

学号: 123 UserName:zhaowende 第一周作业链接：https://github.com/zhaowende/algorithm/tree/master/Week_02/id_123 学习感言 #387

[smz198181]

学号：141 username: smz198181 第二周作业链接：https://github.com/smz198181/algorithm/tree/master/Week_02/id_141 学习感言：#388

[zjg23]

学号：027 username：zjg23 第二周作业链接：https://github.com/zjg23/algorithm/tree/master/Week_02/id_27 学习感言： #391

[SeanMrLi]

学号：108 UserName：SeanMrLi 第二周作业链接：https://github.com/SeanMrLi/algorithm/tree/master/Week_02/id_108 学习感言：https://github.com/algorithm001/algorithm/issues/392

[cwbcheng]

学号：002 username：cwbcheng 第二周作业链接：https://github.com/cwbcheng/algorithm/tree/master/Week_02/id_2 学习感言： #393

[plin005]

学号: 039, GitHub Username: plin005(林媛媛) 第二周作业链接：https://github.com/plin005/algorithm/tree/master/Week_02/id_39 学习感言: 【039-week2】学习总结”，#394

[hapiman]

学号：061 username：otkinlife(贾凯超) 第二周作业链接：https://github.com/otkinlife/algorithm/tree/master/Week_02/id_61 学习感言：#307

783: 递归求解,然后再用两层循环应该是时间复杂度最大,可否直接找到最小值及最大值

[hapiman]

学号：135 username : oxcz 第二周作业链接：https://github.com/oxcz/algorithm/tree/master/Week_02/id_135 学习感言：#339

242##: 兄台,直接用库函数实现,太直接了吧.

[alxjerr]

学号：097 username: alxjerr 第二周作业连接：https://github.com/alxjerr/algorithm/tree/master/Week_02/id_97 学习感言：https://github.com/algorithm001/algorithm/issues/400

[hapiman]

学号: 039, GitHub Username: plin005(林媛媛) 第二周作业链接：https://github.com/plin005/algorithm/tree/master/Week_02/id_39 学习感言: 【039-week2】学习总结”，#394

671##: 左右节点对称递归代码逻辑会更加清晰

[HongChao6]

学号：131 username：HongChao6 第二周作业链接：https://github.com/HongChao6/algorithm/tree/master/Week_02/id_131 学习感言：#310

[ajun-victor]

学号：016 username：ajun 第二周作业链接：https://github.com/ajun-victor/algorithm/tree/master/Week_02/id_16 学习感言：#null 代码语言：Java

[hapiman]

学号: 123 UserName:zhaowende 第一周作业链接：https://github.com/zhaowende/algorithm/tree/master/Week_02/id_123 学习感言 #387

783: 测试case学习了

[zsndev]

学号：129 username：zsndev 第二周作业链接：https://github.com/zsndev/algorithm/tree/master/Week_02/id_129 学习感言：#406 代码语言：Java

[bin-albin]

学号: 100 UserName:bin_albin 第一周作业链接：https://github.com/bin-albin/algorithm/tree/master/Week_02/id_100 学习感言 #407

[zsndev]

学号：036 UserName：Lugyedo 第二周作业链接：https://github.com/Lugyedo/algorithm/tree/master/Week_02/id_36 学习感言：#379

242题最后的那个遍历可以省掉，在循环参数t的时候，其实只要发现值小于等于0就可以return false了

[gebitang]

学号：087 username：gebitang 第二周作业链接：https://github.com/gebitang/algorithm/tree/master/Week_02/id_87 学习感言：#409 代码语言：Java

[zsndev]

学号：135 username : oxcz 第二周作业链接：https://github.com/oxcz/algorithm/tree/master/Week_02/id_135 学习感言：#339

692题使用优先级队列排序的时候，把所有数据一次性都加进去了，空间复杂度一下多了o(n)，可以只维护大小为k的优先级队列

[speng975]

学号：102 username：speng975 第二周作业链接：https://github.com/speng975/algorithm/tree/master/Week_02/id_102 学习感言：#408

[zsndev]

学号：087 username：gebitang 第二周作业链接：https://github.com/gebitang/algorithm/tree/master/Week_02/id_87 学习感言：#409 代码语言：Java

692题， map有个叫getOrDefault的方法可以简化一开始扫描的代码，不用再写额外的if else了。 另外取topK那块儿，在大家普遍用系统库的情况下，你从头撸了个链表也是挺给力的

[MrWang5200]

学号：085 username : MrMuddle 第二周作业链接：https://github.com/MrMuddle/algorithm/tree/master/Week_02/id_85 学习感言：#411

[bugcodes]

学号：049 Username：bugcodes 第二周作业链接：https://github.com/bugcodes/algorithm/tree/master/Week_02/id_49 学习感言： #416

[gebitang]

学号: 044 UserName : yxs354 第二周作业链接:https://github.com/yxs354/algorithm/tree/master/Week_02/id_44 学习总结: #330

没学过 java ，能说一下使用 PriorityQueue 结构 的用意跟用法么

学习一下。 这个PriorityQueue类库还没用过呢。

[gaoshengnan]

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

[zsndev]

学号：102 username：speng975 第二周作业链接：https://github.com/algorithm001/algorithm/tree/master/Week_02/id_102 学习感言：#408

671题，这个题中的一定是大于等于父节点的，那解答里寻找比secondMinVal小的值，在第一次赋值后，今后就没用了吧，感觉这个条件是不是可以省掉，在树的两侧第一次给secondMinVal赋值后，不再赋值就好了