数据结构与算法

1. 代码 /* * @Brief: 常见排序算法汇总 * @Author: * @Date: 2021-07-01 */ #include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; void printArray(int *a, int len){ for(int i = 0; i < len; i++) cout << a[i] << " "; cout << endl << endl; } void bubbleSort(int *a, int len){ for(int i = 0; i < len - 1; i++){ for(int j = 0; j < len - i; j++){ if(a[j] > a[j+1]) swap(a[j], a[j+1]); } } } void selectSort(int *a, int len){ for(int i = 0; i < len; i++){ int mi = i; for(int j = i; j < len; j++){ if(a[j] < a[mi]) mi = j; } if(i != mi) swap(a[i], a[mi]); } } void insertionSort(int *a, int len){ for(int i = 0; i < len;...

1. 单调栈 1.1 可解决的问题 单调栈的使用场景时分有限，只处理一种典型的问题，叫做 Next Greater Element。 例如：在一个数组中，每个数左边（右边）第一个比它大（小）的数是什么。 1.2 详解 直接上例子解释它。 题目：给出一个原始数组 a[3, 4, 2, 7, 5]，输出每个数左边第一个比它小的数，如果不存在则输出-1。 解释...

0. 欧几里得算法 欧几里得算法用于求解两个数的最大公约数。代码如下: int gcd(int a, int b){ if(b == 0) return a; return gcd(b, a % b); } 当b为0时，结束递归，此时a即为a和b的最大公约数。 1. 裴蜀定理 定理内容： 如果a、b均是整数，则一定存在整数x和y，使得ax + by = gcd(a, b)成立。 我们可以再深层次的理解一下式子ax + by = gcd(a, b...

模板代码： typedef long long ll; ll quick_pow(ll a,ll b){ ll res = 1; while(b > 0){ if(b & 1){ res *= a; } a *= a; b >>= 1; } return res; } 这里以a^10为例，说一下对快速幂代码的理解。 右下角的o表示这是十进制数 这里写错了，图片中不应该是o，应该d，d表示这是十进制数 ，b表示这是二进制数。可以得到以下的几个式子，都是逐步变换得出来的。 最后一个式...