如何学好算法与数据结构

-- 主讲人： 九章算法 Mark Chen

算法为什么离不开数据结构

• 算法是解决问题的一系列操作集合
• 数据结构能使得这些操作更加的高效
• 同样的算法我们可以选择不同的数据结构，会带来不同效率的算法

有哪些需要学习的算法与数据结构

国外主流 IT 企业面试：算法数据结构 + 系统设计
国内主流 IT 企业面试：算法数据结构 + 系统设计 + 操作系统 + 网络 + 数据库 + ...

面试中的算法和数据结构并不是很多，常见的有：

1. Array （如各种 SubArray 问题）
2. LinkedList （各种翻转操作链表问题）
3. Queue
4. Stack
5. Binary Tree
6. .....

学习的广度和深度

1. 广度和深度并重
2. 先广度（即系统化学习），了解数据结构直接的联系
3. 后纵深，深入的挖掘每一种数据结构的应用

数据结构分类

• 线性数据结构 1 VS 1 的关系

  • 数组 & 链表
  • 栈和队列
• 树状数据结构 1 VS N 的关系
• 图数据结构 N VS N 的关系

了解数据结构的特性

1. 数组 Array

   1. 可随机访问，可以访问每一个位置，如 A[i].
   2. 前缀和，Prefix Sum - SubArray 问题的杀手锏.

2. 链表 LinkedList

   1. 翻转链表一系列问题，本质是你是否了解 LinkedList

3. 树结构 Tree

   1. Tree 与 LinkedList 的关系:

      1. LinkedList 本质是一叉树
      2. Tree 本质是 LinkedList 的变种

4. 堆 Heap

   1. 优先队列的一种，能够在 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

刷题的重要性

1. 检验学习的正确性，实践自己所学

2. 量的积累

   • 没有量的积累，再科学的方法也没有卵用！

3. 科学的刷题

   1. 给自己 20-30 分钟的思考时间， Why?

   2. 学会分类与总结， Why? LintCode 题目上有 Tag

      1. http://www.lintcode.com/en/tag/
      2. 按照专题，类别刷题来学习一个知识点
      3. 即使自己能够实现该算法或者数据结构，也要看看他们好的代码。同样的算法和数据结构，不同的人实现出来效率上也会有差别
   3. 笔记，而不是做完 Accepted 后就丢在一边

   4. Bug Free 的重要性

      1. 需要有时间的限制
      2. 需要又提交次数的限制

锻炼程序的正确性

1. 在白纸和白板上写代码

   1. 抄到电脑上看是否可以直接通过
2. 直接在 LintCode or LeetCode 上提交，不做调试

哪里刷题？

OI & ACM 竞赛类：

- POJ，ZOJ，HDU ....

面试：

• LintCode/LeetCode
• 面试不推荐去刷上述 OJ

算法的设计

1. 了解每一个经典算法的使用场景

2. 在这个特定的场景下，把该算法使用熟练，了解其时空复杂度

   1. 排序算法 - sort integer 问题
   2. 回溯法 - subset 和排列问题
   3. 动态规划 - 背包问题

3. 算法的设计，突破口来源于问题本身：

   1. 合并两个有序数组 - 有序是一个性质
   2. 在行列都递增的矩阵中找一个数是否出现过 - 行列递增是一个性质

4. 想一个“笨”办法，从这个方法开始不断优化

   1. 找出由原来的问题的瓶颈，即他为什么“笨”，能否优化
   2. 不能优化，再找另外“笨”的办法
   3. 举例子：从搜索到动态规划

数据结构 - 算法加速的手段

1. 数据结构的原理和每一种基本操作

   1. 并查集

      1. 判断两个元素是否在同一个集合内
      2. 合并两个元素所在的集合

   2. Stack

      1. 满足元素先进后出的性质

2. 算法中的某些操作能否转变成特定的数据结构的基本操作

   1. http://www.lintcode.com/en/problem/connecting-graph-iii/

      1. 题目大意：

         1. 给出一个点的集合，可以合并两个点所在的集合
         2. 查询当前有多少个集合
   2. 查询当前有多少个集合，这个操作并没有出现在并查集的基本操作里面

数据结构 - 算法的辅助工具

问题：http://www.lintcode.com/en/problem/number-of-islands-ii/

经典面试题岛屿问题：

1. 创建一个小岛，相邻的岛屿连接起来，形成一个块
2. 每次会询问，当前有多少块

3. Follow Up: 如果创建岛屿的操作可以撤销？

   1. 跟面试官交流之后发现 —— 撤销是按照创建的顺序撤销的
   2. 先创建后撤销，我们想到了“先进后出”， 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

形成代码模板的好处：

1. 每次写保持统一的格式和风格，减少出错（每写一次 code 不同，出错的概率太高了，面试要求 bug free！）
2. 在该算法模板上形成流式思维

书籍推荐

算法与数据结构相关书籍：

• 没有推荐的书籍

非算法与数据结构相关书籍：

• 《深入理解计算机系统》（如果你愿意坚持看下来的话）