算法总结

排序算法

分类

时间复杂度

算法稳定性：在一组待排序记录中，如果存在任意两个相等的元素，我们标记为 R 和 S，且在待排序记录中 R 在 S 前，如果在排序后 R 依然在 S 前，即它们的前后位置在排序前后不发生改变，则称为排序算法为稳定的。

十大经典排序算法（动图演示） – 一像素 – 博客园 (cnblogs.com)

算法实例

测试程序

#include <iostream>
using namespace std;
int main()
{
    const int len = 10;             //测试数组长度,数组元素范围为：0 <= nums[i] <= 100
    int nums[len];
    cout << "初始随机数:" << endl;
    for (int i = 0; i < len; i++)
    {
        nums[i] = rand() % 101;
        printf("%3d", nums[i]);
    }

    testSort(nums, 0, len-1);       //请调用你需要测试的函数

    printf("\n排序后:\n");
    for (int i = 0; i < len; i++)
        printf("%3d", nums[i]);

    //判断排序后数组是否单调
    cout << "\n单调性:";
    for(int i = 0; i<len-1; i++)
    {
        if(nums[i] > nums[i+1])
        {
            cout << "非单调" << endl;
            break;
        }
        else if(i == len - 2)
            cout << "单调" << endl;
    }
    getchar();
    return 0;
}

插入排序

  /*
  算法简介：从第二个元素开始(将第一个元素视为已排好的数)，首先取出第二个数,
  判断第二个元素是否小于（大于）前一个元素，若小于（大于）则将第二个元素之前
  的[元素列]向后移动一个位置，然后将该数插入移动[元素列]后的前面所空出来的一
  个位置，重复这个操作，直到所有元素排序完成
  */
  void insertSort(int *arr, int len)
  {
    //for-while版
    for (int i = 1; i <= len; i++)//默认0号下标储存的数已排好
    {
        int temp = arr[i];//取出待插入的数
        int j = i;
        while (j > 0 && temp < arr[j-1])//若未达到0号数组 且 待插入的数小于前面的数
        {
            arr[j] = arr[j-1];//将[待插入的数]前面的数向后移动
            j--;
        }
        arr[j] = temp;//插入[待插入的数]
    }
    /*
    //for-for版
    for(int i = 1, j; i<len; i++)
    {
        int temp = nums[i];
        for(j = i-1; j>=0 && temp < nums[j]; j--)
                nums[j+1] = nums[j];

        nums[j+1] = temp;
    }*/
  }

选择排序

/*
算法简介：遍历全部元素一遍，找到最小值，然后将该值与第一号元素交换，然后
遍历余下n-1个元素，找到最小值，然后将该值与第二号元素相交换，重复以上操
作，直到排序完所有元素。
*/
void selectionSort(int *nums, int len)
{
    for (int i = 0; i < len - 1; i++)
    {
        int min = i;//记录数组的最小值所在位置的下标（初始化为第i个元素）
        for (int j = i + 1; j < len; j++)//走访未排序的元素
            if (nums[j] < nums[min])
                min = j;//记录最小值所在的位置

        if (min != i)//当最小值元素不是i号元素时进行替换
        {
            int temp = nums[min];
            nums[min] = nums[i];
            nums[i] = temp;
        }
    }
}

堆排序

堆排序(heapsort)_哔哩哔哩_bilibili

基础

堆的实现是在完全二叉树上来实现

堆的种类

• 大根堆
  对任意节点来说，根节点的值大于左子节点和右子节点
• 小根堆
  对任意节点来说，根节点的值小于左子节点和右子节点

void heapify(int arr[], int n, int i)//构建大根堆，i是需要构建大根堆的位置，n是数组长度
{
    if(i > n)
        return;
    int c1 = 2*i + 1, c2 = 2*i + 2, max = i;//c1：左子节点 c2：右子节点 i：父节点
    if(c1 <= n && arr[c1] < arr[max])
        max = c1;
    if(c2 <= n && arr[c2] < arr[max])
        max = c2;

    if (max != i)
    {
        swap(arr[i], arr[max]);
        heapify(arr, n, max);
    }
}
void heapSort(int arr[], int n)//传递的n是数组长度-1
{
    for(int i = n / 2; i >= 0; i--)//从下往上，即从完全二叉树的最后一个结点的父节点开始构建大根堆
        heapify(arr, n, i);

    for(int i = n; i>= 0; i--)
    {
        swap(arr[0], arr[i]);//大根堆构造完成，第一个元素是整个数组最大的元素，将其移动
        heapify(arr, i - 1, 0);//对前i-1个构造堆
    }
}

冒泡排序

/*
算法简介：重复地走访过要排序的元素列，依次比较两个相邻的元素，如果大
小顺序错误就将这两个元素交换，直到没有相邻元素需要交换为止
*/
void bubbleSort(int *nums, int len)
{
    int i; //比较的轮数
    int j; //每轮比较的次数

    for (i = 0; i < len - 1; i++)//比较len - 1轮(例如有n个元素，只要对其余的n-1个元素排序后，剩下的那一个就不用排序)
    {
        for (j = 0; j<len - i - 1; j++)//每轮比较len - i - 1次(每一轮排序结束后，都会有一个排序好的元素，不用再对其进行排序)
        {
            if (nums[j] > nums[j + 1])//大于为从小到大排，反之为从大到小排序
            {
                int t = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = t;
            }
        }
    }
}

快速排序

基本思想

分治法，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序基准数的选择

• 一种错误的方法-基准位置为首（尾）位置
  

  通常的、没有经过充分考虑的选择是将第一个元素做为”基准“。如果输入数随机的，那么这是可以接受的，但是如果输入是预排序的或是反序的，那么这样的”基准“就是一个劣质的分割，因为所以的元素不是被划入S1就是被划入S2。实际上，如果第一个元素用作”基准“而且输入是预先排序的，那么快速排序花费的时间将是O(n^2)的，可是实际上却没干什么事，因此，使用第一个元素作为”基准“是绝对糟糕的。

• 一种安全的方法-位置随机选择
  

  一种安全的方法是随机选取”基准“。这种策略是非常安全的，除非随机生成器有问题，但是随机数的生成一般是昂贵的，减少不了算法其余部分的平均运行时间。

• 三数中值分割法-取中心位置为基准位置
  

  一组N个数的中值是第[N/2]个最大的数。”基准“的最好选择是数组的中值。但是这很难算出，且减慢快速排序的速度。这样的中值的估计量可以通过随机选取三个元素并用它们的中值作为”基准”而得到。实际上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为“基准”。

教材上给出的代码

/*
算法简介：假定有一个长度为n的数组；先选择一个基准数，这里我们以数组中的0号元素为
基准，然后1号元素标记为左标记，n-1号元素为右标记，之后左边标记右移，直到某一个元
素比基准数大时停止移动; 同样，右标记向左移动，直到某一个元素比基准数小为止，停止
移动，然后将左标记元素和右标记的元素相互交换（注意，这里假定左标记是小于右标记的）
之后同上操作，左标记向右移动，右标记向左移动，直到左标记等于右标记时，将基准数与
这个左标记相交换，这时候，数组以基准数为界分为了左右两部分，对于这左右两部分，同
最开始的操作，直到全部排序完成
*/
void quicksort(int *nums, int left, int right)
{
    if (left >= right)//当左标记大于右标记，退出函数
        return;
    int pivot = nums[left];//先存储基准数(基准数的位置可选取left或者right，但是切记第61行的基准数与相遇点位置交换也要改成相应left/right)
    int i = left;//左标记，第一：为了减少代码量，所以不用left+1；第二：用left+1这种写法，在数组只有一个元素或者两个元素时，可能出错
    int j = right;//右标记

    while (i < j)//当左标记小于右标记
    {
        while (i < j && nums[j] >= pivot)//顺序很重要，要先从基准数的对面开始，即从右开始
            j--;
        //再从左往右找
        while (i < j && nums[i] <= pivot)//然后在左边
            i++;

        if (i < j)//当i和j没有相遇时，交换两个数在数组中的位置,  也可以使用c++ algorithm头文件的swap函数
            swap(nums[i], nums[j]);
    }
    nums[left] = nums[i];  //最终将基准数与左右标记相遇点交换
    nums[i] = pivot;

    quicksort(nums, left, i - 1);//继续处理左边的，这里是一个递归的过程
    quicksort(nums, i + 1, right);//继续处理右边的，这里是一个递归的过程
}

