##第十周学习总结 #数据结构

一维

• 基础：数组array，链表Linked list
• 高级：栈stack，队列queue，双端队列deque，集合set，映射map（hash or map） #二维
• 基础：树tree，图graph
• 高级：二叉搜索树binary search tree(red-black tree,AVL).堆heap，并查集disjoint set,字典树Trie #特殊
• 位运算 Bitwise，布隆过滤器BloomFilter
• LRU Cache

#时间复杂度

#算法

• if-else,switch->branch
• for,while loop->Iteration
• 递归 Recursion(Divide & Conqure,Backtrace)
• 搜索 Search：深度优先搜索Depth first search，广度优先搜索Breadth first search,A*
• 动态规划 Dynamic Programming
• 二分查找 Binary Search
• 贪心 Greedy
• 数学Math，几何Geometry

#化繁为简的思想

1. 抵制人肉递归
2. 找到最近最简方法，将其拆解为可重复解决的问题
3. 数学归纳法思维

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

#学习要点

• 基本功。深厚的功底来自于过遍数
• 最大的误区：只做一遍
• 五毒神掌
• 刻意练习-练习缺陷弱点的地方、不舒服、枯燥
• 反馈-看题解、看国际版的高票回答

#经典习题 爬楼梯、硬币兑换 括号匹配、括号⽣成、直⽅图最⼤⾯积、滑动窗⼝ ⼆叉树遍历、分层输出树、判断⼆叉排序树 股票买卖、偷房⼦、字符串编辑距离、最⻓上升⼦序列、最⻓公共⼦序列 异位词（判断和归类）、回⽂串（最⼤回⽂串）、regex和通配符匹配 ⾼级数据结构（Trie、BloomFilter、LRU cache、etc）

#五毒神掌

• 第一遍：不要死磕，要看代码学习（一定要看国际版的高票回答）
• 第二遍：自己写
• 第三遍：24小时后
• 第四遍：一周后
• 第五遍：面试前

面试技巧

1. Clarification:明确题目意思、边界、数据规模
2. Possible solution:穷尽所有可能的解法

• compare time/space
• opimal solution

3. Coding:代码简洁、高效性能、美感 https://shimo.im/docs/rHTyt8hcpT6D9Tj8/read
4. Test cases