数据结构和算法（构建中...）

发表于 更新于 分类于 ，

《数据结构和算法》包含…名字已经说明了好吧，文中不是千篇一律的教科书文字，是我自己写的，我自己的理解，这里的示例代码是 Java 写的，一般情况下省略外层的类，其他语言版本在另一份文档中，叫《数据结构和算法-其他语言版本》。总体写的完全是白话文，对话的感觉，啰里啰嗦的，但是，啊，我觉得很棒啊，我喜欢，就这样。

为什么要自己写呢？市面上虽然有大把资料，但是自己写的才是自己的。也许我知道一个算法或者数据结构的一切，但是我不去多多复习的话，我会忘记的，再去翻找其他资料，我的理解也许没那么快，这份文档，也是写给我自己看的，在忘记的时候，以便快速回忆起来。

数据结构和算法（构建中…）

大 O 表示法

哎这玩意，我看了几万遍，才明白，哦，是这样！下一秒，这怎么算来着？没错，这就是我的真实感受，不够理解，就算理解了吧，很快又忘记了，想记住呢，还是需要得多多联系，把它真正的记住。

学习顺序

学习顺序是我按照自己的接受程度订的，高亮的是学完了的，没高亮的是没学会的，总之都学了，还没完全学会，这是自我检验标准罢了。顺序：==数组== -> ==链表== -> ==哈希表== -> ==字符串== -> ==栈== -> ==队列== -> 树 -> 回溯 -> 贪心 -> 动态规划 -> 图论 -> …

基础

数组

数组，是连续的数据集合，连续不仅体现在逻辑上，也体现在内存地址上，他们在内存上也是一样的连续。数组的下标是从0开始的，这不用多说。其实数组很简单，但是它的应用更多的体现在算法逻辑和代码逻辑的转变，比如二分查找的思想很简单吧，但是真正写代码的时候还是要注意细节的，细节决定成败嘛。

二分查找

二分查找是有条件的：有序和不重复。

满足条件之后，就可以说二分查找的核心了，二分查找是思想是通过“中间值”，来快速判断目标所在的位置。这个算法很容易理解，但是代码是思路和理解的思路是不一样的，理解了是查找的思想，自然可以想到这里有四个变量：左边界，右边界，中间值，目标值。涉及到区间，就要考虑区间的闭合问题，而在二分查找的领域内，常见的区间考虑形式有两种，一种是 左闭右闭 [,]，一种是左闭右开 [,)。再想，二分查找是怎么找的？循环的条件是比较左边界和右边界的大小，比较大小，又分两类，一类是纯大于纯小于，一类是大于等于和小于等于。怎么样才是合理的呢？先看结论吧：

左闭右闭 [,] 要加等于

左闭右开 [,) 不加等于

问为什么？比如，在左闭右闭的条件下，判断条件是：if(left <= right) 因为在这个区间，左边和右边相等是有必要且合理的，这个区间就是包含着端点值的。那在左闭右开的条件下，左边和右边就没必要判断大小了，这个区间的右侧已经不在考虑范围之内了，所以判断条件是 if(left < right)。

再就是赋值问题，在数据序列是升序、左闭右闭的条件下，当执行到if(num[mid] < target)的时候，那么右边界就要移动了，移动到哪里呢？由于右边界是包含在区间内部的，所以右边界移动到中间值这里就好，那么问题来了，此时很明显，既然执行到这里，那么必然是 num[mid] != target，中间值没有必要再去比较了，右边界也就可以再移动一位到 mid-1 的地方，即，right = mid - 1。同理，数据升序、左闭右开的情况，right从一开始就必须要指向数据序列最右侧的下一个数据才能包含全部数据， 还是上面的时刻，中间值已经没有再次比较的必要了，既然右边界本身就不包含，那么直接就让右边界等于中间值好了，即，right = mid。

在左闭右闭时候，示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 升序，无重复，左闭右闭，返回查询到的索引，未找到返回 -1
public int search(int[] nums, int target) {
    // 避免无效计算
    if(target < nums[0] || target > nums[nums.length - 1]) {
        return -1;
    }
    int left = 0, right = nums.length - 1;
    while(left <= right) {
        int mid = left + ((right - left) >> 1);
        if(nums[mid] == target) {
            return mid;
        } else if(nums[mid] < target) {
            left = mid + 1;
        } else if(nums[mid] > target) {
            right = mid - 1;
        }
    }
    return -1;
}

在左闭右开的时候，示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 升序，无重复，左闭右开，返回查询到的索引，未找到返回 -1
public int search(int[] nums, int target) {
    // 避免无效计算
    if(target < nums[0] || target > nums[nums.length - 1]) {
        return -1;
    }
    int left = 0, right = nums.length;
    while(left < right) {
        int mid = left + ((right - left) >> 1);
        if(nums[mid] == target) {
            return mid;
        } else if(nums[mid] < target) {
            left = mid + 1;0
        } else if(nums[mid] > target) {
            right = mid;
        }
    }
    return -1;
}

