Algorithm API

1. 返回最值元素的迭代器

• max_element(begin, end) / min_element(begin, end)

  • 作用：返回容器（如数组、vector）中最大/最小元素的迭代器（指针）。注意需要加 * 取值。

  • vector<int> v = {3, 1, 4, 1, 5};
    auto it = max_element(v.begin(), v.end());
    cout << *it << endl;      // 输出: 5 (最大值)
    cout << it - v.begin();   // 输出: 4 (最大值的下标)

2.全排序

• next_permutation(begin, end)

  • 作用：将序列变为“下一个”字典序更大的排列。如果是最后一个排列（降序），则变回第一个排列（升序）并返回 false。

  • string s = "abc";
    do {
        cout << s << " "; // 输出: abc acb bac bca cab cba
    } while(next_permutation(s.begin(), s.end()));

• prev_permutation(begin, end)

  • 作用：与上面相反，求“上一个”字典序更小的排列。

  • string s = "cba";
    do {
        cout << s << " "; // 输出: cba cab bca bac acb abc
    } while(prev_permutation(s.begin(), s.end()));

3.原地反转元素

• reverse(begin, end)

  • 作用：原地反转区间内的元素。

  • vector<int> v = {1, 2, 3, 4};
    reverse(v.begin(), v.end());
    // v 变为: {4, 3, 2, 1}

4.查找目标值的迭代器

• find(begin, end, value)

  • 作用：线性查找第一个等于 value 的元素，返回迭代器。找不到返回 end。

  • vector<int> v = {10, 20, 30};
    auto it = find(v.begin(), v.end(), 20);
    if(it != v.end()) cout << "Found!"; // 输出: Found!

5.统计值的出现次数

• count(begin, end, value)

  • 作用：统计某个值出现的次数。

  • vector<int> v = {1, 2, 2, 3, 2};
    cout << count(v.begin(), v.end(), 2); // 输出: 3

6.二分查找

• binary_search(begin, end, value)

  • 作用：二分查找。前提是序列必须有序。返回 bool。时间复杂度 O(log⁡n)。

  • vector<int> v = {1, 3, 5, 7, 9}; // 必须有序
    bool found = binary_search(v.begin(), v.end(), 5);
    cout << found; // 输出: 1 (true)

7.去重

• unique(begin, end)

  • 作用：去重（仅针对相邻重复元素）。它不会删除元素，而是把不重复的移到前面，返回去重后的尾部迭代器。通常配合 erase 使用。

  • vector<int> v = {1, 1, 2, 3, 3};
    auto last = unique(v.begin(), v.end());
    v.erase(last, v.end()); // 真正删除多余元素
    // v 变为: {1, 2, 3}

8.返回二分查找边界

• lower_bound / upper_bound

  • 作用：二分查找边界。

    • lower_bound: 找第一个 ≥val 的位置。
    • upper_bound: 找第一个 >val 的位置。

  • vector<int> v = {1, 2, 4, 4, 5};
    // 找第一个 >= 4 的位置
    auto pos = lower_bound(v.begin(), v.end(), 4);
    cout << pos - v.begin(); // 输出: 2 (下标)

质数筛 欧拉筛

const int N = 1e8 + 5; // 根据需要调整上限
bool vis[N];           // 标记数组，true表示合数
int primes[N], cnt;    // 存储素数及计数

void euler_sieve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) primes[++cnt] = i; // 未被标记即为素数
        
        for (int j = 1; j <= cnt && i * primes[j] <= n; ++j) {
            vis[i * primes[j]] = true;  // 标记合数
            if (i % primes[j] == 0) break; // 【核心】保证每个合数只被最小质因数筛除
        }
    }
}

最小公倍数 最大公约数

// 求最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 求最小公倍数（防溢出写法）
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

占位用