• 以right为基准数

  ​ 教材所给出的代码，默认基准数只能选择left或者right，当选择right的时候要修改①基准数选择right，②修改两个while循环位置，③修改最终基准数与标记相遇位置

• 以中间点/随机位置为基准数

  ​ 在默认的代码之上是无法直接修改为（left+right）/2的，修改方式必须为先找到基准位置mid = （left+right）/2，然后在将该位置的数与left位置的数互换，这样也就是以中间结点为基准数的快排了

  int mid = left + (right-left)/2;
  swap(nums[left], nums[mid]);//swap(nums[left + (right-left)/2], nums[left]);
    int i = left, j = right, pivot = nums[left];
  //···········
  

• 缺点

  ​ 该方法在数组长度超大且元素唯一的情况，例如nums = {50000,50000,50000，······，50000};的情况时，速度仍不如改进后的代码

改进后的代码

void quicksort(int *nums, int left, int right)
{
    if(left >= right)
        return;
    int i = left-1, j = right+1, mid = nums[left + (right-left) / 2];//rand() % (right + 1 - left) + left => [left, right]
    while(i < j)
    {
        do i++; while(nums[i] < mid);
        do j--; while(nums[j] > mid);
        if(i < j)
            swap(nums[i],nums[j]);
    }
    quicksort(nums, left, j);
    quicksort(nums, j+1, right);
}

该方法缺点：

• 以left为基准数

  ​ 只能使用quicksort(nums, left, j) 和 quicksort(nums, j+1, right);

• 以right为基准数

  ​ 只能使用quicksort(nums, left, i-1) 和 quicksort(nums, i, right);

上述两种情况的原因反例就是nums[2] = {1， 2};​这种情况，上述的写法会导致死循环，而上述代码中使用right的方式是因为当数组元素个数为2时，会出现和以left为基准数相同的情况，因此要用j​

快速排序 – 非递归

栈和队列实现

使用C++ STL stack/queue来实现

以下代码改队列将stack替换为queue，st.top()替换为st.front()，同时将int right 和left互换（left先入队right后入队）

#include <stack>
void quicksort(int *nums, int left, int right)
{
    stack<int>st;
    st.push(left);st.push(right);       //初始排序范围为[left, right]

    while (!st.empty())     //还有待排序的范围
    {
        right = st.top();st.pop();    //根据入栈顺序知，栈顶是right，因此代码必须先取right在取left
        left = st.top();st.pop();     //这两行代码必须要加上，因为每次循环left和right的值都是在改变的，如果省略，直接用st.top()给i和j复制那么就会出现错误，这对下面的基准数调换会发生错误，因为每次基准数调换的位置都不相同
        int i = left, j = right, pivot = nums[left];    //放置哨兵和选择基准数

        while(i < j)
        {
            while (i < j && nums[j] >= pivot)
                j--;
            while (i < j && nums[i] <= pivot)
                i++;
            if (i < j)
                swap(nums[i], nums[j]);
        }
        swap(nums[left], nums[i]);      //基准数与相遇点互换
        if(left < i-1)                  //quicksort(nums, left, i - 1);
            st.push(left), st.push(i-1);//下次排序的范围入栈

        if(i + 1 < right)               //quicksort(nums, i + 1, right);
            st.push(i+1), st.push(right);
    }
}

归并排序

这段内容建议草稿纸上画图，当初就是画图然后想通的，先划分到第一个递归恰好结束的地方，这时第一个递归恰好分出来一个数，开始第二个递归，第二个递归也恰好分出两个数，然后申请一个空间，对这两个数进行排序，将这两个数排序后放到新空间中，要知道这个新空间的长度恰好等于两个递归划分之后的长度，在将该新空间的数（已经排序好了）依次复制到原来划分的位置上，在删除这个新空间，重复以上，最终就可以排序完成

void mergeSort(int *nums, int left, int right)
{
    if(left >= right)
        return;
    int mid = left + (right - left)/2;
    mergeSort(nums, left, mid);//该递归恰好结束时left == mid，即恰好有一个元素
    mergeSort(nums, mid+1, right);//该递归恰好结束时也恰好只有一个元素

    int *temp = new int[right - left + 1];//申请一个2元素大小的空间用于存放排序后的数据
    int k = 0, i = left, j = mid + 1;//temp数组起始位置和边界位置
    while(i <= mid && j <= right)
    {
        if(nums[i] < nums[j])
            temp[k++] = nums[i++];
        else
            temp[k++] = nums[j++];
    }
    while(i<=mid)
        temp[k++] = nums[i++];
    while(j<=right)
        temp[k++] = nums[j++];
    for(int i = left, j = 0; i<=right; i++, j++)
        nums[i] = temp[j];
    delete[] temp;
}

注意：每次都将申请的空间释放固然是好的，但是每次都重新申请空间也会浪费大量时间，因此建议使用一个全局的变量或者形参用作临时存储空间temp

进阶：链表排序

归并排序 – 非递归

