基础算法实践一

vector

基本是对基础Vector的应用，这里复习一下： 构造vector变量：

//创建一个空的vector
vector<int> vec1;

//初始化列表（C++11）
vector<int> vec2 = {1, 2, 3, 4, 5};
vector<string> vec_str = {"hello", "world"};

//制定空间数量，并给予默认值，这里是5个空间，默认值100
vector<int> vec4(5, 100);

//复制操作
vector<int> vec5 = vec2

一些常用操作：

• []：不进行边界检查的访问。
• v.at(index)：进行边界检查的访问。
• v.front()：返回对第一个元素的引用。
• v.back()：返回对最后一个元素的引用。
• v.push_back(value)：在末尾添加一个元素。
• insert(iterator pos, value)：在指定迭代器 pos 指向的位置之前插入一个元素 value。

v.insert(v.begin() + 2, 30); // 在索引为 2 的位置 (即 40 之前) 插入 30

• v.pop_back()：删除 vector 的最后一个元素。
• v.clear()：删除 vector 中的所有元素，使其大小变为 0。容量通常保持不变。
• v.size()：返回 vector 中元素的数量。
• v.empty()：如果 vector 为空（即 size() == 0），则返回 true，否则返回 false。
• resize(new_size, value): 改变 vector 的大小为 new_size。如果 new_size 大于当前大小，则添加的新元素会被初始化为 value，value可以省略。

迭代器（index）：

• begin(): 返回一个指向 vector 第一个元素的迭代器。
• end(): 返回一个指向 vector 最后一个元素之后位置的迭代器 (哨兵)。
• rbegin(): 返回一个指向 vector 最后一个元素的反向迭代器。
• rend():返回一个指向 vector 第一个元素之前位置的反向迭代器。
• cbegin(), cend(), crbegin(), crend() (C++11 及更高版本):返回常量迭代器，不允许通过它们修改元素。 [[基于范围的 for 循环（C++11）]]

#include <vector>
#include <iostream>
#include <algorithm> // for std::for_each (现在是 for_each)

// 使用 std 命名空间，这样我们就不需要在每个标准库成员前加上 std::
using namespace std;

int main() {
    vector<int> v = {10, 20, 30, 40, 50};

    // 1. 使用基于范围的 for 循环 (C++11 及更高版本，推荐) 
    cout << "Using range-based for: ";
    for (int x : v) {
        cout << x << " ";
    }
    cout << endl;

    // 2. 使用迭代器
    cout << "Using iterators: ";
    for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
        // *it = (*it) * 2; // 可以通过迭代器修改元素
    }
    cout << endl;

    // 3. 使用常量迭代器 (如果不想修改)
    cout << "Using const_iterators: ";
    for (vector<int>::const_iterator cit = v.cbegin(); cit != v.cend(); ++cit) {
        cout << *cit << " ";
        // *cit = (*cit) * 2; // 编译错误，不能通过 const_iterator 修改
    }
    cout << endl;

    // 4. 使用反向迭代器
    cout << "Using reverse_iterators: ";
    for (vector<int>::reverse_iterator rit = v.rbegin(); rit != v.rend(); ++rit) {
        cout << *rit << " "; // 输出: 50 40 30 20 10
    }
    cout << endl;

    // 5. 使用 auto 关键字简化迭代器声明 (C++11 及更高版本)
    cout << "Using auto with iterators: ";
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 6. 使用算法库 (例如 for_each)
    cout << "Using for_each: "; // 注意：std::for_each 变成了 for_each
    for_each(v.begin(), v.end(), [](int x){ cout << x << " "; });
    cout << endl;

    return 0;
}

其他： v.assign():给 vector 赋新内容，替换其所有现有内容，有两种赋值形式。

std::vector<int> v;
v.assign(5, 10); // v 现在是 {10, 10, 10, 10, 10}

std::vector<int> v2 = {1, 2, 3};
v.assign(v2.begin(), v2.end()); // v 现在是 {1, 2, 3}

v.swap(other_vector):交换两个向量的内容，因为是更改指针所以时间复杂度很低。

vector的迭代器的不稳定性

vector中，内存的分配变动会导致迭代器失效，包括以下几种方式：

导致内存重分配的操作，因为vector需要一个连续内存保存，所以一旦插入过多的数，会导致内存重选地方，之前的迭代器也就失效。当操作导致 vector 的大小 size() 超过其当前容量 capacity() 时，就会发生内存重分配。

• push_back() / emplace_back()
• insert() / emplace()
• resize()

std::vector<int> vec = {1, 2, 3};
vec.reserve(3); // 此时 size() == 3, capacity() == 3

auto it = vec.begin(); // it 指向 1

std::cout << "Before push_back, a[0] is at: " << &(*it) << std::endl;

