# 常用算法
# 内容总览
打钩的是讲到的,其他的是算法竞赛中建议学习的,不在下面列出的在比赛中基本用不到。
(很多函数的功能很简单,自己都能快速写出来,但是使用函数可以让代码可读性变得更高,这在比赛中是至关紧要的)
- 算法库 Algorithm
- [ ]
count()
- [ ]
find()
- [ ]
fill()
- [x]
swap()
- [x]
reverse()
- [ ]
shuffle()
C++ 11 - [x]
unique()
- [x]
sort()
- [x]
lower_bound()
/upper_bound()
- [x]
max()
/min()
- [ ]
max_element()
/min_element()
- [ ]
prev_permutation()
/next_permutation()
- [ ]
- 数学函数 cmath
- [x]
abs()
- [x]
exp()
- [x]
log()
/log10()
/log2()
- [x]
pow()
- [x]
sort()
- [ ]
sin()
/cos()
/tan()
- [ ]
asin()
/acos()
/atan()
- [ ]
sinh()
/cosh()
/tanh()
- [ ]
asinh()
/acosh()
/atanh()
C++ 11 - [x]
ceil()
/floor()
- [x]
round()
C++ 11 (四舍五入)
- [x]
- 数值算法 numeric
- [ ]
iota()
C++ - [ ]
accumulate()
- [x]
gcd()
C++17 - [x]
lcm()
C++17
- [ ]
- 伪随机数生成 random
- [ ]
mt19937
- [ ]
random_device()
- [ ]
# swap()
交换两个变量的值
用法示例:
template<class T>
void swap(T& a, T& b);
2
int a = 0, int b = 1;
swap(a, b);
// now a = 1, b = 0
int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
swap(arr[4], arr[6]);
// now arr = {0, 1, 2, 3, 6, 5, 4, 7, 8, 9}
2
3
4
5
6
7
注意事项
这个swap参数是引用的,不需要像C语言一样取地址。
# sort()
使用快速排序给一个可迭代对象排序
用法示例
template<class Randomit, class Compare>
void sort(Randomit first, Randomit last, Compare comp);
2
默认排序从小到大
vector<int> arr{1, 9, 1, 9, 8, 1, 0};
sort(arr.begin(), arr.end());
// arr = [0, 1, 1, 1, 8, 9, 9]
2
3
如果要从大到小,则需要传比较器进去
vector<int> arr{1, 9, 1, 9, 8, 1, 0};
sort(arr.begin(), arr.end(), greater<int>());
// arr = [9, 9, 8, 1, 1, 1, 0]
2
3
如果是特殊比较,就需要自己写比较器
bool cmp(pair<int, int> a, pair<int, int> b)
{
if(a.second != b.second) //第二个值从小到大
return a.second < b.second;
return a.first > b.first;
}
int main()
{
vector<pair<int, int>> arr{{1, 9}, {2, 9}, {8, 1}, {0, 0}};
sort(arr.begin(), arr.end(), cmp);
// arr = [(0, 0),(8, 1), (2, 9), (1, 9)]
}
2
3
4
5
6
7
8
9
10
11
12
13
# lower_bound() / upper_bound()
在已升序排序的元素中,应用二分查找检索指定元素,返回对应元素迭代器位置,找不到则返回尾迭代器。
lower_bound()
:寻找的第一个元素位置upper_bound()
:寻找的第一个元素位置
怎么找或的第一个元素呢?
的第一个元素的前一个元素(如果有)便是 的第一个元素
的第一个元素的前一个元素(如果有)便是 的第一个元素
返回的是迭代器,如何转成下标索引呢?减去头迭代器即可。
用法示例
template<class Forwordit, class T>
Forwordit lower_bound(Forwordit first, Forwordit last, const T& value);
2
vector<int> arr{0, 1, 1, 1, 8, 9 ,9};
vector<int>::iterator it = lower_bound(arr.begin(), arr.end(), 7);
int idx = it - arr.begin();
//idx = 4;
2
3
4
我们通常写成一行
vector<int> arr{0, 1, 1, 1, 8, 9 ,9};
int idx = lower_bound(arr.begin(), arr.end(), 7) - arr.begin();
2
# reverse()
使一系列元素反序
template<class T>
T reverse(T first, T last);
2
注意:[first, last)
vector<int> arr{0, 1, 1, 1, 8, 9 ,9};
reverse(arr.begin(), arr.end());
// arr = [9, 9, 8, 1, 1, 1, 0]
reverse(arr.begin()+2, arr.begin()+5);
// arr = [9, 9, 1, 1, 8, 1, 0]
2
3
4
5
6
# max() / min()
获取最大值或最小值
min(1, 2); // 比较两个数
min(min(1, 3), 2); //比较三个数
min({1, 3, 2, 4}); //C++ 11及以后
2
3
4
5
# unipue()
消除数组的重复相邻元素,数组长度不变,但是有效数据缩短,返回的是有效数据位置的结尾迭代器
例如:,?位置为返回的迭代器指向。
template<class Forwardit>
Forwardit unipue(Forwardit first, Forwardit last);
2
用法示例
单独使用 unique 并不能达成去重效果,因为它只消除相邻的重复元素。但是如果序列有序,那么它就能去重了。
但是它去重后,序列尾部会产生一些无效数据:,函数返回第一个?位置,为了删掉这些无效数据,我们需要结合 erase.
最终,给 vector 去重的写法便是:
vector<int>arrt{1, 2, 1, 4, 5, 4, 4};
sort(arr.begin(), arr.end()); //排序
arr.erase(unique(arr.begin(), arr.end()), arr.end()); //将无效数据删除
2
3
# 数学函数
所有函数均支持int / long long / float / double / long double
公式 | 示例 |
---|---|
abs(-1.0) | |
exp(2) | |
log(3) | |
pow(2, 3) | |
sqrt(2) | |
ceil(2.1) | |
floor(2.1) | |
round(2.1) |
注意事项
由于浮点误差,有的数学函数的行为可能与预期不符,导致WA。如果操作数都是整型,那么用下面的写法会更稳妥
-
- 别用:
floor(1.0 * a / b)
- 要用:
a / b
- 别用:
-
- 别用:
ceil(1.0 * a / b)
- 要用:
(a + b - 1) / b
()
- 别用:
-
- 别用:
(int) sqrt(a)
- 要用:二分查找https://io.zouht.com/7.html (opens new window)
- 别用:
-
- 别用:
pow(a, b)
- 要用:快速幂https://io.zouht.com/18.html (opens new window)
- 别用:
-
- 别用:
log2(a)
- 要用:
__lg
(不规范)/bit_width
(C++ 20 可用)
- 别用:
# gcd() / lcd()
(C++ 17)返回最大公因数 / 最小公倍数
int x = gcd(8, 12); // 4
int y = lcm(8, 12); // 24
2
如果不是C++ 17,但是是GUN编译器(g++),那么可以用内置函数__gcd()
当然,gcd() / lcd()
函数也挺好写,直接写也行(欧几里得算法):
int gcd(int a, int b)
{
if(!b)
return a;
return gcd(b, a % b);
}
int lcd(int a, int b)
{
return a / gcd(a, b) * b;
}
2
3
4
5
6
7
8
9
10
11