算法训练营第四周作业

[GeekUniversity]

本周重点学习知识点

Trie树、AC自动机、贪心算法、分治算法、回溯算法、动态规划

要求

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

注意事项

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

第四周题目

Trie树

简单：https://leetcode-cn.com/problems/longest-word-in-dictionary/
中等：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/different-ways-to-add-parentheses/
困难：https://leetcode-cn.com/problems/burst-balloons/

贪心算法

简单：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/ipo/

回溯算法

简单：https://leetcode-cn.com/problems/letter-case-permutation/
中等：https://leetcode-cn.com/problems/add-and-search-word-data-structure-design/
困难：https://leetcode-cn.com/problems/n-queens/

动态规划

简单：https://leetcode-cn.com/problems/min-cost-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-cn.com/problems/edit-distance/

作业提交规则

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

1. 学号 + GitHub Username
2. 作业代码的 GitHub 链接（填写自己仓库下对应的作业链接即可，同时记得给本仓库提交 pull request）
3. 发表自己本周的学习感言 issues，并提交链接，issues 标题格式：“【学号后三位-week4】+文章标题”，格式参考：示例：【000-week1】关于二分查找的一些新的理解 #9

[lovingcodesk]

学号：121 Username：lovingcodesk
第四周作业链接：#636
学习感言：

[AndroidQin]

学号：095 Username：AndroidQin
第四周作业链接：https://github.com/AndroidQin/algorithm/tree/master/Week_04/id_95
学习感言：#642

[Fanlu91]

第四周题目

Trie树

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

分治算法

简单：https://leetcode.com/problems/majority-element/
中等：https://leetcode.com/problems/different-ways-to-add-parentheses/
困难：https://leetcode.com/problems/burst-balloons/

贪心算法

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

回溯算法

简单：https://leetcode.com/problems/letter-case-permutation/
中等：https://leetcode.com/problems/add-and-search-word-data-structure-design/
困难：https://leetcode.com/problems/n-queens/

动态规划

简单：https://leetcode.com/problems/min-cost-climbing-stairs/
中等：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
困难：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
困难：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
困难：https://leetcode.com/problems/edit-distance/

[aiter]

学号：095 Username：AndroidQin
第四周作业链接：https://github.com/AndroidQin/algorithm/tree/master/Week_04/id_95
学习感言：#642

作业提交积极，赞。代码清晰易读

[tidelgl]

学号：064 Username：李路
第四周作业链接：https://github.com/tidelgl/algorithm/tree/week-4/Week_04/id_64
学习感言：#646

[zjg23]

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

[suncen0505]

学号：126 Username：suncen0505
第四周作业链接：https://github.com/suncen0505/algorithm/tree/master/Week_04/id_126
学习感言：#648

[suncen0505]

学号：095 Username：AndroidQin
第四周作业链接：https://github.com/AndroidQin/algorithm/tree/master/Week_04/id_95
学习感言：#642

我也是做了两道简单的题，还是依据老师的套路，用了笨法，再去化简的，感觉老师的套路泰通用了

[suncen0505]

学号：064 Username：李路
第四周作业链接：https://github.com/tidelgl/algorithm/tree/week-4/Week_04/id_64
学习感言：#646

你做了好多题呀，我也喜欢在本上记笔记，不过最近发现本上记录好像找一个知识点有点费劲，哈哈 ，最近在考虑用在线笔记做记录呢

[AndroidQin]

学号：095 Username：AndroidQin
第四周作业链接：https://github.com/AndroidQin/algorithm/tree/master/Week_04/id_95
学习感言：#642

我也是做了两道简单的题，还是依据老师的套路，用了笨法，再去化简的，感觉老师的套路泰通用了

一起加油吧，我这得抓紧跟啊

[suncen0505]

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

我好像还没用过前序遍历、中序遍历和后序遍历，一直在用同一种递归，有时间去优化下代码

[SherryShi0108]

学号：086 Username: SherryShi0108
第四周作业链接：https://github.com/SherryShi0108/algorithm/tree/master/Week_04/id_86
学习感言：#649

[suncen0505]

学号：086 Username: SherryShi0108
第四周作业链接：https://github.com/SherryShi0108/algorithm/tree/master/Week_04/id_86
学习感言：#649

活动结束，但是咱们的学习没有结束，以后学完咱们好好交流

[suncen0505]