// 这个操作会导致 size() 变为 4，超过 capacity()，触发内存重分配
vec.push_back(4); 

// 此时，之前的迭代器 it 已经失效了！
// 对它进行任何操作（如解引用、自增）都是未定义行为，很可能导致程序崩溃。
// std::cout << "Value from stale iterator: " << *it; // !!! CRASH !!!

auto it_new = vec.begin(); // 必须重新获取迭代器
std::cout << "After push_back, a[0] is at: " << &(*it_new) << std::endl; // 地址会改变

移动元素也会导致一些迭代器失效：

• insert() / emplace(): 在位置 p 插入元素，会导致插入点 p 以及之后的所有迭代器、指针和引用全部失效。因为这些元素需要向后移动来腾出空间。
• erase(): 删除位置 p 的元素（或一个范围的元素），会导致被删除点 p 以及之后的所有迭代器、指针和引用全部失效。因为这些元素需要向前移动来填补空缺。

如何安全地在遍历中删除 vector 元素？

这是一个非常经典的错误场景：

// !!! 错误且危险的写法 !!!
for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (*it % 2 == 0) { // 假设要删除所有偶数
        vec.erase(it); // erase 之后, it 失效了!
    }                  // 下一轮循环的 ++it 就是对失效的迭代器操作，导致未定义行为
}

正确的写法（C++03/传统写法）： erase() 函数会返回一个指向被删除元素的下一个元素的有效迭代器。我们必须接收这个返回值来更新我们的迭代器。

for (auto it = vec.begin(); it != vec.end(); /* a blank */) {
    if (*it % 2 == 0) {
        it = vec.erase(it); // 用 erase 的返回值更新 it
    } else {
        ++it; // 只有不删除时，才手动将 it 后移
    }
}

现代 C++ 写法（：

#include <algorithm>

// std::remove_if 把所有要删除的元素“移动”到容器末尾，并返回一个指向第一个被移动元素的迭代器
auto new_end = std::remove_if(vec.begin(), vec.end(), 
                              [](int n){ return n % 2 == 0; });

// 然后，一次性地调用 erase 删除所有这些元素
vec.erase(new_end, vec.end());

约瑟夫问题

在一组人（或事物）围成的圆圈中，从某个人开始按固定步长（k）计数，每数到第 k 个人就将其淘汰出局，然后从下一个人开始重新计数，如此循环，直到剩下最后一个人。你需要找出最后一个幸存者的初始位置。

输入以一个整数 T (T ≤ 200) 开始，表示测试用例的数量。 每个测试用例包含两个正整数 n (1 ≤ n ≤ 200) 和 k (1 ≤ k < 201)。对于每个测试用例，请打印案例编号和最后一个剩下的人的位置。

思路

设 J(i, k) 是当有 i 个人（0-indexed，即编号为 0, 1, ..., i-1），每次数 k 个人时，幸存者的0-indexed编号。

• 基本情况： 当只有1个人时（i=1），这个人就是幸存者，其0-indexed编号为0。所以 J(1, k) = 0。
• 递推关系： 当有 i 个人时，第一个被淘汰的人的0-indexed编号是 (k-1) % i。在他被淘汰后，剩下 i-1 个人。问题规模缩小了。关键在于，原来 i-1 人问题的解（假设为 J(i-1, k)）是相对于淘汰第一个人之后重新编号的圈子而言的。 如果我们观察人员编号的变化，可以发现从 i-1 个人的解到 i 个人的解，幸存者的编号会向后移动 k 位（并对 i 取模）。 因此，0-indexed的递推公式为： J(i, k) = (J(i-1, k) + k) % i

我们可以从 i=2 迭代计算到 i=n，初始时 J(1, k) 的结果（即0-indexed的幸存者位置）为0。

example: 0 1 2 3 4 5 6, i=7, k=5,进行一次迭代后 2 3 4 5 0 1, (0+5)%7=5,(2+5)%7=0

求斐波那契数

输入N，求第N个斐波那契数。(N<=100)

思路：这个题的主要难度在于斐波那契数列增长太快了，导致long long型也存不下，所以必须得使用字符串手搓一个字符串型的加法。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // for reverse

using namespace std;

