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

一、前言

本专栏所有文章所讨论范围均局限在计算机数据结构和算法，加密、数学公式等算法不包括在内。

几句话总结一切数据结构和算法

种种数据结构，皆为数组（顺序存储）和链表（链式存储）的变换。

数据结构的关键点在于遍历和访问，即增删查改等基本操作。

种种算法，皆为穷举。

穷举的关键点在于无遗漏和无冗余。熟练掌握算法框架，可以做到无遗漏；充分利用信息，可以做到无冗余。

二、数据结构的存储方式

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

数组：由于是紧凑连续存储，可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。

链表：因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。

三、数据结构的基本操作

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

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

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

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

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

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

// 基本的单链表节点
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);
}

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

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

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

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

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

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

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

三、算法的本质

如果要让我一句话总结，我想说算法的本质就是「穷举」。

顺便强调下，「算法工程师」做的这个「算法」，和「数据结构与算法」中的这个「算法」完全是两码事，免得一些初学读者误解。

为了区分，不妨称算法工程师研究的算法为「数学算法」，称刷题面试的算法为「计算机算法」，我写的内容主要聚焦的是「计算机算法」。

其实计算机思维也没什么高端的，你想想计算机的特点是啥？不就是快嘛，你的脑回路一秒只能转一圈，人家 CPU 转几万圈无压力。所以计算机解决问题的方式大道至简，就是穷举。

四、穷举的难点

但是，你千万不要觉得穷举这个事儿很简单，穷举有两个关键难点：无遗漏、无冗余。

当你看到一道算法题，可以从这两个维度去思考：

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

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

什么算法的难点在「如何穷举」呢？一般是递归类问题，比方说回溯算法、动态规划系列算法。

五、数组/单链表系列算法

单链表常考的技巧就是双指针，属于「如何聪明地穷举」这一类，单链表双指针技巧汇总全给你总结好了，会者不难，难者不会。

数组常用的技巧有也是双指针相关的技巧，也都属于「如何聪明地穷举」这一类。

再说说滑动窗口算法技巧，典型的快慢双指针。你用嵌套 for 循环花 O(N^2) 的时间肯定可以穷举出所有子数组，也就必然可以找到符合题目要求的子数组。但是滑动窗口算法表示，在某些场景下，它可以用一快一慢两个指针，只需 O(N) 的时间就可以找到答案，这就是更聪明地穷举方式。

最后说说前缀和技巧和差分数组技巧。

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

数组链表的技巧差不多就这些了，都比较固定，只要你都见过，运用出来的难度不算大，之后会说一说稍微有些难度的算法。