思路：后续在遇到需要二分查找的情况时，需要判断是否有序，是否有重复，根据区间判断条件就好。

力扣题目：
704 二分查找

链表

字符串

哈希表

哈希表是根据关键码的值而直接进行访问的数据结构。说白了可以将任何一种数据映射成一个独一无二的值，而查找的时候直接映射一下就可以知道是否保存的有所需要寻找的值，具体是怎么映射的暂时不用管，知道是哈希函数就好。作用：一般都是用于快速的判断一个元素是否出现在集合里。

说到这里，就会引出哈希碰撞的概念，指的是两个元素映射到了同一个值，使用拉链法可以将元素以 [链表] 的方式挂载在哈希值后面，而使用 线性探测法会将元素向下移动，直到移动到空位置。

队列

栈

堆

双指针

双指针分为快慢指针和相向指针。多用于数组、链表、字符串的算法题中。如果不好理解，在纸上画画就好理解了。下面讲解的双指针的一种一种用法，很多题目的用法都不一样，用其中一种理解双指针是什么就好了，用法千奇百怪，重点还在于融会贯通，需要多多练习做题就好，注意观察！

题目：
27 移除元素
977 有序数组的平方

快慢指针

快慢指针的精髓在于：利用两个指针，将本来需要两个循环完成的任务压缩成一个循环完成。这个算法对数据的操作是原地性质的，没有开辟额外的空间。做题的时候需要明确快慢指针的含义、职责是什么，才能够顺畅的解题。这种算法需要根据题目来具体说，这里贴题就好，细节呢靠参悟哈哈。

题目：
27 移除元素

用上面的这个题目举个例子，原地移除数组中的元素，快指针的含义是找到新的数组，慢指针的含义是找到需要被覆盖的数组下标，这样循环一轮，需要移除的元素就被覆盖了，最终的结果就是新的数组。代码如下：

