// 每次选出[i, n]中最小的元素, 不稳定 voidselectSort(vector<int>& vec){ int n = vec.size(); for (int i = 0; i < n; ++i) { int k = i; for (int j = i; j < n; ++j) { if (vec[j] < vec[k]) { k = j; } } swap(vec[k], vec[i]); } }
直接插入排序
1 2 3 4 5 6 7 8 9 10 11 12
voidinsertSort(vector<int>& vec){ int n = vec.size(); for (int i = 1; i < n; ++i) { int temp = vec[i], j = i; // 找到插入的位置 while (j > 0 && temp < vec[j - 1]) { vec[j] = vec[j - 1]; j--; } vec[j] = temp; } }
inthashFunc(char S[], int len){ int id = 0; for (int i = 0; i < len; ++i) { id = id * 26 + (S[i] - 'A'); // 转换为26进制表示 } return id; }
如果出现小写字母, 则变为52进制
出现数字, 变为62进制
3 | 二分
递归和贪心比较简单, 这里略过
经典的二分查找: 如何在一个严格递增序列A中找出给定的数x
二分查找代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
// 二分法在有序vec中寻找x, 返回值为x的下标, 如果没找到返回-1 intbinarySearch(vector<int>& vec, int x){ int left = 0, right = vec.size() - 1; int mid; while (left <= right) { mid = left + ((right - left) >> 1); // 防止溢出 if (vec[mid] == x) return mid; elseif (vec[mid] > x) { right = mid - 1; } else { left = mid + 1; } } return-1; }
upper_bound 和lower_bound
关于lower_bound和upper_bound函数的实现:
lower_bound用于寻找第一个大于等于x的元素
upper_bound用于寻找第一个大于x的元素
lower_bound的实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
// 第一个大于等于x的元素下标 intlowerBound(vector<int>& vec, int x){ int left = 0; int right = vec.size(); //加入x比所有元素都大, 应当返回vec.size() int mid; while (left < right) { mid = left + ((right - left) >> 1); if (vec[mid] >= x) { right = mid; } else { left = mid + 1; } } return left; }
upper_bound的实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
// 第一个大于x的元素下标 intupperBound(vector<int> &vec, int x){ int left = 0, right = vec.size(); int mid; while (left < right) { mid = left + ((right - left) >> 1); if (vec[mid] > x) { right = mid; } else { left = mid + 1; } } return left; }
解决这类问题(寻找有序序列第一个满足某条件元素的位置)题目的写法:
1 2 3 4 5 6 7 8 9 10 11 12
intsolve(int left, int right){ int mid; while (left < right) { mid = (left + right) / 2; if (条件成立) { // 条件成立, 第一个满足条件的元素位置 <= mid right = mid; } else { // 条件不成立, 第一个满足条件的元素位置 > mid left = mid + 1; } } return left; }
快速幂
基本问题:
给定三个整数a, b, m, 求$\mathrm{a}^{\mathrm{b}}\%\mathrm{m}$
直接暴力的写法:
1 2 3 4 5 6 7
llpow(longlong a, longlong b, longlong m) { longlong ans = 1; for (int i = 0; i < b; ++i) { ans = ans * a % m; } return ans; }
longlongbinaryPow(longlong a, longlong b, longlong m){ if (b == 0) return1; if (b & 1) return a * binaryPow(a, b - 1, m) % m; // b为奇数 else { // b为偶数 // 先计算mul = binaryPow而不要使用binaryPow * binaryPow的形式, 否则时间复杂度将变为O(b) longlong mul = binaryPow(a, b / 2, m); return mul * mul % m; } }
binaryPow(longlong a, longlong b, longlong m) { longlong ans = 1; while (b > 0) { if (b & 1) { ans = ans * a % m; } a = a * a % m; b >>= 1; } return ans; }