void merge(int arr[], int left, int mid, int right)//多传递一个mid值的原因，mid = (left+right)/2并不是一定成立，见主调函数的第二次调用
{
    int *temp = new int[right-left+1];
    int k = 0, i = left, j = mid+1;
    while(i <= mid && j <= right)
    {
        if(arr[i] < arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
    while(i <= mid)
        temp[k++] = arr[i++];
    while(j <= right)
        temp[k++] = arr[j++];

    for(int i = left, j = 0; i<=right; i++, j++)
        arr[i] = temp[j];
    delete[] temp;
}

void mergeSort(int arr[] , int n)
{
    for(int k = 1; k <= n; k *= 2)//将数组划分为包含k个元素的子数组, 每次划分的结果都是得到新的含有2*k个元素的子数组
    {
        int i = 0;          //n-2*k+1是最后一个子数组的起始位置
        for(i = 0; i <= n-2*k+1; i += 2*k)//对含有2*k个元素的子数组排序，直到达到最后一个2*k个元素的子数组，要注意着并不代表最后一个子数组之后没有元素
            merge(arr, i, i+k-1, i+2*k-1);

        //当n为奇数情况时，需要考虑最后一个单着的元素
        if(i < n-k+1)//将最后一个元素与前偶数个归并好的元素最后归并成一个序列
            merge(arr, i, i+k-1, n);
    }
}

查找算法

有序表查找

二分查找（折半查找）

一种针对有序区间的O(logn)搜索方法，最常见用于已经排好序的数组，需要注意的是二分查找并不是针对有序的数据才能实现查找。下面举个例子

有一天小明到图书馆借了 N 本书，出图书馆的时候，警报响了，于是保安把小明拦下，要检查一下哪本书没有登记出借。小明正准备把每一本书在报警器下过一下，以找出引发警报的书，但是保安露出不屑的眼神：你连二分查找都不会吗？ 于是保安把书分成两堆，让第一堆过一下报警器，报警器响；于是再把这堆书分成两堆…… 最终，检测了 logN 次之后，保安成功的找到了那本引起警报的书，露出了得意和嘲讽的笑容。于是小明背着剩下的书走了。 从此，图书馆丢了 N – 1 本书。

二分查找并不简单，Knuth 大佬（发明 KMP 算法的其中一位）都说二分查找：思路很简单，细节是魔鬼。 很多人喜欢拿整型溢出的 bug 说事儿，但是二分查找真正的坑根本就不是那个细节问题，而是在于到底要给 mid 加一还是减一，while 里到底用 <= 还是 <。

二分查找套路和解题模板（bilibili）

二分查找细节详解（力扣）

基本原则

• 每次都要缩减搜索区域
• 每次缩减不能排除潜在答案

三大模板

• 找一个准确值
  • 循环条件 l <= r
  • 缩减搜索空间：l = mid + 1， r = mid – 1
• 找一个模糊值（边界值）
  • 循环条件 l < r
  • 缩减搜索空间
  • 左边界：l = mid + 1，r = mid
  • 右边界：l = mid，r = mid – 1
• 万用型（准确值，左右边界值）
  • 循环条件：l < r – 1
  • 缩减搜索空间：l = mid，r = mid

mid 的选取

• mid = left + right >> 1; 或 mid = (left + right)/2;
• mid = left + (right - left)/2;有效避免了left+right过大导致整型溢出

复杂度分析

二分查找的速度相较于简单查找O(n)来说，二分查找的速度是O(logn)，因为每次查找都将要查找的范围划分了一半

找一个准确值

搜索一个数，如果存在，返回其索引，否则返回 -1。

int search(int* nums, int numsSize, int target)
{
    int left = 0, right = numsSize - 1, mid;
    while (left <= right)//注意
    {
        mid = (right + left) / 2;
        if (nums[mid] == target)
            return mid;
        else if (nums[mid] < target)
            left = mid + 1;//注意
        else
            right = mid - 1;//注意
    }
    return -1;
}

找一个模糊值（左边界）

AcWing 789. 数的范围 – AcWing

35. 搜索插入位置 – 力扣（LeetCode） (leetcode-cn.com)

int search(int* nums, int numsSize, int target)
{
    int left = 0, right = numsSize - 1, mid;
    while (left < right)//注意，如果是等于，那么当left和right相遇时，此时right = mid，如果nums[mid] >= target，那么每次if都是right = mid，将导致死循环
    {
        mid = (right + left) / 2;
        if (nums[mid] < target)//target比nums[mid]小了，那么一定不是答案，可以放心的给left赋mid+1
            left = mid + 1;//注意
        else//nums[mid]可能等于target，这是一个潜在答案，不能排除掉，因此right = mid
            right = mid;//注意
    }
    if(nums[left] == target)//循环的结束条件是left = right，要判断结束时nums[left]是否等于target，等于说明找到了，否则返回-1
        return left;
    else
        return -1;
}

找一个模糊值（右边界）

int search(int* nums, int numsSize, int target)
{
    int left = 0, right = numsSize - 1, mid;
    while (left < right)//注意
    {
        mid = (right + left + 1) / 2;//注意，加一是为了确保数组只有两个元素，left在左，right在右，如果nums[mid]<=target成立，那么每次循环left都等于mid，那么将导致是循环，解决的办法就是对mid+1
        if (nums[mid] > target)
            right = mid - 1;//注意
        else
            left = mid;//注意
    }
    if(nums[left] == target)
        return left;
    else
        return -1;
}

万用型（准确值，左右边界值）

以左边界为例

int search(int* nums, int numsSize, int target)
{
    int left = 0, right = numsSize - 1, mid;
    while (left < right - 1)//注意
    {
        mid = (right + left) / 2;
        if (nums[mid] < target)
            left = mid;//注意
        else
            right = mid;//注意
    }
    if(nums[right] < target)//循环结束后最终区间有两个值，如果最右值都小于要查找的则直接返回最右元素的索引，因为右值一定最靠近要查找的值
        return right;
    else if(nums[left] > target)//否则检查左边的值是否大于要查找的值，如果大于，那么左值最靠近要查找的值
        return left;
    else//当左边小于搜索值，右边大于搜索值时，返回搜索值最靠近的数组索引值
        return (target - nums[left] <= nums[right] - target) ? left : right;
}

查找右边界请修改代码为

        if (nums[mid] > target)
            right = mid;//注意
        else
            left = mid;//注意

‍

插值查找

该算法由算法科学家在二分查找的基础上改进而得，二分查找每次查找都是$mid = {{(high-low)}\over{2}} = low+{{1}\over{2}}(high-low)$，算法科学家在该基础上做出改进，对该公式的${1}\over{2}$做出改进，即

---

$$
mid = low+{{key -ar[low]}\over{ar[high]-ar[low]}}(high-low)//注意这里发生了截断
$$

key为待查找数，ar为数组，low为区间下限，high为区间上限

---

该算法的好处在于能有效提高算法的速度。例入ar[11] = {0，1，16，24，35，47，59，62，73，88，99}；若key = 16，按照原来的二分法，查找需要四次才能得到结果，如果使用该方法，${{key -ar[low]}\over{ar[high]-ar[low]}}={{16-1}\over{99-1}}\approx0.153$，mid = 1+0.153*(10-1) = 2(发生截断，mid为整数)，只需要两次就可以找到key值，因此该方法能有效提高查找速度。

int search(int* nums, int numsSize, int target)
{
    int left, right, mid;
    left = 0; right = numsSize - 1;

    while (left <= right)
    {
        mid = low + (target - nums[left])*(right - left)/(nums[right] - nums[left]);
        if (nums[mid] == target)
            return mid;

        else if (nums[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

该方法对于数组中数据分布不均匀的情况非常有效，例如{0,1,2,2000,2001,2002，·······，99999};

串的模式匹配算法

串的模式匹配设有两个字符串S和T,设S为主串，也称正文串;设T为子串，也称为模式。在主串s中查找与模式T相匹配的子串，如果匹配成功，确定相匹配的子串中的第一个字符在主串S中出现的位置。
著名的模式匹配算法有BF算法和KMP算法、下面详细介绍这两种算法。

BF算法

BF(brute force)

//介绍：给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle
//字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1。
/*在一些数据结构的书籍中的BF算法具有以下bug
1.主串：""  子串：""   返回值:0
2.主串："a"  子串：""   返回值:0
3.主串：""  子串："a"   返回值:0
*/
int BruteForce(char* haystack, char* needle, int pos)//haystack主串， needle子串， pos主串开始查找位置
{
    int n = strlen(haystack), m = strlen(needle);
    int i = pos, j = 0;
    while (i < n && j < m)
    {
        if (haystack[i] == needle[j])
        {
            i++;
            j++;
        }
        else
        {
            i = i - j + 1;//指针回溯
            j = 0;
        }
        if (j == m)
            return i - j;
    }
    return -1;
}

//力扣上所给出的算法，解决了以上bug，并且和标准库的char *strstr()函数的返回值类型基本一致,标准库的strstr遇到主子串都是空串的情况，返回一个空地址，遇到子串是空串的情况也是返回一个空地址
int strStr(char * haystack, char * needle)
{
    int n = strlen(haystack), m = strlen(needle);
    for(int i = 0; i <= n - m; i++)
    {
        bool matching = true;
        for(int j = 0; j<m; j++)
        {
            if(haystack[i+j] != needle[j])
                matching = false;
        }
        if(matching == true)
            return i;
    }
    return -1;
}

KMP算法

KMP（Knuth-Morria-Pratt），该算法相对于 Brute-Force（暴力）算法有比较大的改进，主要是消除了主串指针的回溯，利用匹配失败后的信息，减少了子串与主串的匹配次数，从而使算法效率有了某种程度的提高。

算法详解，视频讲解

前提知识

前缀：对于一个长度为n的字符串，除了最后一个字符以外的由0~i的字符串，称为该字符串的前缀，例如："abza"的前缀有"a","ab","abz"

后缀：对于一个长度为n的字符串，除了第一个字符以外的由1~n的字符串，称为该字符串的后缀，例如："abza"的后缀有"a","za","bza"

最大公共前后缀：是前缀字符串和后缀字符串的最长相同字符串，例如："abzbab"的最大公共前后缀为："ab",长度为2

next数组：匹配数组，是子串匹配失败后指针指向下个滑动位置。

next[i]存储的是S串（主串）前i个字符（S[0] ~ S[i-1] 这段字串）的最大公共前后缀的长度，例如：

模串： a b z b a b
next：-1 0 0 0 0 1 2

//KMP算法next数组计算
int *getNext(char *T){
    int m = strlen(T);
    int *next = new int[m+1] {-1}; // 数组要大一点防止++i越界

    int i = 0, j = -1;
    while (i < m){
        if (j == -1 || T[i] == T[j])
            next[++i] = ++j; // 可以把指针j看作是一个cnt计数，当没有公共前后缀时，j指针回到起点位置
        else
            j = next[j];
    }
    return next;
}

//KMP算法
int kmp(char* haystack, char* needle, int pos = 0){
    int n = strlen(haystack), m = strlen(needle);
    int *next = getNext(needle);//计算next数组

    int i = pos, j = 0; // 字符串比较要从0开始
    while (i < n && j < m){
        if (j == -1 || haystack[i] == needle[j])//与BF算法不同点
            i++, j++;
        else
            j = next[j];//与BF算法不同点,j回退到合适位置，i值不变

        if (j == m)
            return i - m; // 如果不return，需要寻找所有出现位置请使用 j = next[j]
    }
    return -1;
}

默认数组下标从0开始

next数组改进

我们将next数组改进后的数组称为nextVal数组

改进原因：假设

主串S：aaaabcdef
子串T：aaaaax
next[]: -1 0 1 2 3 4

由以上可知，在i = 4, j = 4时候，S[i] != T[j]，发生匹配失败，那么j自然要回退到j = next[j] = 3, 如下图所示，直到回退到j = 0为止，而由于T串的1,2,3,4字符a都与0号字符a相同，那么就可以直接回退到j = 0，可以省略下图的②③④⑤步骤，由此我们对next数组做出改进

bilibili视频讲解

//KMP算法next数组改进算法
int *getNextVal(char *T)
{
    int m = strlen(T);
    int *nextval = new int[m+1] {-1};
    int i = 0, j = -1;
    while (i < m){
        if (j == -1 || T[i] == T[j]){
            i++; j++;
        //----------------修改位置-----------------
            if(T[i] != T[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        //----------------修改位置-----------------
        }
        else
            j = nextval[j];
    }
    return nextval;
}

其他算法

汉诺塔算法

(122条消息) 多柱汉诺塔问题浅析——算法及公式推导li-ucas的博客-CSDN博客汉诺塔递推公式及推导过程

1. 将r个圆盘移到其他非目标柱上，需要$F_M(r)$步
2. 将余下的N−r个圆盘移至目标柱，需要$F_{M-1}(N-r)$步
3. 将r个圆盘移至目标柱，需要$F_M(r)$步

给定一个汉诺塔，从左到右分别标记为A, B, C柱，现在在A柱上从上到下依次有n个圆盘，从1~n，且大小严格递增，要求将A柱上的全移动到C柱，且不改变顺序，请设计算法实现

基本实现思路：例如A栈上有n个圆盘

• 将A上的n-1移动到B，此时C做辅助
• 将A上的第n个移动到C
• 然后B栈上的n-1个移动到C，此时A做辅助

#include <iostream>
#include <stack>
#define Size 10
using namespace std;
int cnt = 0;

//移动单个元素
void move(stack<int> &A, stack<int> &C)
{
    cnt++;
    C.push(A.top());
    A.pop();
}

//汉诺塔算法
void hanoi(int n, stack<int> &A, stack<int> &B, stack<int> &C)
{
    if (n == 1)
        move(A, C);
    else
    {
        hanoi(n - 1, A, C, B); //将A上的n-1移动到B，此时C做辅助
        move(A, C);            //将A上的第n个移动到C
        hanoi(n - 1, B, A, C); //然后B栈上的n-1个移动到C，此时A做辅助
    }
}

//输出到屏幕
void show(char ch, stack<int> temp)
{
    cout << ch << ": ";
    while (!temp.empty())
    {
        cout << temp.top() << ' ';
        temp.pop();
    }
    cout << endl;
}

int main()
{
    stack<int> A, B, C;
    for (int i = Size; i > 0; i--)
        A.push(i);

    show('A', A);
    show('B', B);
    show('C', C);
    cout << endl;
    hanoi(Size, A, B, C);

    show('A', A);
    show('B', B);
    show('C', C);

    cout << "移动次数：" << cnt << endl;
    system("pause");
    return 0;
}

二叉树的遍历

二叉树的遍历分为四种

• 深度优先遍历（递归法，迭代法）
  • 前序遍历
  • 中序遍历
  • 后序遍历
• 广度优先遍历
  • 层序遍历（迭代法）

1.深度优先遍历——递归

//前序遍历      中左右
void preorderTrav(BiTree *tree)
{
    if (tree)
    {
        cout << tree->data << ' ';
        preorderTrav(tree->left);
        preorderTrav(tree->right);
    }
}

//中序遍历      左中右
void inorderTrav(BiTree *tree)
{
    if (tree)
    {
        inorderTrav(tree->left);
        cout << tree->data << ' ';
        inorderTrav(tree->right);
    }
}

//后序遍历      左右中
void postorderTrav(BiTree *tree)
{
    if (tree)
    {
        postorderTrav(tree->left);
        postorderTrav(tree->right);
        cout << tree->data << ' ';
    }
}

2.深度优先遍历——迭代

前序遍历

第一种方法

前序遍历非递归访问，使用栈即可实现。首先先将根结点压入栈，而后依次将根结点的右子节点、子节点入栈，直到栈为空为止。代码如下：

void preorderTrav(BiTree *tree)
{
    stack<BiTree *>st;//用于存储父节点
    if(tree)
        st.push(tree);//保证循环能否开始
    while(!st.empty())
    {
        BiTree *node = st.top();//父节点出栈，并打印
        st.pop();
        cout << node->data << ' ';
        if(node->right)//先入栈右子节点，空节点不入栈
            st.push(node->right);
        if(node->left)//后入栈左子节点
            st.push(node->left);
        //这么写，是为了保证出栈时候是先 左子节点出栈 后 右子节点出栈，遵循前序遍历的 中左右 遍历原则
    }
}

第二种方法

也是使用栈，这种方法更贴近于递归法，当左子树遍历完后，回溯并遍历右子树。

void preorderTrav(BiTree *tree)
{
    stack<BiTree *>st;//用于存储父节点
    while(tree || !st.empty())
    {
        if(tree)//父节点存在时
        {
            st.push(tree);//父节点入栈
            cout << tree->data << ' ';
            tree = tree->left;//访问左子结点
        }
        else
        {
            tree = st.top();//回溯父节点
            st.pop();
            tree = tree->right;//右子节点
        }
    }
}

中序遍历

与前序遍历的不同点在于，中序遍历规则是 左中右；用栈来实现，就是一种循环到左终端结点时，打印该结点，然后回溯到父节点

void inorderTrav(BiTree *tree)
{
    stack<BiTree *>st;//用于存储父节点
    while(tree || !st.empty())
    {
        if(tree)//父节点存在
        {
            st.push(tree);//父节点入栈
            tree = tree->left;//访问左子节点
        }
        else//某节点不存在
        {
            tree = st.top();//回溯到父节点
            st.pop();
            cout << tree->data << ' ';//打印父节点
            tree = tree->right;//访问右子树
        }
    }
}

后序遍历

前序遍历是中左右，后序遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了

所以后序遍历只需要前序遍历的代码稍作修改就可以了，代码如下：

第一种方法

在前序遍历算法的基础上稍作改动

void postorderTrav(BiTree *tree)
{
    stack<BiTree *>st;//用于存储父节点
    if(tree)
        st.push(tree);//保证循环能否开始
    vector<char> result;//存储后序遍历结果

    while(!st.empty())
    {
        BiTree *node = st.top();//父节点出栈，并打印
        st.pop();
        result.push_back(node->data);
        if(node->left)//后入栈左子节点，空节点不入栈
            st.push(node->left);
        if(node->right)//先入栈右子节点
            st.push(node->right);
    }
    reverse(result.begin(), result.end());//翻转
    for(auto it = result.begin(); it != result.end(); ++it)
        cout << *it << ' ';
}

第二种方式

也是两个栈实现，不过这种方法的实现和递归更贴近

void postorderTrav(BiTree *tree)
{
    stack<BiTree *>temp;//用于存储父节点
    stack<char>str;//用于存储后序遍历结果

    while(tree || !temp.empty())
    {
        if(tree)//父节点存在
        {
            temp.push(tree);//父节点入栈
            str.push(tree->data);//数据入栈
            tree = tree->right;//访问右子节点
        }
        else
        {
            tree = temp.top();//右子节点不存在，回溯到父节点
            temp.pop();
            tree = tree->left;//访问左子节点
        }
    }
    while(!str.empty())//输出中序遍历结果
    {
        cout << str.top() << ' ';
        str.pop();
    }
}

也可以使用一个vector容器来存储结果，最后将vector翻转即可

    vector<char>str;//用于存储后序遍历结果
    //······
    reverse(str.begin(), str.end());//翻转数组
    for (auto it = str.begin(); it != str.end(); ++it)//输出后序遍历
        cout << *it << ' ';

迭代法的总结

上述迭代法实现的前中后序，前序遍历第二种，中序遍历，后序遍历第二种几乎相同

实践过的同学，也会发现使用迭代法实现前中后序遍历，很难写出统一的代码，不像是递归法，实现了其中的一种遍历方式，其他两种只要稍稍改一下节点顺序就可以了。

其实针对三种遍历方式，使用迭代法是可以写出统一风格的代码！

接下来介绍一下统一写法。

迭代法统一写法

前序遍历

遍历方式为中左右，那么用栈存储，入栈顺序就是右左中，这样出栈顺序才是中左右

void preorderTrav(BiTree* root)
{
    stack<BiTree*> st;
    if (root)
        st.push(root);
    while (!st.empty())
    {
        BiTree* node = st.top();
        if (noder)
        {
            st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
            if (node->right)                                                   //右
                st.push(node->right);  // 添加右节点（空节点不入栈）

            if (node->left)                                                    //左
                st.push(node->left);  // 添加左节点（空节点不入栈）

            st.push(node);     // 添加中节点                                     //中
            st.push(nullptr);  // 中节点访问过，但是还没有处理，加入空节点做为标记。
        }
        else
        { // 只有遇到空节点的时候，才将下一个节点放进结果集
            st.pop();           // 将空节点弹出
            node = st.top();    // 重新取出栈中元素
            st.pop();
            cout << node->data << ' ';
        }
    }
}

中序遍历

迭代法中序遍历代码如下： (注意此时我们和前序遍历相比仅仅改变了两行代码的顺序)

void inorderTrav(BiTree* root)
{
    stack<BiTree*> st;
    if (root != nullptr)
        st.push(root);
    while (!st.empty())
    {
        BiTree* node = st.top();
        if (node != nullptr)
        {
            st.pop();
            if (node->right)        //右
                st.push(node->right);

            st.push(node);          //中
            st.push(nullptr);

            if (node->left)         //左
                st.push(node->left);
        }
        else
        {
            st.pop();
            node = st.top();
            st.pop();
            cout << node->data << ' ';
        }
    }
}

后序遍历

后续遍历代码如下： (注意此时我们和中序遍历相比仅仅改变了两行代码的顺序)

void postorderTrav(BiTree* root)
{
    stack<BiTree*> st;
    if (root != nullptr)
        st.push(root);
    while (!st.empty())
    {
        BiTree* node = st.top();
        if (node != nullptr)
        {
            st.pop();

            st.push(node);          //中
            st.push(nullptr);

            if (node->right)        //右
                st.push(node->right);

            if (node->left)         //左
                st.push(node->left);
        }
        else
        {
            st.pop();
            node = st.top();
            st.pop();
            cout << node->data << ' ';
        }
    }
}

3.层序遍历

层序遍历，使用一个队列来实现，如下执行步骤所示

1. 第i层入队
2. 计算第i层节点数j
3. 由第i层节点数来循环打印第i层的各个节点存储的值，每打印一个，出队一个
4. 将第i层的左数第1~j个结点的左右子节点分别入队
5. 循环上述2~4步骤

void levelorderTrav(BiTree *tree)
{
    queue<BiTree *>que;
    if (tree)//确保循环可以开始
        que.push(tree);

    while (!que.empty())
    {
        int size = que.size();//在for循环中que.size()会随着que.pop()的改变而改变
        for (int i = 0; i < size; i++)
        {
            BiTree *node = que.front();
            que.pop();
            cout << node->data << ' ';
            if (node->left)//当前结点的左子结点分别入队
                que.push(node->left);
            if (node->right)//当前结点的右子结点分入队
                que.push(node->right);
        }
        cout << endl;//打印一层后换行加以区分
    }
}

贪心算法

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

这么说有点抽象，来举一个例子：

例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？

指定每次拿最大的，最终结果就是拿走最大数额的钱。

每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

其实这个分的有点细了，真正做题的时候很难分出这么详细的解题步骤，可能就是因为贪心的题目往往还和其他方面的知识混在一起。

实际上，贪心没有套路，说白了就是常识性推导加上举反例。

如何验证可不可以用贪心算法呢？

最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

最短路

(79条消息) 最短路算法总结（超详细~）wmy0217的博客-CSDN博客_最短路算法

dijkstra算法

用点来进行松弛操作

• 每次从未标记的节点中寻找距离出发点最近的节点，标记，收录到最优路径集合中
• 计算刚加入的节点A到相邻节点B的距离，不包括已标记的节点
• 若 节点A到源点的距离 + 节点A到节点B的边长 < 节点B到源点的距离，更新节点B到源点的值
• 重复以上步骤，直到未标记的节点未空时，停止算法

【算法】最短路径查找—Dijkstra算法_哔哩哔哩_bilibili

void dijkstra(int dist[], bool st[], int grid[][N])
{
    dist[x] = 0;
    for(int i = 1; i<=n; i++)
    {
        int t = -1;//标记最小权值点
        for(int j = 1; j<=n; j++)//寻找最小权值点
            if(st[j] == false && (t == -1 || dist[j] < dist[t]))
                t = j;
        st[t] = true;
        for(int j = 1; j<=n; j++)
            dist[j] = min(dist[j], dist[t] + grid[t][j]);
    }
}

dijkstra稀疏图

当节点个数非常大，且属于稀疏图时使用

链式前向星——最完美图解 – 腾讯云开发者社区-腾讯云 (tencent.com)

堆优化

Dijkstra算法堆优化详解 – Seaway-Fu – 博客园 (cnblogs.com)

dijkstra的时间复杂度为O(N^2)原因在于每次都需要遍历寻找最小的节点，使用优先队列，就可以解决这个问题

struct edge{
    int to, w, next;
}edges[N];
int head[N];
typedef pair<int, int> PII;

void dijkstra(){
    memset(dist, INF, sizeof(dist));
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> que;
    que.push({0, 1}); // first存权值，second存点的编号
    while(!que.empty()){
        auto p = que.top(); que.pop();
        int w = p.first, v = p.second;
        if(st[v]) continue;

        st[v] = true;
        for(int i = head[v]; i!=-1; i = edges[i].next){
            int e = edges[i].to;
            if(dist[e] > w + edges[i].w){
                dist[e] = w + edges[i].w;
                que.push({dist[e], e});
            }
        }
    }
}

最短路路径

使用一个额外的数组来标记当前节点的前一个节点，就可以知道最短路径经过了那些节点，不过该数组只标记了前一个节点，于是只能由终点向前推到，即终点的前一个节点为k，k的前一个节点为m，依次类推，直到到达源点，即可得到最短路径中间节点

Bellman-ford算法

用边进行松弛操作

302 最短路 Bellman-Ford 算法 SPFA 算法_哔哩哔哩_bilibili

优点

• 和dijkstra不同的是，BF算法可以解决负环的最短路径问题，同时可以判断负环是否存在。
• 环：从某个顶点出发、经过若干个不同的顶点，可以回到该顶点的情况。
• 零环、正环、负环

思路讲解

1. 初始化源点s到各个点v的路径dis[v] = ∞，dis[s] = 0。
2. 进行n – 1次遍历，每次遍历对所有边进行松弛操作，满足则将权值更新。
   松弛操作：以a为起点，b为终点，ab边长度为w为例。dis[a]代表源点s到a点的路径长度，dis[b]代表源点s到b点的路径长度。如果满足下面的式子则将dis[b]更新为dis[a] + w。

• dis[b] > dis[a] + w
  3. 遍历都结束后，若再进行一次遍历，还能得到s到某些节点更短的路径的话，则说明存在负环路。

  理由在于：对于给定n个节点的图，从i到j，最短路径至多有n-1条路径，当出现n条路径时，说明在该条路径上至少存在一个环，也就是如果在进行一次遍历，如果节点的最短路径还能得到更新，那么只有环存在时，才会更新路径

struct edge{
    int v, w;//v是出边，w是当前点到出边v的权值
};

vector<edge> e[maxn];
int dis[maxn];
const int inf = 0x3f3f3f3f;

bool bellmanford(int s)
{
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    bool flag; // 判断一轮循环过程中是否发生松弛操作
    for (int i = 1; i <= n; i++)//至多遍历n-1次得到最短路径
    {
        flag = false;
        for (int u = 1; u <= n; u++)//依次遍历每一个点
        {
            if (dis[u] == inf)//当前点到源点还不存在路径时，不更新该点，理由如下
                continue;// 无穷大与常数加减仍然为无穷大，因此最短路长度为 inf 的点引出的边不可能发生松弛操作
            for (auto ed : e[u])//遍历当前点的所有邻边
            {
                int v = ed.v, w = ed.w;
                if (dis[v] > dis[u] + w)
                {
                    dis[v] = dis[u] + w;
                    flag = true;//存在松弛操作，打上标记
                }
            }
        }
        if (!flag)// 没有可以松弛的边时就停止算法
            break;
    }
    // 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个【负环】
    return flag;
}

• 环的判断：当返回值为true时，说明由起点s，可以抵达一个负环，同时如果返回值为false，只能说明由起点s开始的路径没有负环存在，但是这并不代表该图种就没有环

链式前向星版本

struct edge{
    int to, next, w;
}edges[M];
int dist[N];

void bellman_ford(int s){
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    for(int k = 1; k<=n; k++){//至多n次迭代
        for(int u = 1; u<=n; u++){//遍历每一个点
            for(int i = edges[u]; i != -1; i = edges[i].next){//遍历每一个点的所连接的边
                int v = edges[i].to, w = edges[i].w;//v是与u相接的点
                dist[v] = min(dist[v], dist[u] + w);
            }
        }
    }
}

由于bellman-ford的特殊性质，也可以使用其他存边方式，例如

struct edge{
    int a, b, w;//使用a存始点，b存终点，w存权值
}edges[M];
int dist[N];

void bellman_ford(int s){
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    for(int i = 1; i<=n; i++){//至多n次迭代
        for(int j = 0; j<m; j++){//遍历所有边
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], dist[a] + w);
        }
    }
}

例题：AcWing 853. 有边数限制的最短路 – AcWing

SPFA算法

视频资源：和bellman-ford是同一个

全称：Shortest Path Faster Algorithm,SPFA是bellman-ford队列优化算法的别称。

在bellman-ford算法的松弛操作中，只有本轮被更新的点，其出边从有可能引起下一轮的松弛操作，因此在这里可以使用队列来维护被更新的点的集合。很多时候我们并不需要那么多无用的松弛操作。

即：只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。那么我们用队列来维护“哪些结点可能会引起松弛操作”，就能只访问必要的边了。

算法流程：

vis[u]标记u点是否在队内，cnt[v]记录边数，判定以s为源点负环是否存在。

• 初始化，s入队，标记s在对内，d[s]=0，d[其他点]=无穷大
• 从队头弹出u点，标记u不在队内
• 枚举u的所有出边，执行松弛操作，记录从s走到v的边数，并判定负环。如果v不在队内，则把v压入队尾，并打上标记；
• 重复2、3步骤，直到队列为空

struct edge{
    int v, w;//出边，权值
};
vector<edge>edges[M];
int vis[N], dist[N], cnt[N];//vis标记是否在队列，dist最短距离，cnt边数
bool spfa(int s){
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    vis[s] = true;
    queue<int>que;
    while(!que.empty()){
        int u = que.top(); que.pop();
        vis[u] = false;
        for(auto eq : edges[u]){
            int v = eq.v, w = eq.w;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                cnt[v] = cnt[u] + 1;//更新到v的路径，边数+1
                if(cnt[v] >= n)//根据抽屉原理，以s为起点一定存在一个负环
                    return true;
                if(!vis[v])//该点可以被松弛，即该点的出边也会被松弛，入队
                    que.push(v), vis[v] = true;
            }
        }
    }
    return false;
}

链式前向星

int dist[N], vis[N], head[N], cnt = 1;
struct edge{
    int to, next, w;
}edges[M];

void add(int a, int b, int w){
    edges[cnt].to = b, edges[cnt].w = w, edges[cnt].next = head[a], head[a] = cnt++;
}

void spfa(){
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    queue<int> que;
    que.push(1);
    vis[1] = true;

    while(!que.empty()){
        int v = que.front(); que.pop();
        vis[v] = false;
        for(int k = head[v]; k != -1; k = edges[k].next){
            int u = edges[k].to, w = edges[k].w;
            if(dist[u] > dist[v] + w){
                dist[u] = dist[v] + w;
                if(!vis[u])
                    que.push(u), vis[u] = true;
            }
        }
    }
}

floyd算法

设定矩阵$A_{n*n}$，其中

$$
a_{ij}=\left{
\begin{matrix}0,i=j
\c_{i,j}, (i,j)\in E
\ \infty , (i,j)\notin E
\end{matrix}\right.
$$

视频讲解：​最短路径（二）Floyd算法_哔哩哔哩_bilibili

• 解决图中任意点到某一点之间的最短路问题，例如P点到M点，中间可以直达也可以经过其他点到达

在视频中拓展：

• $A_{n*n}$矩阵依据公式$a_{ij} = min(a_{ij},a_{ik} + a_{kj})$迭代n次后得到i到j的最短路径，但是得不到经过那些点，可以用一个额外的数组来记录经过的点，在视频讲解的末尾位置

  例如：i到节点j经过k节点，那么在额外的二维数组中，P[i][j] = k，然后在检查P[i][k]是否存在节点，P[k][j]是否存在节点，重复这一过程，得到所有中间节点

• $A_{n*n}$矩阵依据公式$a_{ij} = min(a_{ij},max(a_{ik}, a_{kj}))$可以得到i到j的所有通路集合中的通路的最大边的的最小值，就是在这一堆通路中，每条通路都有一条最大的边，在将这些边中的最小值取出

  例题：

  • 4240. 青蛙 – AcWing题库
  • 4241. 货物运输 – AcWing题库（青蛙题的相反题）

//针对无向图
void floyd(){
    //设k为中间节点，检查从i到j的距离和i到k，k到j（即以k作为中间节点绕行）的距离
    for(int k=0; k<n; k++){
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                grid[i][j] = grid[j][i] = min(grid[i][j], grid[i][k] + grid[k][j]);
            }
        }
    }
}

最小生成树

定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。

注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。

给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

• kruskal 时间复杂度 O(mlogm)，适合稀疏图
• prim时间复杂度O(n^2)，适合稠密图

Kruskal算法

在不构成环的情况下，在图中寻找权值最小的边，如此往复

Kruskal （克鲁斯克尔）算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。

使用：并查集、图的存储、贪心

例题：4291. 丛林之路 – AcWing题库

时间复杂度：O(mlogm)（m是边数）

流程

• 将所有边按权值从小到大排序，时间复杂度O(mlogm)
• 依次遍历所有边，如果某边的两点不构成回路，即加入最短路径集合
• 统计最短路径集合中的边个数，如果小于n-1，即不构成最小生成树，等于n-1，即可构成最小生成树

struct edge{
    int a, b, w;//始点，终点，权
}edges[M];
int p[N], cnt;
void add(int a, int b, int w){
    edges[cnt].a = a, edges[cnt].b = b, edges[cnt].w = w, cnt++;
}

int find(int x){
    if(p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

int kruskal(){
    for(int i = 1; i<=n; i++) p[i] = i;
    sort(edges, edges + cnt);
    int sum = 0, en = 0;//权值和，路径条数
    for(int i = 0; i<cnt; i++){
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        int pa = find(a), pb = find(b);
        if(pa != pb){
            p[pa] = pb;
            sum += w;
            en++;
        }
    }
    if(en < n - 1){
        cout << "无法构成最小生成树";
        return -1;
    }
    return sum;
}

prim算法

以某顶点为起点，找到最小的边，如此反复

Prim （普里姆）算法是另一种常见并且好写的最小生成树算法。该算法的基本思想是从一个结点开始，不断加点（而不是 Kruskal 算法的加边）。具有贪心的思想。

具体来说，每次要选择距离集合（已访问点集合）最小的一个结点，以及用新的边更新其他结点的距离。

其实跟 Dijkstra 算法一样，每次找到距离最小的一个点，可以暴力找也可以用堆维护。

堆优化的方式类似 Dijkstra 的堆优化，但如果使用二叉堆等不支持 decrease-key 的堆，复杂度就不优于 Kruskal，常数也比 Kruskal 大。所以，一般情况下都使用 Kruskal 算法，在稠密图尤其是完全图上，暴力 Prim 的复杂度比 Kruskal 优，但 不一定 实际跑得更快。

时间复杂度：O(n^2)

流程

• 初始化：dist[N]为所有点到集合的距离，初始化为无穷大
• 任选一个点，然后将该点加入最短路集合
• 寻找距离到最短路集合最近的点，同时将该点加入最短路集合中
• 遍历该点的邻接点，更新邻接点到集合的距离dist
• 重复三四步骤，n次循环，即遍历n个点，得到最小生成树

int grid[N][N], n, m;
int dist[N], vis[N];

int prim(){
    memset(dist, 0x3f, sizeof(dist));

    int sum = 0;
    for(int i = 0; i<n; i++){
        int t = -1;
        for(int j = 1; j<=n; j++){
            if(!vis[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        vis[t] = true;
        //如果该点非第一个点，但是该点到集合的距离是无穷大，也就是说该点是孤立出来的
        if(i && dist[t] == INF)
            return INF;

        if(i)//该点非第一个点
            sum += dist[t];

        for(int j = 1; j<=n; j++)
            dist[j] = min(dist[j], grid[t][j]);
    }   
    return sum;
}

思路详解

在每一次选择一个点加入最小生成树集合中后，都会更新该点的所有邻接点到集合的距离，我们只要维护dist这个距离就可以得到答案，例如

第一次循环：在选取第一个点的时候，t = 0，vis[0]==true，更新了该点的所有邻接点到0点的距离

第二次循环：选取了到0点最近的一个点，加入最小生成树集合，更新该点的所有邻接点到该点的距离

重复n次循环，也就是n个点，值得注意的是，我们每次选取的都是这个集合的所有邻接点，而这些邻接点都被更新过了，因此是可以得到答案的。

同时：还需要注意，如果在除开第一次选的点以外的点中，找到一个到集合距离无穷大的点，那么也就是说这个点是孤立点，一定是无法构成最小生成树的，即可返回impossible

筛质数

埃氏筛

时间复杂度: $O(nloglogn)$，每个数可能被标记多次

void get_primes(){
    memset(vis, false, sizeof(vis));
    for(int i=2; i<=n; i++){
        if(!vis[i]){
            primes[cnt++] = i; //把素数存起来
            for(int j=i; j<=n; j+=i) //筛掉i的倍数
                st[j]=true;
        }
    }
}

欧拉筛（线性筛）

时间复杂度: $O(n)$，每一个数只被标记了一次

算法学习笔记(17): 筛素数 – 知乎 (zhihu.com)

疑问

• 为什么当数x被质数表中的一个数整除时，停止向下筛选呢？

  举例：对于质数表（2，3），当前遍历到4，那么12应不应该被4筛掉？答案是不应该，原因在于4 = 2 X 2p（p=1，2，3···），而12 = [2] X 6 = [3] X 4（方括号内是质数），而由线性筛的定义：某个数 = 最小的质数 X 一个数，只有2才符合，因此，不应该被4筛选掉，同时，线性筛可以保证每个数只被筛选一次，那么，如果4把12筛选掉，那么6又会把12筛选掉，12就被筛选了两次，可见是不合理的

bool isnp[MAXN];
vector<int> primes; // 质数表
void init(int n)
{
    memset(isnp, true, sizeof(isnp));
    for (int i = 2; i <= n; i++)//依次检查2到n是否为质数
    {
        if (isnp[i])//是质数添加进质数表
            primes.push_back(i);
        for (int p : primes)//遍历质数表
        {
            if (p * i > n)//超出n范围跳出, 这一步可以简化到for循环中
                break;
            isnp[p * i] = false;//剔除可以被分解的质数
            if (i % p == 0)
                break;
        }
    }
}

拓扑序列

AOV网和AOE网

AOV网

定义：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网（Activity On Vertex Network）,AOV网中的弧表示活动之间的某种约束关系。AOV网是有向无圈的图。

AOE网

定义：在一个表示工程的带权有向图中，用顶点表示事件，用弧表示活动，用弧上的权值表示活动持续的时间，这种有向图的弧表示活动的网，我们称为AOE网（Activity On Edge Network），AOE网中没有入度的顶点称为始点或源点，没有出度的顶点叫做终点或汇点。

不同之处

它们都是用来对工程建模的，但它们还是有很大的区别，主要体现在AOV网是顶点表示活动的网，它只描述了活动之间的约束关系，而AOE网是用有向边表示活动，边上的权值表示活动持续的时间。

AOE网只能有一个入度为0的点，称为开始顶点（源点），一个出度为0的点，称为结束顶点（汇点），而AOV网可以有多个。

路径各个活动所持续的时间之和称为路径长度，从源点到终点具有最大路径长度的路径叫做关键路径，在关键路径上的活动叫做关键活动。

AOE网也用邻接表结构，与AOV网邻接表不同的是，AOE网的邻接表中增加了weight域，用来存储弧的权值。

拓扑序列

拓扑排序详解 通俗易懂 – 知乎 (zhihu.com)

若一个由AOV网图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

数据结构的选择：使用邻接表 + 栈或队列

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5+10;
struct edge{
    int to, next;
}edges[N];

int head[N], cnt[N], output[N], n, m, idx = 1;

int tosort(){
    queue<int> st;
    for(int i = 1; i<=n; i++){
        if(!cnt[i])
            st.push(i);
    }
    int tt = 0, dd = 1;
    while(!st.empty()){
        int top = st.front(); st.pop();
        output[dd++] = top;
        tt ++;
        for(int i = head[top]; i!=-1; i = edges[i].next){
            int u = edges[i].to;
            cnt[u]--;
            if(cnt[u] == 0)
                st.push(u);
        }
    }
    return tt;
}

int main(){
    cin >> n >> m;
    memset(head, -1, sizeof(head));
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i<m; i++){
        int a, b;
        cin >> a >> b;
        edges[idx].to = b, edges[idx].next = head[a], head[a] = idx++;
        cnt[b]++;
    }

    if(tosort() != n)
        cout << -1;
    else
        for(int i = 1; i<=n; i++)
            cout << output[i] << ' ';

    return 0;
}

二分图

二分图，又称二部图，英文名叫 Bipartite graph。

二分图是什么？节点由两个集合组成，且两个集合内部没有边的图。

换言之，存在一种方案，将节点划分成满足以上性质的两个集合。如下图：

​

另外一种定义方法：

• 把一个图定义为G = <u, v, m>，其中u和v是节点的集合，m是边的集合
• 集合u和集合v中的所有边都在集合m中
• 集合u内任意两点没有边
• 集合v内任意两点没有边

二分图的性质

• 二分图不一定是连通图
• 二分图没有奇数条边的环，反正没有奇数条边的环的图，一定是二分图

  以三个点两两相连的图为例，是不能构成二分图的，可以使用染色法来证明。

14-1: 二部图及其判定算法 Bipartite Graphs_哔哩哔哩_bilibili

染色法

首先随意选取一个未染色的点进行染色，然后尝试将其相邻的点染成相反的颜色。如果邻接点已经被染色并且现有的染色与它应该被染的颜色不同，那么就说明不是二分图。而如果全部顺利染色完毕，则说明是二分图。染色结束后的情况（记录在数组中）便将图中的所有节点分为了两个部分，即为二分图的两个点集。

时间复杂度：O(n + m)

染色法可以使用dfs和bfs来实现

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5+10;
int head[N], e[N*2], ne[N*2], idx;
int c[N], vis[N], n, m;

void add(int a, int b){
    e[idx] = b, ne[idx] = head[a], head[a] = idx++;
}

bool bfs(int u){
    queue<int> que;
    que.push(u);
    c[u] = 1;
    while(!que.empty()){
        int p = que.front(); que.pop();
        if(vis[p])
            continue;
        vis[p] = true;
        for(int i = head[p]; i!=-1; i = ne[i]){
            int j = e[i];
            if(c[j] != 0 && c[j] == c[p]) // 某个点染色过，但是颜色等于领点
                return false;
            c[j] = c[p] ^ 3;
            if(!vis[j])
                que.push(j);
        }
    }
    return true;
}

bool dfs(int u, int t){
    c[u] = t;
    for(int i = head[u]; i!=-1; i = ne[i]){
        int j = e[i];
        if(!c[j]){
            if(!dfs(j, t ^ 3))
                return false;
        } else if(c[j] == c[u])
            return false;
    }
    return true;
}

int main(){
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for(int i = 0, a, b; i<m; i++){
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    bool flag = true;
    for(int i = 1; i<=n; i++){
        if(!c[i]){
            if(!bfs(i)){
                flag = false;
                break;
            }
        }
    }
    cout << (flag ? "Yes" : "No") << endl;
    return 0;
}

匈牙利算法

匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。

漫谈匈牙利算法和增广路径

二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。

增广路径是匈牙利算法的核心，每找到一条增广路径，意味这M集合中边的数量就会增加1，当找不到增广路径的时候，这个时候M中边的数量就是我们二部图的最大匹配数量。

时间复杂度：$O(n^3)$

(101条消息) 匈牙利算法（简单易懂）一只大秀逗的博客-CSDN博客匈牙利算法

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 1e5+10;
int head[N], e[M], ne[M], idx;
int match[N], vis[N], n1, n2, m;

void add(int a, int b){
    e[idx] = b, ne[idx] = head[a], head[a] = idx++;
}

bool find(int u){
    for(int i = head[u]; i!=-1; i = ne[i]){
        int j = e[i];
        if(!vis[j]){
            vis[j] = true;
            if(match[j] == 0 || find(match[j])){ 
                // 如果当前女生没有男朋友，或者可以为这个这个女生的男朋友寻找到备胎，就将当前女生分配给当前男生
                match[j] = u;
                return true;
            }
        }
    }
    return false;
}

int main(){
    memset(head, -1, sizeof(head));
    cin >> n1 >> n2 >> m;
    for(int i = 0; i<m; i++){
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    int res = 0; // 对每一个男生寻找女朋友
    for(int i = 1; i<=n1; i++){
        memset(vis, 0, sizeof(vis)); 
        // 在每个男生寻找前，清空对女生的访问记录，注意，这并不会导致有两个女生选择到同一个女生，还存在match数组对女生的男朋友进行标记
        if(find(i)) res++;
    }
    cout << res;
    return 0;
}

快速幂

快速幂（平方求幂）是一种简单而有效的算法，它可以在O(log⁡n)​的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。

例如我们计算$a^n$

• 常规解法是暴力求解，即对a进行乘以（n-1）次，时间复杂度为O(n)​
• 如果我们对n进行二进制拆解，那么时间复杂度将降低为O(logn)​

二进制拆解：n可以表示为 $n = t_1 * 2^0 + t_2 * 2^1 +··· + t_{n-2} * 2^{n-2}+t_{n-1} * 2^{n-1}$，其中$t_i$为每个二进制为上为1还是为0

那么$a^n$就可以表示为$a^n =a^{ t_1 * 2^0 + t_2 * 2^1 +··· + t_{n-2} * 2^{n-2}+t_{n-1} * 2^{n-1}} = a^{ t_1 * 2^0} * a^{t_2 * 2^1} * ··· * a^{ t_{n-2} * 2^{n-2}} * a^{t_{n-1} * 2^{n-1}}$

举例计算：$a^b \mod p$

typedef long long LL;
LL qmi(LL a, LL b, LL p){
    LL res = 1;
    while(b){
        // 只对二进制位为1的进行乘积运算
        if(b & 1)
            res = res * a % p;
        // 在二进制位上，a每次扩大一倍
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

快速幂求逆元

乘法逆元

同余： 两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m。记作：$a≡b (\mod m)$

数学上的乘法逆元就是指直观的倒数，即 $a$ 的逆元是 $1 \over a$，也即与 $a$ 相乘得 1 的数。$ax=1$，则$x$是$a$的乘法逆元。

这里我们讨论取模运算的乘法逆元，即对于整数 a，与 a 互质的数 b 作为模数，当整数 x 满足 $ax≡1( \mod b)$ 时，称 x 为 a 关于模 b 的逆元，代码表示就是a * x % b == 1​。

费马小定理： 如果p是一个质数，而整数a不是p的倍数，则具有性质：$a^{p-1}≡1 ( \mod p)$

最美数学系列-什么是费马小定理以及如何证明它？，费马小定理的证明需要用到扩展欧几里得定理来证明。

由费马小定理可以推出(保证a不是p的倍数)：$a*a^{p-2} ≡ 1(\mod p)$，即$a^{p-2}$就是$a$模以$p$的乘法逆元。

// 方法一：暴力
int x, flag = 0;
for(x = 0; x<p && !flag; x++){
    if(a * x % p == 1)
        flag = 1;
}
if(flag)
    cout << x << '\n';
else
    cout << "impossible\n";

// 快速幂 + 费马小定理
cin >> a >> p;
if(a % p)
    cout << qmi(a, p-2, p) << '\n'; // qmi是求a^b % p的标准快速幂算法
else
    cout << "impossible\n";

扩展欧几里得算法

欧几里得算法

学习扩展欧几里得算法前，先介绍裴蜀定理（贝祖定理），是一个关于最大公约数的定理。

裴蜀定理： 给予任意两个整数a和b，必定存在整数x和y，使得$ax + by = \gcd(a, b)$成立。

推论： 在裴蜀定理下，如果a和b互质得$gcd(a, b) = 1$，即有$ax+by = 1$，那么有$(ax + by) \mod b = ax \mod b$，得$ax \equiv 1(\mod b)$，x又称为a模b的乘法逆元。

x和y的求解：使用扩展欧几里得算法。

方法如下

基本思路就是在求gcd(a, b)​的同时，计算x和y的值，由于gcd(a, b) = gcd(b, a % b)​，形参发生改变，那么理所应当exgcd(a, b, x, y) = exgcd(b, a % b, x1, y2)​中，x1和y2也不再是原先的值，我们需要重新计算x1和x2的结果，计算方式如下，

不过我们需要注意的是​**b == 0**​时，​**ax + 0y = gcd(a, 0)** ​是没有意义的，因此y取任意值都是可以的。为了方便起见取​y=0​

• 方式一（形参x和y互换位置）

  $$
  exgcd(a,b,x,y) = ax + by \
  exgcd(b,a\%b,y,x) = by + (a – [\frac{a}{b}]·b)x = ax + b(y-[\frac{a}{b}]· x) \
  ∴y更新为y-[\frac{a}{b}]·x
  $$

• 方式二（形参x和y不交换位置）

  $$
  exgcd(a,b,x,y) = ax + by \
  exgcd(b,a\%b,x,y) = bx + (a-[\frac{a}{b}]b)y = ay + b(x – [\frac{a}{b}]y) \
  ∴x更新为y, 同时y更新为x – [\frac{a}{b}]y
  $$

#include <iostream>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y){
    if(b){
        LL d = exgcd(b, a % b, y, x); // 需要对x和y进行交换
        y = y - a / b * x;
        return d;
    }
    x = 1, y = 0; // ax + 0y = gcd(a, 0)无意义，y可取任意值，这里取0
    return a;
}

int main(){
    LL n;
    cin >> n;
    while (n -- ){
        LL a, b;
        cin >> a >> b;
        LL x, y;
        exgcd(a, b, x, y);
        cout << x << ' ' << y << '\n';
    }
    return 0;
}

线性同余方程

形如$ax≡ b (\mod m)$的方程，已知a、b、m，求解x

线性同余方程

• 上式可转换为$ax = my + b$，进一步推到为$ax – my = b$，由扩展欧几里得定理可得$ax+my^1 = gcd(a, m)$，当且仅当$gcd(a, m) | b$时，即b是$gcd(a, m)$的任意倍，该方程有解
• 将$ax+my^1 = gcd(a, m)$转换为$ax≡ b (\mod m)$，需要对原方程左右两边同时除以$b \over \gcd(a, m)$，得到$(ax+my^1)·{b \over \gcd(a, m)} = b$，此时在两边同时模以m，即可得到答案x

int main(){
    LL n;
    cin >> n;
    while (n -- ){
        LL a, b, m, x, y;
        cin >> a >> b >> m;
        int gcd = exgcd(a, m, x, y);
        if(b % gcd)
            cout << "impossible\n";
        else
            cout << x * (b/gcd) % m << '\n';
    }
    return 0;
}

‍