学号：095 Username：AndroidQin
第四周作业链接：https://github.com/AndroidQin/algorithm/tree/master/Week_04/id_95
学习感言：#642

我也得再重新看一遍，到时候学完咱们再总结，一起交流

[ericyang89]

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

[HongChao6]

学号：131 Username: HongChao6
第四周作业链接：https://github.com/HongChao6/algorithm/tree/master/Week_04/id_131
学习感言：#651
编程语言：C++

[HongChao6]

学号：086 Username: SherryShi0108
第四周作业链接：https://github.com/SherryShi0108/algorithm/tree/master/Week_04/id_86
学习感言：#649

活动结束，但是咱们的学习没有结束，以后学完咱们好好交流

以后咱们就在这个github上建分支呗，然后有问题在 issue 上提交，每次的leetcode题也可提交

[HongChao6]

学号：095 Username：AndroidQin
第四周作业链接：https://github.com/AndroidQin/algorithm/tree/master/Week_04/id_95
学习感言：#642

嗯，一起努力吧

[HongChao6]

学号：121 Username：lovingcodesk
第四周作业链接：#636
学习感言：

我跟你实现的方法一样，不过我是用C++，看你 JAVA 代码正好熟悉一下不同语言

[HongChao6]

学号：095 Username：AndroidQin
第四周作业链接：https://github.com/AndroidQin/algorithm/tree/master/Week_04/id_95
学习感言：#642

感觉784可以 先将字母处理成数字，然后用 hash 实现

[HongChao6]

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

动态规划一般可以用填表来实现，还是做题少，不大熟练

[FollowMyHeart]

1. 学号：033 Username:FollowMyHeart
   2.第四周作业链接： https://github.com/FollowMyHeart/algorithm/tree/master/Week_04/id_33
2. 学习感言：#653

[FollowMyHeart]

学号：064 Username：李路
第四周作业链接：https://github.com/tidelgl/algorithm/tree/week-4/Week_04/id_64
学习感言：#646

你做了好多题呀，我也喜欢在本上记笔记，不过最近发现本上记录好像找一个知识点有点费劲，哈哈 ，最近在考虑用在线笔记做记录呢

嗯，记在在线笔记上能够笔记好的查阅以前的记录！

[salanhess]

学号：040 Username: salanhess
第四周作业链接：https://github.com/salanhess/algorithm/tree/master/Week_04/id_40
学习感言：#655
编程语言：golang

[otkinlife]

学号：061 Username：[email protected](贾凯超)
第四周作业链接：https://github.com/otkinlife/algorithm/tree/master/Week_04/id_61
学习感言：#656

[aiter]

学号：014 Username：aiter
第四周作业链接 java：https://github.com/aiter/algorithm/tree/master/Week_04/id_14
学习感言： #657

[aiter]

学号：061 Username：[email protected](贾凯超)
第四周作业链接：https://github.com/otkinlife/algorithm/tree/master/Week_04/id_61
学习感言：#656

764 写得真好，这题我花了不少时间

[AHaoPang]

学号：009 用户名：AHaoPang
第三周作业链接：https://github.com/AHaoPang/algorithm/tree/master/Week_04/id_9
学习感言：#658

[yxs354]

学号：044 Username: yxs354
第四周作业链接：https://github.com/yxs354/algorithm/tree/master/Week_04/id_44
学习感言：#662

[shironghui0593]

学号：065 Username: shironghui0593
第四周作业链接：https://github.com/shironghui0593/algorithm/tree/master/Week_04/id_65
学习感言：#761
编程语言：java

[wahaha2019]

学号: 063 (9组)
GitHub Username: wahaha2019
语言: Java
代码链接: https://github.com/wahaha2019/algorithm/tree/master/Week_04/id_63
学习感言: #762

[bin-albin]

学号：100 Username：bin_albin
第四周作业链接：https://github.com/bin-albin/algorithm/tree/master/Week_04/id_100
学习感言：#764

[Hermancg]

学号：014 Username：aiter
第四周作业链接 java：https://github.com/aiter/algorithm/tree/master/Week_04/id_14
学习感言： #657

做题心得很是认同

[hfcc8685]

学号：71 Username：hfcc8685
第四周作业链接：https://github.com/hfcc8685/algorithm/tree/master/Week_04/id_71
学习感言: #765

[Hermancg]

