数据结构和算法的框架思维

数据结构的框架思维

在不纠结细节的情况下，从整体到细节，自顶向下，从抽象到具体的对数据结构和算法建立一个框架性的认识。

数据结构的存储方式

数据结构的存储方式只有两种：数组（顺序存储）和链表（链式存储）。

结构基础：数组、链表
上层建筑：散列表、栈、队列、堆、树、图等

队列、栈：既可以使用链表也可以使用数组实现。用数组实现，就要处理扩容缩容的问题；用链表实现，没有这个问题，但需要更多的内存空间存储节点指针。

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

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

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

数组和链表二者的优缺点：

类型	优点	缺点
数组	1. 紧凑连续存储，可以随机访问，通过索引快速找到对应元素 2. 相对节约存储空间	1. 扩容问题 2. 难以在数组中间进行插入和删除元素
链表	1. 元素不连续，通过指针指向下一个元素的位置，不存在扩容问题 2. 知道某一元素的前驱和后驱，操作指针即可在O(1)删除该元素或者插入新元素	1. 无法根据一个索引算出对应元素的地址，所以不能随机访问 2. 需要开辟指针空间，会消耗相对更多的储存空间

数据结构的基本操作

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

那么，我们如何在不同的应用场景，选择合适的数据结构，尽可能高效地增删查改。

如何遍历 + 访问？从最高层来看，各种数据结构的遍历 + 访问无非两种形式：线性的和非线性的。线性就是 for/while 迭代为代表，非线性就是递归为代表。

再具体一步，分为以下几种框架：

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

void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        // 迭代访问 arr[i]
    }
}

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

/* 基本的单链表节点 */
class ListNode {
    int val;
    ListNode next;
}

void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {
        // 迭代访问 p.val
    }
}

void traverse(ListNode head) {
    // 递归访问 head.val
    traverse(head.next);
}

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

/* 基本的二叉树节点 */
class TreeNode {
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
}

N 叉树的遍历框架

/* 基本的 N 叉树节点 */
class TreeNode {
    int val;
    TreeNode[] children;
}

void traverse(TreeNode root) {
    for (TreeNode child : root.children)
        traverse(child);
}

N 叉树的遍历又可以扩展为图的遍历，因为图就是好几 N 叉棵树的结合体。

算法学习指南

刷题顺序：

1、先学习像数组、链表这种基本数据结构的常用算法，比如单链表翻转，前缀和数组，二分搜索等；

2、学会基础算法之后，先刷二叉树；

3、再刷回溯算法、动态规划这类笔试常考题

总结

1、数据结构的基本存储方式：链式、顺序

2、数据结构的基本操作：增删查改

3、数据结构的遍历方式：迭代、递归

算法的框架思维

主要内容：

1、算法的本质是什么

2、概括各种常用的算法

算法的本质

用一句话总结，算法的本质就是「穷举」。

需要注意的是，穷举有两个关键难点：无遗漏、无冗余。

遗漏，会直接导致答案出错；冗余，会拖慢算法的运行速度。所以，当你看到一道算法题，可以从这两个维度去思考：

1、如何穷举？即无遗漏地穷举所有可能解。

2、如何聪明地穷举？即避免所有冗余的计算，消耗尽可能少的资源求出答案。

什么算法的难点在「如何穷举」呢？一般是递归类问题，最典型的就是动态规划系列问题。

动态规划系列问题的核心原理，先写出暴力穷举解法（状态转移方程），加个备忘录就成自顶向下的递归解法了，再改一改就成自底向上的递推迭代解法。

什么算法的难点在「如何聪明地穷举」呢？一些耳熟能详的非递归算法技巧，都可以归在这一类。

1）Union Find 算法

2）贪心算法

3）KMP字符匹配算法

下面概括性地列举一些常见的算法技巧：

数组/单链表系列算法

双指针

比如判断单链表是否成环问题

可以用暴力解法遍历每一个节点，但是用快慢指针可以避免使用额外的空间。

二分搜索

可以归为两端向中心的双指针。

如果在数组中搜索元素，可以用一个 for 循环穷举搞定，但如果数组是有序的，二分搜索是一种更聪明的搜索方式。

**限制：**二分搜索只能用于有序数组。

滑动窗口

典型的快慢双指针，快慢指针中间就是滑动的「窗口」，主要用于解决子串问题。

比如最小覆盖子串这道题，让你寻找包含特定字符的最短子串

字符串暴力匹配算法，用嵌套 for 循环穷举，平方级的复杂度。而滑动窗口技巧可以用快慢指针遍历一次就求出答案。

**限制：**滑动窗口无法用于有负数的数组，因为无法确定滑动窗口的扩大和缩小的时机。

回文串

如果判断一个串是否是回文串，使用双指针从两端向中心检查，如果寻找回文子串，就从中心向两端扩散。

前缀和 和 差分数组

如果频繁地让你计算子数组的和，每次用 for 循环去遍历肯定没问题，但前缀和技巧预计算一个 preSum 数组，就可以避免循环。

类似的，如果频繁地让你对子数组进行增减操作，也可以每次用 for 循环去操作，但差分数组技巧维护一个 diff 数组，也可以避免循环。

二叉树系列算法

二叉树题目的递归解法可以分两类思路：

第一类是遍历一遍二叉树得出答案——回溯法

第二类是通过分解问题计算出答案——动态规划

1）最优子问题

2）重叠子问题

动态规划系列问题有「最优子结构」和「重叠子问题」两个特性，而且大多是让你求最值的。很多算法虽然不属于动态规划，但也符合分解问题的思维模式。

第三类是大问题分解成子问题——分治法

核心依然是大问题分解成子问题，只不过没有重叠子问题，不能用备忘录去优化效率罢了。

第四类是——DFS

更进一步，图论相关的算法也是二叉树算法的延续。

1） DFS 算法

2）BFS算法

上述这些算法的本质都是穷举二（多）叉树，有机会的话通过剪枝或者备忘录的方式减少冗余计算，提高效率。