1-2算法基础-常用库函数

1.排序
sort(first,last,cmp)
first指向要排序范围的第一个元素，从0起
last指向要排序范围的最后一个元素的下一个位置
cmp（可选），自定义函数，默认从小到大

评测系统

#include <iostream>
#include<algorithm> 
using namespace std;
bool cmp(int a, int b) {
    return a > b;//定义从大到小排序
}
int main()
{
    int n;
    cin >> n;
    long long int a[500005];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);//从小到大
    for (int i = 0; i < n; i++) {
        cout<< a[i]<<" ";
    }
    cout << endl;
    sort(a, a + n,cmp);//定义比较函数
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

2.最值查找
min和max只能传入两个值或一个列表
min(3,5)=3
min({1,2,3,4})=1
min_element(st,ed)
st到end（不含）中最小那个值的地址

[例]成绩分析

评测系统

#include <iostream>
#include <algorithm>
#include <numeric>
#include <iomanip>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int a[10005];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int* x = max_element(a, a + n);  //#include <algorithm>
    cout << *x<<endl;

    x = min_element(a, a + n);  //#include <algorithm>
    cout << *x<<endl;

    double sum = accumulate(a, a + n, 0);  //#include <numeric>
    cout << fixed << setprecision(2) << 1.0*sum / n;  //#include<iomanip>，*1.0确保是小数，这样才能确保精度
    return 0;
}

3.二分查找
二分查找的库函数只能处理数字式单调不减/单调不增的

（1）binary_search
头文件#include <algorithm>
返回bool类型

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int a[] = { 1,4,6,8,9 };
    //查找6，返回bool类型，成功1，失败0
    cout << binary_search(a, a + 5, 6); // # include <algorithm>
}

（2）lower_bound
复杂度O(log n)
适用于单调不减的数组

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int a[] = { 1,4,6,6,9 };
    //返回第一个大于等于6的地址
    cout<<lower_bound(a, a + 5, 6);// 000000DB0954F9C0
    //减去首地址，返回的是索引下标，即6第一次出现的位置
    cout << lower_bound(a, a + 5, 6)-a;// 2
}

（3）upper_bound
适用于单调不减的数组

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int a[] = { 1,4,6,6,9 };
    //返回第一个大于6的地址
    cout<<upper_bound(a, a + 5, 6);// 000000010134FC58
    //减去首地址，返回的是索引下标
    cout << upper_bound(a, a + 5, 6)-a;// 4
}

[例] 二分查找数组元素，要求复杂度小于O(n)

解：数组中没有相同元素，且是单调递增的

#include <iostream>
using namespace std;
int main()
{
    int data[200];
    for (int i = 0; i < 200; i ++){
      data[i] = 4 * i + 6;
    }
    int  n;
    cin >> n;
    cout<<lower_bound(data, data + 200, n)-data;//lower_bound得到的是地址，减去首地址data即为下标
    return 0;
}

4.大小写转换

#include <iostream>
using namespace std;
int main()
{
    char a = 'A';
    if (isupper(a)) {//isupper判断是否是大写字母，bool类型
        cout << tolower(a);//转为小写，ASCII类型。输出：97
        cout << char(tolower(a));//ASCII转字符。输出：a
    }
}

对应的
判断是否小写（bool）：islower
转小写（ASCII）：tolower

当前，也可以用ASCII直接转换，
a 97
A 65
相差32

#include <iostream>
using namespace std;
int main()
{
    char s = 'A';
    cout << char(s + 32);// a
}

5.全排列（排列组合）
只能处理初始有序的序列
（1）next_permutation
若初始是abc（这是最小的序列组合（在字符串比较中））
大一点acb
再大bac
再大bca
再大cab
最大cba

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int a[3] = { 2, 5, 7 };
    do {
        for (int i = 0; i < 3; i++) {
            cout << a[i];
        }
        cout << endl;
    } while (next_permutation(a, a + 3));
    return 0;
}

输出：
257
275
527
572
725
752

（2）prev_permutation
由大到小输出，初始序列应为降序

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int a[3] = { 7, 5, 2 };
    do {
        for (int i = 0; i < 3; i++) {
            cout << a[i];
        }
        cout << endl;
    } while (prev_permutation(a, a + 3));

    return 0;
}

输出：
752
725
572
527
275
257

6.其他库函数

（1）memset
用于将一块内存区域的每个字节都设置为特定的值，通常用于初始化内存块
头文件#include <cstring>

只能设置成0或-1

int a[3] = { 7,6,4 };
memset(a, 0, sizeof(a));//对a数组每个元素初始化0

（2）swap
交换两个变量的值，变量值发生了改变

#include <iostream>
using namespace std;
int main() {
    int a = 1;
    int b = 2;
    swap(a, b);
    cout << a; //2
    return 0;
}

（3）reverse
翻转数组，会修改数组元素值

#include <iostream>
using namespace std;
int main() {
    int a[5] = { 1,2,3,4,5 };
    reverse(a, a + 5);
    for (int i = 0; i < 5; i++) {
        cout << a[i];//54321
    }
}

（4）unique
去除相邻重复元素
复杂度O(n)

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int a[10] = { 1, 2, 2, 3, 3, 3, 4, 5, 5, 5 };
    int* b=unique(a, a + 10);//指针b指向了去重后的最后一个元素的下一个位置
    int n = b-a;//b-起始地址即为去重后数组的元素个数
    for (int i = 0; i < n; i++) {
        cout << a[i];//12345
    }
}