学号：061 Username：[email protected](贾凯超)
第四周作业链接：https://github.com/otkinlife/algorithm/tree/master/Week_04/id_61
学习感言：#656

学习了

[kk5171]

学号：119 Username：kk5171
第四周作业链接：https://github.com/kk5171/algorithm/tree/master/Week_04/id_119
学习感言： #767

[cwbcheng]

学号：002 Username：cwbcheng
第四周作业链接：https://github.com/cwbcheng/algorithm/tree/master/Week_04/id_2
学习感言：#768

[ma451152002]

学号：058 Username：maguangjun(马光君)
第四周作业链接：https://github.com/AndroidQin/algorithm/tree/master/Week_04/id_58
学习感言：#769

[taolei0108]

学号：054 Username：taolei0108
第四周作业链接：https://github.com/taolei0108/algorithm/tree/master/Week_04/id_54
学习感言：#773

[mikejicken]

学号：041 username：mikejacken
作业链接：https://github.com/mikejicken/algorithm/tree/master/Week_04/id_41
学习感言： #771

[tommy1989]

学号：075 Username：tommy1989
第四周作业链接：https://github.com/tommy1989/algorithm/tree/master/Week_04/id_75
学习感言： #774
编程语言:java

[yulongz]

学号：067 Username：yulongz
第四周作业链接：https://github.com/yulongz/algorithm/tree/master/Week_04/id_67
学习感言： #704

[Uriah6140]

学号：008 Username：Uriah6140
第四周作业链接：https://github.com/Uriah6140/algorithm/blob/id_08_homework/Week_04/id_8/LeetCode_169_8.java
https://github.com/Uriah6140/algorithm/blob/id_08_homework/Week_04/id_8/LeetCode_720_8.java
学习感言：

[dreakzss]

学号：139 Username：dreakzss
第四周作业链接：
https://github.com/dreakzss/algorithm/tree/master/Week_04/id_139
感想：
#777

[1005419213zxf]

学号：115 Username：1005419213zxf
第四周作业链接：https://github.com/1005419213zxf/algorithm/tree/master/Week_04/id_115
学习感言：#782

[SherryShi0108]

学号：086 Username: SherryShi0108
第四周作业链接：https://github.com/SherryShi0108/algorithm/tree/master/Week_04/id_86
学习感言：#784

[wwb4694376]

学号：132 Username: wwb4694376
第四周作业链接：https://github.com/wwb4694376/algorithm/tree/master/Week_04/id_132
学习感言：#792

[IMC666]

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

[wangxu0]

学号：134 Username：wxisme
第四周作业链接：https://github.com/wxisme/algorithm/tree/master/Week_04/id_134
学习总结： #799

[wangfanstar]

学号057
wangfanstar
作业：https://github.com/wangfanstar/algorithm/tree/057-wangfan/Week_04/id_57
总结：#814

[myrichhub]

学号：028 Username：myrichhub
第四周作业链接：https://github.com/myrichhub/algorithm/tree/master/Week_04/id_28
总结：#820

[okbengii]

学号：081 Username：abinbao
第四周作业链接：https://github.com/abinbao/algorithm-1/tree/master/Week_04/id_81
总结：#824

[songsmith]

学号：137 Username：songsmith
第四周作业链接：https://github.com/songsmith/algorithm/tree/master/Week_04/id_137
学习感言： #830

[flowbywind]

学号：104 username：flowbwyind
第四周作业链接：https://github.com/flowbywind/algorithm/tree/master/Week_04/id_104
学习感言：#869

[wcvolcano]

学号: 047 username: wcvolcano
第四周作业: https://github.com/wcvolcano/algorithm/tree/master/Week_04/id_47
学习感言: #888

[oxcz]

学号: 135 username:oxcz
第四周作业: https://github.com/oxcz/algorithm/tree/master/Week_04/id_135
学习感言: #898

[liutong-cnu]

学号: 144 username:liutong_cnu
第四周作业: https://github.com/liutong-cnu/algorithm/blob/master/Week_04/id_144
学习感言：#923

[luckypeak]

学号: 124 username:luckypeak
第四周作业: https://github.com/luckypeak/algorithm/tree/master/Week_04/id_124
学习感言: #911

[lglove]

学号：024 username:lglove(李戈）
https://github.com/lglove/algorithm/tree/master/Week_04/id_24
学习感言：#918