【007-week4】算法训练营第四周学习总结 #249

嗯...这周题目都很难，基本都是看了官方解答或国际版中discuss。
720. 词典中最长的单词 Trie树结构，第一次做这个类型的题目，首先按照暴力法自己写了一遍（先排序，后双循环），从执行时间 1216ms 优化到 456ms 。然后就是Trie树结构，第一感觉，构造这个树就好麻烦，代码长好多，不想写。但还是照着国际版解答自己写了一遍，当然结果是更好的，时间复杂度从平方提升到常数级别，执行时间也进一步缩短到 296ms ,当然这是因为使用 C# 的原因，用Java 或 python 或 go 应该是更快的。
分治与贪心算法，倒是相对来说好理解一些，169. 求众数 这道题，虽然 摩尔投票法 很高效，但没几个人能想出来，我觉得最好理解的方法还是，在暴力法的基础上加记忆化，时间复杂复杂度 O(n) 虽然没有分治 O(nlgn) 好，但效果不差。贪心的代码实现其实不难，类似暴力法，但难点是，什么情况下才使用贪心呢，较难判断。
动态规划，70. 爬楼梯 这题做了起码3遍了，每做一遍都有新的收获，第一遍：完全没思路；第二遍：暴力法+记忆化，哎呦，效果很不错，还有就是可以总结出是斐波那契数列；第三遍：嗯，DP方程真是太强了。这也反映出，超哥解题五步的确是很有用。
最后，这是我感觉过的最快的一个月了，每天都是在做题中度过（😂做得很慢，每题都得理解半天），有压力才有动力，收获肯定是有的，或许对别人来说微不足道，但对自己来说，第一次坚持一个月在做一件事，很开心，会坚持下去。题目做的不多，目前也就20来道，最后的考试感觉压力还是比较大的，这周还会继续做题目的，再多记得一些，希望考试能一次过。