1
2
3
4
5
6
7
8
9
10
public int removeElement(int[] nums, int target) {
    int slow = 0;
    for(int fast = 0; fast < nums.length; fast++) {
        if(nums[fast] != target) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow;
}

相向指针

还是以上一题目为例。相向指针相比快慢指针而言有一些不同，快慢指针是用快指针的值覆盖慢指针的值，数据的顺序是不变的，而在不考虑顺序的情况下，相向指针也可以使用，相向指针是用右指针的值覆盖左指针，右指针找非目标，左指针找目标，用右指针覆盖左指针并删除右指针，就完成了一轮删除！但是顺序乱了。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int removeElement(int[] nums, int target) {
    int left = 0, right = nums.length-1;
    // 先将右指针移动到非目标处。
    while(right >= 0 && nums[right] == target) {
        right--;
    }
    while(left <= right) {
        if(nums[left] == target) {
            nums[left] = nums[right];
            right--;
        }
        left++;
        // 需要考虑到万一右指针还是 target 的情况，需要继续移动。
        while(right >=0 && nums[right] == target) {
            right--;
        }
    }
    // 题目要的是长度，所以返回 left 刚好
    return left;
}

滑动窗口

题目：
209 长度最小的子数组

排序

比较排序

术语

  • 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
  • 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面。
  • 内排序：所有排序操作都在内存中完成。
  • 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。

冒泡排序

运行模式
核心是相邻两个元素比较，不符合条件就换位置，然后逐一向后比较相邻的元素

代码实现

选择排序

运行模式
每次比较就是从起始点找到数组结尾，找到最小的那个，移动到数组最前面，以此类推，最大的也是同样的效果。

代码实现

插入排序

运行模式
两个两个的相比较，但是遇到小的数字，要不断的向前比较，直到找到合适的位置，数字大也是同样的。有个比喻很恰当，比如我手需要拿扑克牌，每次摸一张牌，就需要在手上找到它对应的位置，手上的牌总是是排序好的，插入排序也是一样，它是在本身的数组中运行的，直到找到元素合适的位置才停下来。

代码实现
Java 语言版本

希尔排序/缩小增量排序

运行模式
插入排序的改进版本。非稳定排序算法。核心在于间隔序列的设定。说白了，希尔排序就是插入排序的改进版，插入排序针对整个数据序列执行插入排序，效率当然不高，但是希尔排序是给整个数据序列进行了分组，每个组里面用插入排序，分组的依据就是：“间隔”。那么谈到这里，就得提出“间隔”是如何定义的了。

间隔的定义：初始间隔：数组长度除以2倍取整，得到的数字。数据序列按照间隔分组序列，子序列内部采用插入排序。一遍结束后，后续的间隔以前一个间隔除以2取整，直到间隔为1，那么排序完成。

举个例子
有一串数据序列：5,10,7,0,4,11,2,9,12,3,6,8,13,1 一共14个数字，按照希尔排序的规则，初始间隔便是：14/2=7 所以，第一个5和第七个9就是一个组的数字了，对这两个数字进行插入排序。

第一遍排序完的结果是：5,10,3,0,4,11,1,9,12,7,6,8,13,2 到这里就能够看出来了，它也是在原数据序列上执行的，和插入排序很像，对吧。

这里也体现出了不含前面包含后面这种现象，或者叫，思想的东西。
间隔为7，不包含5，包含9，便是如此。

代码实现
Java 语言版本

归并排序

运行模式
归并排序是分治思想的产物，先将数组拆分成两组，然后继续拆分，直到只剩下两个或者1个，这是拆分。算法在开始前需要申请空间，为原数列的长度，在申请空间后，将拆分后的数据进行比较，比较的结果放在新空间内部。代码实现的思路和算法的思路是有一些差异的，这就是有时候懂算法，却不一定能够写出来，原因就在于没有把握到代码思维，两种思维的转换是需要刻意练习的。

代码实现
Java 语言版本

快速排序

运行模式
快速排序的模式也是分而治之，但是是递归类型的。运行快速排序需要为数据序列设置一个“基准”，比“基准”小的元素排到前面，比“基准”大的元素排到后面，这样“基准”前后就出现了两个新的数据序列，然后再为这两个数据序列进行同样的操作即可，如此循环即可。当然，得注意，这是算法思维，而要转换为代码思维，是需要刻意去思考，想不出来没关系，就去看别人写的，然后细想为什么，大概这样就知道了。

代码实现
Java 语言版本

桶排序

计数排序

基数排序

堆排序

递归和分治

朴素模式匹配算法

说白了，你现在需要比较两个字符串，需要在长的那个字符串中找出短的字符串，用长字符串的每一个字符代表子串的开头，与子串进行比较。对主串做大循环，对子串做小循环，直到匹配成功。这个方法，很，朴素。

KMP模式匹配算法

KMP 算法有个核心，叫做 部分匹配表 的这么个东西，这个东西决定了匹配的位移偏移量。这个算法还得举例子。

首先要说这个 [部分匹配表] 。比如，有个字符串是 ‘abcdab’。
针对第 1 位 a, 前缀为 ‘’，后缀为 ‘’，相等部分长度为 0
针对第 2 位 ab，前缀为 ‘a’，后缀为 ‘b’，相等部分长度为 0
针对第 3 位 abc，前缀为 ‘a、ab’，后缀为 ‘c、bc’，相等部分长度为 0
针对第 4 位 abcd，前缀为 ‘a、ab、abc’，后缀为 ‘d、cd、bcd’，相等部分长度为 0
针对第 5 位 abcda，前缀为 ‘a、ab、abc、abcd’，后缀为 ‘a、da、cda、bcda’，相等部分长度为 1
针对第 6 位 abcdab，前缀为 ‘a、ab、abc、abcd、abcda’，后缀为 ‘b、ab、dab、cdab、bcdab’，相等部分长度为 2
这样一来，部分比配表 的结果是：
a b c d a b
0 0 0 0 1 2

怎么用呢？
比如，需要在 abcabcdab 中 找出 abcdab。
第 1 次比较：
abdabcdab
abcdab
上述两行相比较，比较完毕之后，应该移动到哪里开始比较呢？从上述的比较我们可以很直观的看出来：前面 2 位 匹配成功了，长度是 2。这是已知的信息。
接来下需要介绍一个公式：移动位数 = 已匹配的字符数 - 对应的部分匹配值 ,在上述的例子中，已匹配的字符数 = 2，对应的部分匹配值是：0, 所以，移动位数 = 2 - 0 = 2。要注意的是，这个公式是用在有匹配上的字符的情况下采用，没有的话就直接移动 1 位就好了。
第 2 次比较：
abdabcdab
abcdab
执行完偏移，便开始了这一次比较，第 1 位 不匹配，则移动 1 位。
第 3 次比较：
abdabcdab
abcdab
找到啦。效率巨高好吧。

代码实现 - 封装版

代码…其实在实际应用中是有封装好的 KMP 算法的，不需要每次都去自己实现它。先说封装版本的。封装版的是要用的，KMP写起来很复杂（也不能说复杂，就是太多了），明白原理了就可以，在实际中，我遇到也是写封装版（如果有的话）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.regex.Pattern;
import java.util.regex.Matcher;

public class KMPAlgorithmExample {
    public static void main(String[] args) {
        String text = "Hello, world!";
        String pattern = "world";
        //  Pattern.CASE_INSENSITIVE 标志，表示不区分大小写
        Pattern kmpPattern = Pattern.compile(pattern, Pattern.CASE_INSENSITIVE);
        Matcher matcher = kmpPattern.matcher(text);

        if (matcher.find()) {
            // 获取匹配的起始位置并打印
            System.out.println("Found at index " + matcher.start());
        } else {
            System.out.println("Not found");
        }
    }
}

Java 独立实现版，这个也不能少啦。

1

树

二叉树

回溯算法

图

深度优先搜索

广度优先搜索

迪克斯特拉算法-最短路径

贪心算法

教室调度问题

背包问题

集合覆盖问题

动态规划

背包问题

最长公共子串

前缀和

K 最近邻算法