算法训练营（上海站）第四周作业

[GeekUniversity]

要求

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

注意事项

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

第四周题目

Trie树

简单：https://leetcode-cn.com/problems/longest-word-in-dictionary/ 中等：https://leetcode-cn.com/problems/implement-trie-prefix-tree/ 中等：https://leetcode-cn.com/problems/add-and-search-word-data-structure-design/ 困难：https://leetcode-cn.com/problems/word-search-ii/

分治算法

简单：https://leetcode-cn.com/problems/majority-element/ 中等：https://leetcode-cn.com/problems/maximum-subarray/ 中等：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

贪心算法

简单：https://leetcode-cn.com/problems/assign-cookies/ 中等：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

回溯算法

简单：https://leetcode-cn.com/problems/letter-case-permutation/ 中等：https://leetcode-cn.com/problems/subsets/ 中等：https://leetcode-cn.com/problems/permutations/ 中等：https://leetcode-cn.com/problems/combinations/ 困难：https://leetcode-cn.com/problems/n-queens/

动态规划

简单：https://leetcode-cn.com/problems/climbing-stairs/ 中等：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/ 困难：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/ 困难：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/ 简单：https://leetcode.com/problems/house-robber/ 中等：https://leetcode.com/problems/house-robber-ii/ 中等：https://leetcode.com/problems/house-robber-iii/ 中等：https://leetcode.com/problems/unique-paths/ 中等：https://leetcode.com/problems/unique-paths-ii/

作业提交规则

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

作业提交

学号： username： 代码作业：（填写自己仓库下对应的作业链接即可，同时记得给本仓库提交 pull request） 学习总结：发表自己本周的学习感言 issues，并提交链接，issues 标题格式：“【学号后三位-week1】+文章标题”，格式参考：#1 使用语言：

[James-Ren]

作业提交

学号：010 username：James-Ren 代码作业：https://github.com/James-Ren/algorithm/tree/master/Week_04/id_10 学习总结：#197 使用语言：Go

[UCSBGauchos]

作业提交

学号：008 username：UCSBGauchos 代码作业：https://github.com/UCSBGauchos/algorithm/tree/master/Week_04/id_8 学习总结：https://github.com/algorithm002/algorithm/issues/200 使用语言：Java

[rocinn]

作业提交

学号：007 username：Yrp1994 代码作业：https://github.com/Yrp1994/algorithm/tree/master/Week_04/id_7 学习总结：https://github.com/algorithm002/algorithm/issues/249 使用语言：C#

[jianyuewu]

作业提交

学号：041 username：jianywu 代码作业：https://github.com/jianywu/algorithm/tree/master/Week_04/id_41 学习总结：https://github.com/algorithm002/algorithm/issues/203 使用语言：CPP

[liveForExperience]

作业提交

学号：018 username：liveForExperience 代码作业：https://github.com/liveForExperience/algorithm/tree/master/Week_04/id_18 学习总结：https://github.com/algorithm002/algorithm/issues/205 使用语言：Java

[hiveryeah]

作业提交

学号：023 username：Eva 代码作业：https://github.com/hiveryeah/algorithm/tree/master/Week_04/id_23 学习总结：#206 使用语言：Java

[hiveryeah]

作业提交

学号：010 username：James-Ren 代码作业：https://github.com/James-Ren/algorithm/tree/master/Week_04/id_10 学习总结：#197 使用语言：Go

DP截图部分灰常受用，赶脚可以把套路记下来，变成自己的O(1) 解题记忆。

[jianyuewu]

作业提交

学号：010 username：James-Ren 代码作业：https://github.com/James-Ren/algorithm/tree/master/Week_04/id_10 学习总结：#197 使用语言：Go

DP截图部分灰常受用，赶脚可以把套路记下来，变成自己的O(1) 解题记忆。

本以为Majority的Boyer-Moore 投票算法已经够骚了，没想到还有更骚的map解法，赞

[lection]

作业提交

学号：003 username：lection 代码作业：https://github.com/lection/algorithm-1/tree/master/Week_04/id_3 学习总结：https://github.com/algorithm002/algorithm/issues/207 使用语言：Python

[lection]

作业提交

学号：018 username：liveForExperience 代码作业：https://github.com/liveForExperience/algorithm/tree/master/Week_04/id_18 学习总结：#205 使用语言：Java

就等着你的总结了，这么详细的总结，比我自己做题都带劲。以后没有作业了，不知道去哪里看总结了。。。

[HugoWen]

作业提交

学号：006 username：HugoWen 代码作业：https://github.com/HugoWen/algorithm-1/tree/master/Week_04/id_6 学习总结：#209 使用语言：PHP

[HugoWen]

作业提交

学号：018 username：liveForExperience 代码作业：https://github.com/liveForExperience/algorithm/tree/master/Week_04/id_18 学习总结：#205 使用语言：Java

每周都来学习下你的总结~

[HugoWen]

作业提交

学号：010 username：James-Ren 代码作业：https://github.com/James-Ren/algorithm/tree/master/Week_04/id_10 学习总结：#197 使用语言：Go

