算法训练营 - 学习笔记 - 第十周

杂想

刚参加完算法训练营的期末考试，很多知识都不是很了解，有的一知半解，有的迷迷糊糊（像算法题就直接查题解了）。。。回顾这次算法训练营，自己没有很好的践行“五毒神掌”、三分视频、七分练习。算法真的是学了就忘。有时候真的是需要在工作、家庭、生活中寻找一个平衡点。

期末考试遇到下面几个有意思的选择题，对于视频全部看完的同学来说，基本上是送分题。

划重点

Serendipity

意外的新发现。正所谓但行好事，默认前程。技不压身，当你用到的时候，好像你所有的努力都是在为这一刻准备。

Commencement

是毕业，也是开始。

第 20 课 字符串算法

字符串基础知识和引申题目

1. Immutable(Java, C#, JavaScript)

2. 创建之后就不能修改，如果修改，就会生成一个新的对象

3. Mutable(C, C++)

4. 创建后可以修改内存

字符串的比较

1. Java: == vs .equals

实战例题

1. 找第一个不重复的字符，并返回它的索引 - 字符串中的第一个唯一字符

2. 字符串转换整数 Atoi

3. 字符串数组的最长公共前缀

4. 左对齐排列，相等则存储字符，如果不相等，输出之前的

5. Trie Tree 字典树

6. 反转字符串 I, II

7. 反转单词

8. Split, Reverse, Join

9. 异位词问题

10. 回文串问题 Palindrome

高级字符串算法

比较难的：字符串+DP

例题

1. 给定两个单词 word1 and word2, 计算出 word1 转换成 word2 所使用的最小操作数

2. 使用二维数组定义状态

3. dp[i][j] 代表 word1 到 i 位置转换到 word2 的 j 位置需要的最少步数

4. 最长公共子序列

5. 二维数组

6. 最长回文子串

7. 暴力 O(n^3)

8. 枚举中心, 中间向两边扩张法 O(n^2)，奇数，可以在一个元素上，偶数：在两个元素中间

9. 动态规划 DP

10. P(i,j) = P(i+1, j-1) && S[i] == S[j])

11. 正则表达式匹配

12. 处理通配符 .*

字符串匹配算法

1. 暴力法（brute force), O(M*N)

2. Rabin-Karp 算法

3. 使用哈希值进行加速

4. KMP 算法

5. Boyer-Moore 算法

6. Sunday 算法

期末串讲

数据结构

一维

• 基础：数组 array(string), 链表 linked list

• 高级：栈 stack, 队列 queue, 双端队列 deque, 集合 set, 映射 map(hash or map). etc

二维

• 基础：树 tree, 图 graph

• 高级：二叉搜索树 binary search tree(red-black tree, AVL), 堆 heap, 并查集 disjoint set, 字典树 Trie, etc

特殊：

• 位运算 Bitwise, 布隆过滤器 BloomFilter

• LRU Cache

时间复杂度

算法

化繁为简的思想

1. 人肉递归低效、很累

2. 找到最近最简方法，将其拆分成可重复解决的问题

3. 数学归纳法思维

4. 本质：寻找重复性 -> 计算机指令集

学习要点

• 基本功是区别业余和职业选手的根本。深厚的工地来自于——过遍数

• 最大的误区：只做一遍

• 五毒神掌

• 刻意练习 - 练习缺陷弱点的地方、不舒服、枯燥

• 反馈 - 看题解、看国际版的高票回答

经典习题

五毒神掌

第一遍：不要死磕，要看代码学习（一定要看国际版的高票回答）

第二遍：自己写

第三遍：24 小时后

第四遍：一周后

第五遍：面试前

面试技巧（切题 4 件套）