1. 框架思维

从整体到细节，从抽象到具体。

不要随便去刷题，效率很低，做完就忘，最好有成体系的知识架构。

数据结构的存储方式：顺序存储，链式存储

数组和链表是基础。

数组：读写方便，增删会触发数据搬移，耗时； 链表：增删方便，随机访问耗时；

刷题顺序

• 数组、链表
• 二叉树：只要涉及递归，都是树的问题
  • 回溯问题都是 N 叉树的后序遍历问题
  • 动态规划的底层也是树的问题

2. 常用数据结构

1. Array（静态、动态数组），String
2. LinkedList（单链表，双链表）
3. Stack
4. Queue，Priority Queue
5. HashMap
6. HashSet（底层跟 HashMap 一样）
7. Tree

数据结构都是基于数组和链表

队列和栈：操作受限的数据结构

图：两种表示方式，邻接表，邻接矩阵

散列表：数组

树：链式存储（常用），顺序存储（堆）

为什么有这么多数据结构？

• 不同的数据结构适合于不同的场景，我们的目标是根据场景选择合适的数据结构来进行高效的增删查改。

为什么要学数据结构和算法？

• 程序员的工具和基本功。

为什么数据结构的课程总是要教人们动手实现数据结构？

• 因为每种程序语言都有原始数据类型（Primitive Type），Primitive Data Type is the foundation of data manipulation.

• Java Primitive data types: byte , short , int , long , float , double , boolean and char.

• 我们手动实现的数据结构，是一种更高级别的封装，方便我们进行数据操作。

• 这跟 Object Oriented Programming 的 Abstraction 理念相关。

• 我们平时都会直接使用现成的 library 所提供的数据结构来完成任务。

• 手动实现数据结构的好处是理解这些数据结构的底层实现细节。

• 当我们需要设计一个数据结构的时候，也需要用到这些基础知识。

简而言之，学会了手动实现数据结构，能让我们更好地理解和使用封装好的库，也能让我们拥有「自己实现新的数据结构」的超能力！

假如现成的库没法提供我们需要的功能，我们就可以做一些扩展。

3. 数据结构的基本操作

数据结构存在的意义就是存储和处理数据，不同的数据结构存在的意义，就是在不同的场景下满足高效的增删查改需求。

增删查改：遍历 + 访问。

• 先找到元素，再修改。
• 先找到位置，再操作。

如何遍历 + 访问？

两种形式：迭代，递归。

• 链表支持两种形式。

各种数据结构的遍历 + 访问无非两种形式：线性的和非线性的。线性就是 for/while 迭代为代表，非线性就是递归为代表。

4. 算法的本质

计算机算法的本质是「穷举」，让计算机穷举所有的可能性。

• 关键是如何穷举（无遗漏），聪明地穷举（无冗余）。

还有些算法是数学的编程实现，不在我们的讨论中（如：机器学习）。

算法工程师做的算法，重点在于数学建模和调参经验，计算机算法的重点是计算机思维，通过抽象、化简实际问题，用合理的数据结构去解决问题。

递归类问题的算法难点在「如何穷举」，最典型的就是动态规划系列问题，动态规划的难点在于找到状态转移方程，后面的优化是常规思路。

非递归算法的难点在于「如何聪明地穷举」，比如贪心、并查集、KMP。

5. 常用算法技巧

链表：双指针，单链表翻转，

数组：双指针（二分搜索，滑动窗口，回文串）教我们如何聪明地穷举，前缀和技巧和差分数组技巧。

二叉树：

• 遍历一遍树得到答案 = 回溯算法核心框架（遍历一遍回溯树拿到答案）
• 分解问题计算出答案 = 动态规划核心框架（把大问题分解成小的子问题，通过子问题的结果反推大问题结果）

学会了二叉树，动归、回溯、分治、BFS 就都学通了。

图论也是二叉树算法的延续。

二叉树是最容易培养框架思维的，而且大部分算法技巧，本质上都是树的遍历问题。