算法总结
排序算法
分类
时间复杂度
算法稳定性：在一组待排序记录中，如果存在任意两个相等的元素，我们标记为 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; } } }
堆排序
基础
堆的实现是在完全二叉树上来实现
堆的种类
- 大根堆
对任意节点来说，根节点的值大于左子节点和右子节点 - 小根堆
对任意节点来说，根节点的值小于左子节点和右子节点
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 里到底用 <= 还是 <。
基本原则
- 每次都要缩减搜索区域
- 每次缩减不能排除潜在答案
三大模板
- 找一个准确值
- 循环条件 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; }
找一个模糊值（左边界）
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 数组做出改进
//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 博客汉诺塔递推公式及推导过程
- 将 r 个圆盘移到其他非目标柱上，需要 $F_M (r)$ 步
- 将余下的 N−r 个圆盘移至目标柱，需要 $F_{M-1}(N-r)$ 步
- 将 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. 层序遍历
层序遍历，使用一个队列来实现，如下执行步骤所示
- 第 i 层入队
- 计算第 i 层节点数 j
- 由第 i 层节点数来循环打印第 i 层的各个节点存储的值，每打印一个，出队一个
- 将第 i 层的左数第 1~j 个结点的左右子节点分别入队
- 循环上述 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 算法可以解决负环的最短路径问题，同时可以判断负环是否存在。
- 环：从某个顶点出发、经过若干个不同的顶点，可以回到该顶点的情况。
- 零环、正环、负环
思路讲解
- 初始化源点 s 到各个点 v 的路径
dis[v] = ∞，dis[s] = 0。 - 进行 n – 1 次遍历，每次遍历对所有边进行松弛操作，满足则将权值更新。
松弛操作：以 a 为起点，b 为终点，ab 边长度为 w 为例。dis [a] 代表源点 s 到 a 点的路径长度，dis [b] 代表源点 s 到 b 点的路径长度。如果满足下面的式子则将dis[b]更新为dis[a] + w。
dis[b] > dis[a] + w- 遍历都结束后，若再进行一次遍历，还能得到 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 的所有通路集合中的通路的最大边的的最小值，就是在这一堆通路中，每条通路都有一条最大的边，在将这些边中的最小值取出
例题：
//针对无向图 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 发明。该算法的基本思想是从小到大加入边，是个贪心算法。
使用：并查集、图的存储、贪心
时间复杂度：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 域，用来存储弧的权值。
拓扑序列
若一个由 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(logn)的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。例如我们计算 $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; }