// 函数：将两个表示数字的字符串相加 (使用 if-else 结构，更清晰)
string addStrings_easyToRead(string num1, string num2) {
    string sum = "";
    int i = num1.length() - 1;
    int j = num2.length() - 1;
    int carry = 0;

    // 只要两个数字中任何一个还有位数，或者最后还有进位，循环就继续
    while (i >= 0 || j >= 0 || carry) {
        
        long long digit1 = 0; // 先假设当前位的数字是0
        // 如果 num1 还有位数 (i 指针没有越界)
        if (i >= 0) {
            // 就从 num1 中取出当前位的数字
            // '8' - '0' 的结果是整数 8
            digit1 = num1[i] - '0';
            i--; // 将指针向前移动一位
        }

        long long digit2 = 0; // 同样，先假设当前位的数字是0
        // 如果 num2 还有位数 (j 指针没有越界)
        if (j >= 0) {
            // 就从 num2 中取出当前位的数字
            digit2 = num2[j] - '0';
            j--; // 将指针向前移动一位
        }
        
        // 将两个数字和上一位的进位相加
        long long current_sum = digit1 + digit2 + carry;
        
        // 计算新结果的个位数，并添加到 sum 字符串中
        int digit_to_add = current_sum % 10;
        sum += to_string(digit_to_add);
        
        // 计算新的进位，用于下一次循环
        carry = current_sum / 10;
    }
    
    // 因为我们是从个位开始加，结果是反的 (例如 123+456 的 sum 是 "975")
    // 所以需要将字符串反转过来得到正确顺序
    reverse(sum.begin(), sum.end());
    
    // 处理一个特殊情况：如果两个输入都是 "0"，那么循环不会执行，sum会是空字符串。
    // 此时我们应该返回 "0"。
    if (sum.empty()) {
        return "0";
    } else {
        return sum;
    }
}

int main() {
    vector<string> Line; // 用字符串存储斐波那契数
    Line.push_back("1");
    Line.push_back("1");

    int N;
    cin >> N;

    if (N <= 0) {
        cerr << "错误：N 必须是一个正整数。" << endl;
        return 1;
    }

    if (N == 1) {
        cout << Line[0] << endl;
    } else if (N == 2) {
        cout << Line[1] << endl;
    } else {
        for (int i = 2; i < N; i++) {
            string next_val = addStrings(Line[Line.size() - 1], Line[Line.size() - 2]);
            Line.push_back(next_val);
        }
        cout << Line[N - 1] << endl;
    }
    return 0;
}

活动安排

设有 n 个活动的集合 $E={1,2,..,n}$，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 $i$ 都有一个要求使用该资源的起始时间 $s_i$​ 和一个结束时间 $f_i​$，且 $s_i​<f_i​$ 。如果选择了活动 $i$ ，则它在时间区间 $[si​,fi​)$ 内占用资源。若区间 $[si​,fi​)$ 与区间 $[sj​,fj​)$ 不相交，则称活动 $i$ 与活动 $j$ 是相容的。也就是说，当 $f_i​≤s_j$​ 或 $f_j​≤s_i​$ 时，活动 $i$ 与活动 $j$ 相容。选择出由互相兼容的活动组成的最大集合。

Input
4
1 3
4 6
2 5
1 7

Output
2

基本思路是贪心算法：

• 排序：将所有活动根据它们的结束时间（fᵢ），从小到大进行排序。
• 选择第一个活动：排序后，列表中的第一个活动自然是结束时间最早的。我们无条件选择它，并将其计入总数。
• 记录结束时间：记下第一个选定活动的结束时间，我们称之为 last_finish_time。
• 遍历剩余活动：从第二个活动开始，依次检查列表中的每一个活动。
• 判断兼容性：对于当前检查的活动 i，如果它的开始时间 sᵢ 大于或等于 last_finish_time，则说明它与我们上一个选择的活动是兼容的。
• 选择新活动并更新：如果兼容，我们就选择这个活动，将总数加一，并把 last_finish_time 更新为这个新选定活动的结束时间 fᵢ。
• 重复：继续遍历，直到检查完所有活动。最终得到的总数就是互相兼容的最大活动个数。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义一个结构体来存储每个活动
struct Activity {
    int start;
    int finish;
};

// 用于 sort 函数的自定义比较函数
// 根据活动的结束时间进行升序排序
bool compareActivities(const Activity& a, const Activity& b) {
    return a.finish < b.finish;
}

int main() {
    // 提高 I/O 效率
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 使用 vector 存储所有活动
    vector<Activity> activities(n);
    for (int i = 0; i < n; ++i) {
        cin >> activities[i].start >> activities[i].finish;
    }

    // 步骤 1: 根据结束时间对活动进行排序
    sort(activities.begin(), activities.end(), compareActivities);

    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    // 步骤 2 & 3: 选择第一个活动
    int count = 1;
    int last_finish_time = activities[0].finish;

    // 步骤 4: 遍历剩余的活动
    for (int i = 1; i < n; ++i) {
        // 步骤 5: 如果当前活动的开始时间晚于或等于上一个活动的结束时间
        if (activities[i].start >= last_finish_time) {
            // 步骤 6: 选择此活动，并更新状态
            count++;
            last_finish_time = activities[i].finish;
        }
    }

    // 输出最终结果
    cout << count << endl;

    return 0;
}