714题二维数组的dp解法和贪心算法自己做都没有想到，学习了

[HugoWen]

作业提交

学号：008 username：UCSBGauchos 代码作业：https://github.com/UCSBGauchos/algorithm/tree/master/Week_04/id_8 学习总结：#200 使用语言：Java

455题代码好简洁

[HugoWen]

作业提交

学号：041 username：jianywu 代码作业：https://github.com/jianywu/algorithm/tree/master/Week_04/id_41 学习总结：#203 使用语言：CPP

做了好多题目，佩服~

[HugoWen]

作业提交

学号：023 username：Eva 代码作业：https://github.com/hiveryeah/algorithm/tree/master/Week_04/id_23 学习总结：#206 使用语言：Java

78题位运算解法学习了

[jianyuewu]

作业提交

学号：018 username：liveForExperience 代码作业：https://github.com/liveForExperience/algorithm/tree/master/Week_04/id_18 学习总结：#205 使用语言：Java

看了你的代码，去试了爬楼梯的公式解法，真快，数学专业搞计算机绝对有优势。

[jianyuewu]

作业提交

学号：023 username：Eva 代码作业：https://github.com/hiveryeah/algorithm/tree/master/Week_04/id_23 学习总结：#206 使用语言：Java

厉害，学到了combinations的API，还是库里API快。我也去试试C的。

[jianyuewu]

作业提交

学号：003 username：lection 代码作业：https://github.com/lection/algorithm-1/tree/master/Week_04/id_3 学习总结：#207 使用语言：Python

784的非递归解决很厉害

[jianyuewu]

作业提交

学号：018 username：liveForExperience 代码作业：https://github.com/liveForExperience/algorithm/tree/master/Week_04/id_18 学习总结：#205 使用语言：Java

总结非常详细，厉害

[jianyuewu]

作业提交

学号：007 username：Yrp1994 代码作业：https://github.com/Yrp1994/algorithm/tree/master/Week_04/id_7 学习总结：暂无 使用语言：C#

厉害，vscode我配置的format document总是会把大括号放到和if/else不是同一行。。您的很好

[jianyuewu]

作业提交

学号：008 username：UCSBGauchos 代码作业：https://github.com/UCSBGauchos/algorithm/tree/master/Week_04/id_8 学习总结：#200 使用语言：Java

厉害，用map的方式做memo，学到了。

[jianyuewu]

作业提交

学号：007 username：Yrp1994 代码作业：https://github.com/Yrp1994/algorithm/tree/master/Week_04/id_7 学习总结：暂无 使用语言：C#

厉害，vscode我配置的format document总是会把大括号放到和if/else不是同一行。。您的很好 我试着把setting改了下，好了。 { BasedOnStyle: Google, IndentWidth: 4}

[James-Ren]

作业提交

学号：018 username：liveForExperience 代码作业：https://github.com/liveForExperience/algorithm/tree/master/Week_04/id_18 学习总结：#205 使用语言：Java

四周了，每次都保持着这么高的水准，总结的很详细，代码不但有多解法，而且代码写得很美观工整。佩服。

[James-Ren]

作业提交

学号：003 username：lection 代码作业：https://github.com/lection/algorithm-1/tree/master/Week_04/id_3 学习总结：#207 使用语言：Python

784还提供了了非递归的解法。学习了

[James-Ren]

作业提交

学号：008 username：UCSBGauchos 代码作业：https://github.com/UCSBGauchos/algorithm/tree/master/Week_04/id_8 学习总结：#200 使用语言：Java

爬楼梯 dp数组的确只需要记录两个变量即可，前面的变量的确是可以舍弃的，从而进一步优化空间复杂度。学到了

[James-Ren]

作业提交

学号：041 username：jianywu 代码作业：https://github.com/jianywu/algorithm/tree/master/Week_04/id_41 学习总结：#203 使用语言：CPP

爬楼梯虽然简单，但是您竟然用了三种方式来写，看您的代码很工整，虽然没有注释也能看懂逻辑，学习了

[James-Ren]

作业提交

学号：023 username：Eva 代码作业：https://github.com/hiveryeah/algorithm/tree/master/Week_04/id_23 学习总结：#206 使用语言：Java

python的写法骚到我了，的确很简洁，我去学习下这个函数。

[hiveryeah]

作业提交

学号：003 username：lection 代码作业：https://github.com/lection/algorithm-1/tree/master/Week_04/id_3 学习总结：#207 使用语言：Python

看别人的Python解法，也算是压力学Python的一种方法 T__T

[hiveryeah]

liveForExperience

严重同意，偶也是每周必读

[hiveryeah]

作业提交

学号：018 username：liveForExperience 代码作业：https://github.com/liveForExperience/algorithm/tree/master/Week_04/id_18 学习总结：#205 使用语言：Java

总结得特别好

[hiveryeah]

作业提交

学号：006 username：HugoWen 代码作业：https://github.com/HugoWen/algorithm-1/tree/master/Week_04/id_6 学习总结：#209 使用语言：PHP

