# 学习算法和刷题的框架思维

首先这里讲的都是普通的数据结构，前端面试普遍算法难度较低，所以只介绍常规问题的解决办法。

从整体到细节，自顶向下，从抽象到具体的框架思维是通用的，不只是学习数据结构和算法，学习其它任何知识都是高效的。

# 数据机构的存储方式

数据结构的存储方式只有两种：

数组（顺序存储）
链表（链式存储）

这句话该怎么理解，不是还有散列表、栈、队列、堆、树、图等等各种数据结构吗？

我们分析问题一定要有递归的思想，自顶向下，从抽象到具体。你上来就列出这么多，那些都属于「上层建筑」，而数组和链表才是「结构基础」。因为那些多样化的数据结构，归根到底都是在链表或者数组的基础上进行封装不同的 API。

比如说「队列」、「栈」这两种数据结构既可以用链表也可以用数组实现。用数组实现就要处理扩容缩容问题；用链表实现就没有这个问题，但需要更多的内存空间存储节点指针。

「图」的两种表示方法，邻接表就是链表，邻接矩阵就是二维数组。邻接矩阵判断连通性迅速，并可以进行矩阵运算解决问题，但是如果图比较稀疏的话很耗费空间。邻接表比较节省空间，但是很多操作的效率上肯定比不过邻接矩阵。

「散列表」就是通过散列函数把键映射到一个大数组里。而且对于解决散列冲突的方法，拉链法需要链表特性，操作简单，但需要额外的空间存储指针；线性探查法就需要数组特性，以便连续寻址，不需要指针存储空间，但操作稍微复杂些。

「树」，用数组实现就是「堆」，因为「堆」是一个完全二叉树，用数组存储不需要节点指针，操作也比较简单；用链表实现就是常见的那种「树」，因为不一定是完全二叉树，所以不适合用数组存储。为此，在这种链表「树」结构上，又衍生出各种巧妙的设计，比如二叉搜索树、AVL树、红黑树、区间树、B树等等，以应对不同的问题。

了解Redis数据库的朋友可能知道，Redis提供列表、字符串、集合等等几种常见的数据结构，但是对于每种数据结构，底层的存储方式都至少有两种，以便于根据存储数据的实际情况使用合适的存储方式。

综上，数据结构种类很多，甚至你也可以发明自己的数据结构，但是底层存储无非数组或者链表，二者的优缺点如下：

数组由于是紧凑连续存储，可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正是因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度是 O(n) ；而且你如果想在数组中间进行叉如何删除，每次必须搬移后面的所有数据以保持连续，时间复杂度是 O(n) 。
链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1) 。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的位置，所以不能随机访问；而且由于每个元素必须存储指向前后元素的指针，会消耗更多的存储空间。

# 数据结构的基本操作

对于任何数据结构，其基本操作无非遍历 + 访问，再具体一点就是：增删改查 。

数据结构种类很多，但它们存在的目的是在不同的应用场景下，尽可能高效地增删改查。

如何遍历 + 访问？我们仍然从最高层来看，各种数据结构的遍历 + 访问无非两种形式：线性和非线性。

线性就是 for/while 迭代为代表，非线性就是递归为代表。再具体一步，无非以下几种框架：

数组遍历框架，典型的线性迭代结构：

function traverse(list: number[]): void {
  for(let i = 0; i < list.length; i++) {
    // 迭代访问 list[i]
  }
}

链表遍历框架，兼具迭代和递归结构：

// 基本的单链表节点
interface ListNode {
  value: number
  next: ListNode | null
}

function traverse(node: ListNode): void {
  for(let n = node; n !== null; n = n.next) {
    // 迭代访问
  }
}

function recursive(node: ListNode): void {
  // 递归访问
  node && recursive(node.next)
}

二叉树遍历框架，典型的非线性递归遍历结构：

interface TreeNode {
  value: number
  left: TreeNode | null
  right: TreeNode | null
}

function recursive(node: TreeNode): void {
  // 递归访问
	node?.left && recursive(node.left)
  node?.right && recursive(node.right)
}

你看二叉树的递归遍历方式和链表的递归遍历方式是不是很相似，再看看二叉树结构和单链表结构是不是很相似？

如果再过几条叉，N叉树你会不会遍历？

二叉树遍历框架可以扩展为N叉树遍历框架：

interface TreeNode {
  value: number
  children: TreeNode[]
}

function recursive(node: TreeNode): void {
  if(!node) return
  for(const child of node.children) {
		recursive(child)
  }
}

N叉树的遍历又可以扩展为图的遍历，因为图就是好多N叉树的结合体。你说图如果出现环？这个很好办，用个布尔值来做标记即可。

所谓框架，就是套路。不管增删改查，这些代码都是永远无法脱离的结构，你可以把这个结构作为大纲，根据具体问题在框架上添加代码即可。

# 算法刷题指南

首先要明确的是，数据结构是工具，算法是通过合适的工具解决特定问题的方法。 也就是说，学习算法之前，最起码得了解哪些常见的数据结构，了解他们的特性和缺陷。

那么该如何在 LeetCode 刷题呢？最通俗的讲就是按照题型刷，但是最直接的方法是：

先刷二叉树，先刷二叉树，先刷二叉树！

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

刷二叉树看到题目没思路？其实不是没有思路，只是没有理解我们所说的「框架」是什么。不要小看这几行代码，几乎所有二叉树的题目都是一套这个框架就出来了。

function recursive(node: TreeNode) {
  // 前序遍历
  traverse(node.left)
  // 中序遍历
  traverse(node.right)
  // 后序遍历
}

对于一个理解二叉树的人来说，刷一到二叉树的题目花不了多少时间。那么如果你对刷题无从下手或者有畏惧心理，不妨从二叉树下手。只要刷完二叉树，再去做什么回溯动态规划分治，你就会发现只要涉及递归的问题，都是树的问题。

# 总结几句

数据结构的基本存储方式是链式和顺序两种，基本操作就是增删改查，遍历方式无非递归和迭代。

刷题建议从「树」分类开始刷，结合框架思维，把几十道题刷完，对于树结构的理解应该就到位了。这时候再去看回溯、动态规划、分治等算法专题，对思路的理解可能会更加深刻一下。

← 回溯算法解题套路框架.md 教你几招算法笔试题的套路.md →