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

[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
学习总结：#200
使用语言：Java

[rocinn]

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

[jianyuewu]

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

[liveForExperience]

#作业提交
学号：018
username：liveForExperience
代码作业：https://github.com/liveForExperience/algorithm/tree/master/Week_04/id_18
学习总结：#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
学习总结：#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

[mcgread]

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

小组里面最拼的同学，完成的很棒，一题五种解法。学习了l

[mcgread]

#作业提交
学号：038
username：liujianbo
代码作业：https://github.com/liujianbo/algorithm/tree/master/Week_04/id_38
学习总结：#223
使用语言：Java

众数的排序取中应该比较好理解的，学习了，赞一个

[mcgread]

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

总结写得很好，每一题都用了多种解法。很赞，学习了

[wangjunting]

#作业提交
学号：019
username：wangjunting
代码作业：https://github.com/wangjunting/algorithm/tree/master/Week_04/id_19
学习总结：#299
使用语言：java

[wangjunting]

#作业提交
学号：008
username：UCSBGauchos
代码作业：https://github.com/UCSBGauchos/algorithm/tree/master/Week_04/id_8
学习总结：#200
使用语言：Java
爬楼梯递归式解法，现在递归用的六六六

[wangjunting]

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

递推解法很不错，赞

[wangjunting]

心得写的挺不错

[wangjunting]

#作业提交
学号：038
username：liujianbo
代码作业：https://github.com/liujianbo/algorithm/tree/master/Week_04/id_38
学习总结：#223
使用语言：Java

众数的排序取中应该比较好理解的，学习了，赞一个

众数的地一种解法学习了，竟然还可以这么简单，两行就搞定。赞

[wangjunting]

#作业提交
学号：038
username：liujianbo
代码作业：https://github.com/liujianbo/algorithm/tree/master/Week_04/id_38
学习总结：#223
使用语言：Java

众数的排序取中应该比较好理解的，学习了，赞一个
N皇后的解法不错

[rocinn]

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

钦佩你的总结

[rocinn]

#作业提交
学号：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}

我并没有修改setting，插件 C# fixformat 默认情况下就是括号不单独一行

[Jerrydreamaker]

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

脑图画的不错啊， 收藏了，回头借鉴下哈。

[Jerrydreamaker]

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

哈哈，总结很棒，惭愧惭愧。

[Jerrydreamaker]

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

斐波拉西用高级递推很棒，表示一直用递归加记忆化，回头试试用它解决更多递推问题。

[Jerrydreamaker]

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

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

收藏 DP 截图 +1 ，有时间慢慢消化。

[Jerrydreamaker]

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

你这个爬楼梯解法，确实不错，。

好认真啊，做了这么多道题，还一道题多种解法，厉害。

总结得很仔细，向你学习。

[confidence93]

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

好多思路

[confidence93]

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

学习了

[confidence93]

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

C#看起来学习曲线好高

[confidence93]

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

厉害

[confidence93]

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

代码挺简洁的

[confidence93]

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

总结非常详细，厉害

厉害厉害

[confidence93]

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

解法真的很棒

[swelily]

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

简单粗暴的解法，我喜欢，哈哈。

代码中用到位运算学习了

[swelily]

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

脑图画的不错啊， 收藏了，回头借鉴下哈。

脑图画的好

[swelily]

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

钦佩你的总结

总结写得不错

[swelily]

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

好多思路

一题多解

[swelily]

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

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

总结写得很详细！

[kaye-liu]

要求

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

注意事项

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

第四周题目

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
使用语言：

#姓名：赵大宝
#班级：前端训练营5期
#小组：1组
#语言：PHP
#作业链接：https://time.geekbang.org
#总结链接：https://time.geekbang.org
#作业&总结链接：https://time.geekbang.org

[kaye-liu]

#学号：G20200337050003
#姓名：赵大宝
#班级：前端训练营5期
#小组：1组
#语言：PHP
#作业链接：https://time.geekbang.org
#总结链接：https://time.geekbang.org
#作业&总结链接：https://time.geekbang.org