这种把每一题的思路都写一下，也是一种很好的回顾解题思路的方法。

[XueminZhu]

作业提交

学号：035 username：XueminZhu 代码作业：https://github.com/GitGarden2019/algorithm/tree/master/Week_04/id_35 学习总结：#210 使用语言：JAVA

[AAluoxiang]

作业提交

学号：001 username：AAluoxiang 代码作业：https://github.com/AAluoxiang/algorithm/tree/master/Week_04/id_1 学习总结：#212 使用语言：Java

[XueminZhu]

作业提交

学号：008 username：UCSBGauchos 代码作业：https://github.com/UCSBGauchos/algorithm/tree/master/Week_04/id_8 学习总结：#200 使用语言：Java

看到JAVA语言都会优先点进去

[AAluoxiang]

作业提交

学号：008 username：UCSBGauchos 代码作业：https://github.com/UCSBGauchos/algorithm/tree/master/Week_04/id_8 学习总结：#200 使用语言：Java

哈哈，这位老哥还是这么的优秀，总是提交作业很靠前，对你印象很深刻，给你点赞。 总结的很好，学习了，特别是 递推公式 那一块

[XueminZhu]

作业提交

学号：007 username：Yrp1994 代码作业：https://github.com/Yrp1994/algorithm/tree/master/Week_04/id_7 学习总结：暂无 使用语言：C#

我不是很明白控制顺序怎么弄，就是两个结果的时候，需要取前面的数据怎么弄的

[AAluoxiang]

作业提交

学号：018 username：liveForExperience 代码作业：https://github.com/liveForExperience/algorithm/tree/master/Week_04/id_18 学习总结：#205 使用语言：Java

这也是位提交作业靠前的优秀的老哥，看了总结写的很全很细，很多题目当中都用了多种解法，学习了

[XueminZhu]

010 求众数的map搞法get到了

[AAluoxiang]

作业提交

学号：023 username：Eva 代码作业：https://github.com/hiveryeah/algorithm/tree/master/Week_04/id_23 学习总结：#206 使用语言：Java

看到 Eva 还有使用python解的题目，很棒，学习学习

[XueminZhu]

作业提交

学号：001 username：AAluoxiang 代码作业：https://github.com/AAluoxiang/algorithm/tree/master/Week_04/id_1 学习总结：#212 使用语言：Java

打家劫舍我感觉代码清晰很多，思路虽然是和我一样的，果然是大佬人很话不多的感觉

[AAluoxiang]

作业提交

学号：003 username：lection 代码作业：https://github.com/lection/algorithm-1/tree/master/Week_04/id_3 学习总结：#207 使用语言：Python

很强，看了一下 720 题写了很多解法。第四周确实都有点感觉力不从心，咱们朝着300 题的目标出发，一起加油

[AAluoxiang]

作业提交

学号：006 username：HugoWen 代码作业：https://github.com/HugoWen/algorithm-1/tree/master/Week_04/id_6 学习总结：#209 使用语言：PHP

闻瀚 总结的很细很全，同时还刷了很多题，点赞，学习了

[XueminZhu]

作业提交

学号：041 username：jianywu 代码作业：https://github.com/jianywu/algorithm/tree/master/Week_04/id_41 学习总结：#203 使用语言：CPP

看题目量就先膜拜一下，还一个代码本身也是很简洁清爽，虽然我不熟悉C++，但是看上去感觉也没啥语言障碍

[XueminZhu]

作业提交

学号：023 username：Eva 代码作业：https://github.com/hiveryeah/algorithm/tree/master/Week_04/id_23 学习总结：#206 使用语言：Java

怎么是两道JAVA一道Python的，看来也是多面手

[XueminZhu]

作业提交

学号：003 username：lection 代码作业：https://github.com/lection/algorithm-1/tree/master/Week_04/id_3 学习总结：#207 使用语言：Python

代码的注释里暴露了一股程序员的画风，提交注释完美阐述了你当时的心情

[XueminZhu]

作业提交

学号：010 username：James-Ren 代码作业：https://github.com/James-Ren/algorithm/tree/master/Week_04/id_10 学习总结：#197 使用语言：Go

偷钱问题分治搞法学习了

[xiaoluome]

作业提交

学号：036 username：xiaoluome 代码作业：https://github.com/xiaoluome/algorithm/tree/master/Week_04/id_36 学习总结：#214 使用语言：Python

[xiaoluome]

作业提交

学号：023 username：Eva 代码作业：https://github.com/hiveryeah/algorithm/tree/master/Week_04/id_23 学习总结：#206 使用语言：Java

居然用到位运算，可以，学习了

[xiaoluome]

作业提交

学号：010 username：James-Ren 代码作业：https://github.com/James-Ren/algorithm/tree/master/Week_04/id_10 学习总结：#197 使用语言：Go

DP截图部分灰常受用，赶脚可以把套路记下来，变成自己的O(1) 解题记忆。

本以为Majority的Boyer-Moore 投票算法已经够骚了，没想到还有更骚的map解法，赞

但是这样的话，空间复杂度就增加了把