如何学好算法与数据结构
-- 主讲人: 九章算法 Mark Chen
算法为什么离不开数据结构
- 算法是解决问题的一系列操作集合
- 数据结构能使得这些操作更加的高效
- 同样的算法我们可以选择不同的数据结构,会带来不同效率的算法
有哪些需要学习的算法与数据结构
国外主流 IT 企业面试:算法数据结构 + 系统设计
国内主流 IT 企业面试:算法数据结构 + 系统设计 + 操作系统 + 网络 + 数据库 + ...
面试中的算法和数据结构并不是很多,常见的有:
- Array (如各种 SubArray 问题)
- LinkedList (各种翻转操作链表问题)
- Queue
- Stack
- Binary Tree
- .....
学习的广度和深度
- 广度和深度并重
- 先广度(即系统化学习),了解数据结构直接的联系
- 后纵深,深入的挖掘每一种数据结构的应用
数据结构分类
线性数据结构 1 VS 1 的关系
- 数组 & 链表
- 栈和队列
- 树状数据结构 1 VS N 的关系
- 图数据结构 N VS N 的关系
了解数据结构的特性
- 数组 Array
a. 可随机访问,可以访问每一个位置,如 A[i].
b. 前缀和,Prefix Sum - SubArray 问题的杀手锏. - 链表 LinkedList
a. 翻转链表一系列问题,本质是你是否了解 LinkedList - 树结构 Tree
a. Tree 与 LinkedList 的关系:
i. LinkedList 本质是一叉树
ii. Tree 本质是 LinkedList 的变种 - 堆 Heap
a. 优先队列的一种,能够在 logn 时间复杂度取出一个集合的最小值或者最大值.
class ListNode:
def __init__(self, val):
self.val = val
self.next = None
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
## 本质上等于 self.next1, self.next2 = None, None
刷题的重要性
- 检验学习的正确性,实践自己所学
量的积累
- 没有量的积累,再科学的方法也没有卵用!
科学的刷题
a. 给自己 20-30 分钟的思考时间, Why?b. 学会分类与总结, Why? LintCode 题目上有 Tag
1. http://www.lintcode.com/en/tag/ 2. 按照专题,类别刷题来学习一个知识点 3. 即使自己能够实现该算法或者数据结构,也要看看他们好的代码。同样的算法和数据结构,不同的人实现出来效率上也会有差别
c. 笔记,而不是做完 Accepted 后就丢在一边
d. Bug Free 的重要性
1. 需要有时间的限制 2. 需要又提交次数的限制
锻炼程序的正确性
- 在白纸和白板上写代码
a. 抄到电脑上看是否可以直接通过 - 直接在 LintCode or LeetCode 上提交,不做调试
哪里刷题?
OI & ACM 竞赛类:
- POJ,ZOJ,HDU ....
面试:
- LintCode/LeetCode
- 面试不推荐去刷上述 OJ
算法的设计
- 了解每一个经典算法的使用场景
- 在这个特定的场景下,把该算法使用熟练,了解其时空复杂度
a. 排序算法 - sort integer 问题
b. 回溯法 - subset 和排列问题
c. 动态规划 - 背包问题 - 算法的设计,突破口来源于问题本身:
a. 合并两个有序数组 - 有序是一个性质
b. 在行列都递增的矩阵中找一个数是否出现过 - 行列递增是一个性质 - 想一个“笨”办法,从这个方法开始不断优化
a. 找出由原来的问题的瓶颈,即他为什么“笨”,能否优化
b. 不能优化,再找另外“笨”的办法
c. 举例子:从搜索到动态规划
数据结构 - 算法加速的手段
数据结构的原理和每一种基本操作
a. 并查集1. 判断两个元素是否在同一个集合内 2. 合并两个元素所在的集合
b. Stack
1. 满足元素先进后出的性质
算法中的某些操作能否转变成特定的数据结构的基本操作
a. http://www.lintcode.com/en/problem/connecting-graph-iii/
i. 题目大意: 1. 给出一个点的集合,可以合并两个点所在的集合 2. 查询当前有多少个集合
b. 查询当前有多少个集合,这个操作并没有出现在并查集的基本操作里面
数据结构 - 算法的辅助工具
问题:http://www.lintcode.com/en/problem/number-of-islands-ii/
经典面试题岛屿问题:
- 创建一个小岛,相邻的岛屿连接起来,形成一个块
- 每次会询问,当前有多少块
- Follow Up: 如果创建岛屿的操作可以撤销?
a. 跟面试官交流之后发现 —— 撤销是按照创建的顺序撤销的
b. 先创建后撤销,我们想到了“先进后出”, Stack, 用栈去维护当前的信息即可。
算法与数据结构在工作中的应用
Queue 作为消息队列的应用
Google 的 protocol buffer 实现序列化与反序列
- https://developers.google.com/protocol-buffers/
- 序列化与反序列化数据结构:
- http://www.lintcode.com/en/problem/binary-tree-serialization/
LRU 算法
- 数组与链表的应用
总结 —— 有哪些经典的解题模板
二分法模板
广度优先搜索模板:
http://www.jiuzhang.com/solution/bfs-template
形成代码模板的好处:
- 每次写保持统一的格式和风格,减少出错(每写一次 code 不同,出错的概率太高了,面试要求 bug free!)
- 在该算法模板上形成流式思维
书籍推荐
算法与数据结构相关书籍:
- 没有推荐的书籍
非算法与数据结构相关书籍:
- 《深入理解计算机系统》(如果你愿意坚持看下来的话)