如何学好算法与数据结构

-- 主讲人: 九章算法 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. 在该算法模板上形成流式思维

书籍推荐

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

  • 没有推荐的书籍

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

  • 《深入理解计算机系统》(如果你愿意坚持看下来的话)
Last modification:August 31st, 2019 at 02:13 pm
如果觉得我的文章对你有用,请随意赞赏