数据结构与算法

[(459条消息) 【C语言】程序运行过程：预处理/编译/汇编/链接_预处理编译汇编链接_慕雪华年的博客-CSDN博客](https://blog.csdn.net/muxuen/article/details/123227200?ops_request_misc={"request_id"%3A"168596052316800182799736"%2C"scm"%3A"20140713.130102334.."}&request_id=168596052316800182799736&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-123227200-null-null.142^v88^control_2,239^v2^insert_chatgpt&utm_term=预处理 编译 汇编 链接&spm=1018.2226.3001.4187)

(443条消息) 保研机试——1基础算法（排序、哈希、模拟（日期、图形、查找、进制、字符串）、递归与分治、贪心）_Yuezero_的博客-CSDN博客

[(425条消息) 数据结构保研面试题整理（自用）_保研数据结构常温问题_乌鸡摸鱼的博客-CSDN博客](https://blog.csdn.net/m0_52571748/article/details/120505195?ops_request_misc=&request_id=&biz_id=102&utm_term=数据结构 保研&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-120505195.142^v73^pc_search_v2,201^v4^add_ask,239^v2^insert_chatgpt&spm=1018.2226.3001.4187)

(463条消息) 插入排序–折半插入排序（来一来，看一看，走过路过，不要错过）_老 胡的博客-CSDN博客

P问题、NP问题、NPC问题、NP-hard问题详解 - 知乎 (zhihu.com)

[保研机试整理 - 知乎 (zhihu.com)

什么时候才考虑用二分答案的技巧？
正向求出答案不好入手，求解答案远远没有验证答案简单。

已知前序后序算中序有多少种：

[(441条消息) 二叉树遍历（已知前序和后序遍历，求中序遍历的可能的序列数）_已知二叉树的前序遍历和后序遍历_我要出家当道士的博客-CSDN博客

(462条消息) 堆排序的时间复杂度分析_一只牛_007的博客-CSDN博客

建立索引树：[(462条消息) 2020北航计算机夏令营机试题目个人理解_北航夏令营 机试_四处碰壁嘤嘤怪的博客-CSDN博客](https://blog.csdn.net/Bernie_double/article/details/118190022?ops_request_misc={"request_id"%3A"168715279416800185829257"%2C"scm"%3A"20140713.130102334.."}&request_id=168715279416800185829257&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-5-118190022-null-null.142^v88^control_2,239^v2^insert_chatgpt&utm_term=北航夏令营 机试&spm=1018.2226.3001.4187)

注意

scanf后，用getchar()吃掉回车

表示最大 INT_MAX(climits)

1
2
3
4
5
6
7
8
//malloc
int *nums;
nums=(*int)malloc(10*sizeof(int));
//long long int 别用cin cout
long long a;
scanf("%lld",&a);
printf("%lld",a);

scanf还会返回成功输入的变量的个数,因此可判定EOF

Floyd判圈法很吊

1.lower_bound(v.begin(), v.end(), key)-v.begin()返回有序序列中大于等于key的第一个值的位置
2.upper_bound(v.begin(), v.end(), key)-v.begin()返回有序序列中大于key的第一个值的位置
3.lower_bound(v.begin(), v.end(), key, greater())-v.begin()返回有序序列中小于等于key的第一个值的位置
4.upper_bound(v.begin(), v.end(), key, greater())-v.begin()返回有序序列中小于key的第一个值的位置
5.上述四个函数，若无满足条件的值，则返回v.size()

文件操作

1
2
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);

lint&formatter

vscode记得装一个clang-format, ctrl+s能够自动保存

strcut初始化的例子：

1
2
3
4
5
6
7
* struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };

一些常用的库

  1. algorithm
  2. vector
  3. map
  4. queue
  5. iostream
  6. string
  7. bits/stdc++.h（带上就对了，不过mac的clang不支持，GCC支持）
  8. cmath(sqrt之类的)
  9. climits（INT_MAX INT_MIN）

STL内置find()复杂度：
algorithm的find 复杂度是O(n)，对vector，string等 顺序查询。
map::find 和 set::find 复杂度是O(logn)，因为map和set底层都是红黑树。

vector:

下面是一些常用的vector方法：

  1. push_back：在vector的末尾添加一个元素。

  2. pop_back：删除vector末尾的一个元素。

  3. size：返回vector中元素的个数。

  4. clear：删除vector中所有的元素。

  5. empty：判断vector是否为空。

  6. at：返回vector中指定位置的元素。

  7. front：返回第一个元素。

  8. back：返回最后一个元素。

  9. erase：删除vector中指定位置的元素。

  10. insert：在vector中指定位置插入一个元素或多个元素。

  11. resize：改变vector的大小。

  12. reserve：为vector预留一定的空间。

    1
    reverse(a.begin(),a.end());

  13. swap：交换两个vector中的元素。

  14. begin：返回指向vector第一个元素的迭代器。

  15. end：返回指向vector最后一个元素之后的迭代器。 这些方法能够满足大部分情况下的需求，可以根据具体的使用场景选择合适的方法进行操作。

要取迭代器的值，直接*指针取值

对于向量(vector)，它是一种支持随机访问的容器，因此可以直接通过下标访问向量中的元素。

1
2
3
4
5
vector<int> v = {1, 2, 3, 4, 5};
// 使用auto关键字定义迭代器
for (auto it = v.begin(); it != v.end(); it++) {
    cout << *it << " ";
}

vector不能直接使用sort函数进行排序，需要传入一个迭代器指定排序的范围。修改代码如下：

sort(v.begin(),v.end(),com);

map

以下是C++中map类的常用方法：

  1. insert(make_pair<key, value>)：向map中插入一个键值对。

  2. erase(key)：删除map中指定键的元素。

  3. clear()：清空map中所有元素。

  4. size()：返回map中元素的个数。

  5. empty()：返回map是否为空。

  6. find(key)：查找map中是否存在指定键的元素，如果存在则返回指向该元素的迭代器，否则返回end()迭代器。

    常常和end联合起来用判断找到没。(这个适合动态查找，底层红黑树实现)

    e.g. if (m.find(key)!=m.end())

  7. count(key)：返回指定键在map中出现的次数，如果不存在则返回0或1。

  8. begin()：返回指向map第一个元素的迭代器。

  9. end()：返回指向map最后一个元素后面的位置的迭代器。

  10. operator[]：通过键访问map中的元素，如果键不存在，则自动插入一个新的键值对并返回对应的值。

  11. lower_bound(key)：返回第一个大于或等于指定键的元素的迭代器。

  12. upper_bound(key)：返回第一个大于指定键的元素的迭代器。

  13. equal_range(key)：返回一个pair对象，其中包含lower_bound和upper_bound返回的迭代器。

  14. swap(map2)：交换当前map和map2的元素。 C++中的map类是一种关联式容器，用于存储键值对，其中每个键都唯一，并且按照一定的顺序排列。map的底层实现通常是红黑树，因此查找、插入和删除操作的时间复杂度为O(log n)，其中n是map中元素的个数。map类提供了丰富的方法，可以方便地进行键值对的操作，例如插入、删除、查找、排序等。同时，由于map使用键值对来存储数据，因此可以将map看作是一种特殊的数组，其下标为键，对应的值为数组元素。因此，可以通过下标来访问和修改map中的元素。

1
2
3
4
5
map<string, int> m = {{"apple", 1}, {"banana", 2}, {"orange", 3}};
// 使用auto关键字定义迭代器
for (auto it = m.begin(); it != m.end(); it++) {
    cout << it->first << ": " << it->second << endl;
}

stack

C++ 中的 stack 库提供了以下常用的方法：

  • push(elem)：将元素 elem 压入栈顶。
  • pop()：弹出栈顶元素。
  • top()：返回栈顶元素，但不弹出。
  • empty()：判断栈是否为空。
  • size()：返回栈中元素的个数。 除此之外，stack 还支持以下操作：
  • emplace(args…)：构造一个新元素并将其压入栈顶。
  • swap(stack)：交换两个 stack 的元素。
  • operator==、operator!=、operator<、operator<=、operator>、operator>=：比较两个 stack 是否相等、不相等、小于、小于等于、大于、大于等于。 具体用法可以参考下面的示例代码

stack元素可以是任何类型。

queue

C++中的queue是一种容器适配器，用于实现“先进先出”（FIFO）的数据结构。queue基于deque或list进行实现，提供了一些方法来操作队列，包括入队、出队、获取队首元素、获取队列大小等。以下是queue的常用方法：

  1. push(element)：将一个元素加入队列的尾部。
  2. pop()：将队列头部的元素弹出，但没有返回值。
  3. front()：返回队列头部的元素。
  4. top():返回队列头部元素（和front一样）
  5. back()：返回队列尾部的元素。
  6. empty()：判断队列是否为空。
  7. size()：返回队列中元素的个数。 使用queue需要包含头文件，可以通过以下方式创建一个queue对象：

对于队列(queue)，由于它是一种先进先出(FIFO)的数据结构，因此只能通过front()和back()函数来访问队列的头部和尾部元素，而不能直接通过下标访问。如果要使用下标访问队列元素，需要先将队列转换为数组或向量。

priority_queue

1
2
3
4
5
6
7
8
#include <queue>
//对于基础类型 默认是大顶堆
    priority_queue<int> a; 
    //等同于 priority_queue<int, vector<int>, less<int> > a;
    

    priority_queue<int, vector<int>, greater<int> > c;  //这样就是小顶堆
    priority_queue<string> b;

对于优先队列，复杂结构类型要重载运算符(436条消息) C++ 运算符重载_c 重载运算符_高祥xiang的博客-CSDN博客

1
2
3
4
5
6
7
8
struct complex{
int real;
int imag;
......
bool operator<(Complex c)const{
return real*real+imag*imag<c.real*c.real+c.imag*c.imag;
}
}

注意上面这个const是必须要有的

string

C++中的string类是一个封装了字符串操作的类，提供了一系列方法来处理和操作字符串。以下是常用的string类方法：

  1. length()：返回字符串的长度。

  2. size()：返回字符串的长度。

  3. clear()：清空字符串。

  4. empty()：判断字符串是否为空。

  5. assign(str)：将字符串的值设置为str。

  6. assign(str, pos, len)：将字符串的值设置为str中从pos位置开始的长度为len的子串。

  7. append(str)：在字符串的末尾添加str。

  8. append(str, pos, len)：在字符串的末尾添加str中从pos位置开始的长度为len的子串。

  9. push_back(ch)：在字符串的末尾添加一个字符。

  10. insert(pos, str)：在字符串的pos位置插入str。

  11. erase(pos, len)：删除从pos位置开始长度为len的子串。

    erase(n):删除indexn后面的字符

  12. replace(pos, len, str)：替换从pos位置开始长度为len的子串为str。

  13. substr(pos, len)：返回从pos位置开始长度为len的子串。

  14. find(str)：查找str在字符串中第一次出现的位置，返回该位置的索引值。(找不到就是-1)

  15. rfind(str)：查找str在字符串中最后一次出现的位置，返回该位置的索引值。

  16. compare(str)：比较字符串和str的大小，返回0（相等）、1（大于）或-1（小于）。 除了以上列举的方法，string类还支持重载运算符，例如+（字符串拼接）、+=（字符串拼接赋值）、==（字符串相等判断）、[]（访问字符串中指定位置的字符）等。string类的使用非常方便，可以像使用普通变量一样对字符串进行赋值、拼接、查找、替换等操作。例如：

注意string s，其s[i]类型为char，char强制类型转换可以这样转换

string(1,s[i])，1表示char长度

s[i]可以直接比较

输入str1,如果str1为空则退出

scanf不会读回车，如果下一行是gets会直接读取缓冲区中的回车，所有会用一个getchar()在中间把缓冲区中的回车抵消掉

stoi(str) 将其转换为整数，注意，如果是"04",直接变成4

string::npos用于判断结尾（其实找不到直接-1也行）：

1
2
3
4
5
6
7
8
9
10
11
12
13
//find函数返回 jk 在 s 中的下标位置
	position = s.find("jk");
	// 如果没找到，返回一个特别的标志
	// c++中用npos表示，我这里npos取值是4294967295
	if(position != s.npos)
	{
		cout << "position: " << position << endl;
	}
	else
	{
		cout << "Not found the flag" << endl;
	}

如果输入的字符串有空格，那么用如下代码

1
getline(cin,str)

可以直接通过下标修改字符

删除字符串内重复字符:

1
2
3
4
5
string str="aadfgggh";
//去重复
sort(str.begin(),str.end());
str.erase(unique(str.begin(),str.end()),str.end());

删除字符串内某个指定字符:

1
2
string str="aadfgggh";
str.erase(remove(str.begin(),str.end(),'a'),str.end()); //在容器中, 删除[begin,end)之间的所有值等于'a'的值.
1
2
#include<string>
string::erase(begin,end)：删除[begin,end)之间的所有值c

在Find the Smallest Number中，我发现string的超出index一位的位置依然可以访问，但是没有数

algorithm

C++标准库中的algorithm库提供了许多常用的算法，这些算法可以用于处理容器中的数据，例如排序、查找、遍历等。以下是algorithm库中常用的方法：

  1. sort(first, last, func)：对[first, last)区间内的元素进行升/降序排序（取决于func返回）。
  2. reverse(first, last)：对[first, last)区间内的元素进行翻转。
  3. find(first, last, val)：在[first, last)区间内查找值为val的元素，返回该元素的迭代器。如果没有找到，返回last。
  4. find_if(first, last, pred)：在[first, last)区间内查找满足条件pred的第一个元素，返回该元素的迭代器。如果没有找到，返回last。
  5. count(first, last, val)：统计[first, last)区间内值为val的元素个数。
  6. count_if(first, last, pred)：统计[first, last)区间内满足条件pred的元素个数。
  7. accumulate(first, last, init)：对[first, last)区间内的元素进行累加，初始值为init。
  8. max_element(first, last)：返回[first, last)区间内的最大元素的迭代器。
  9. min_element(first, last)：返回[first, last)区间内的最小元素的迭代器。
  10. unique(first, last)：对[first, last)区间内的元素去重，返回去重后的末尾迭代器。
  11. remove(first, last, val)：删除[first, last)区间内值为val的元素，返回删除后的末尾迭代器。
  12. remove_if(first, last, pred)：删除[first, last)区间内满足条件pred的元素，返回删除后的末尾迭代器。
  13. for_each(first, last, func)：对[first, last)区间内的元素执行操作func。
  14. transform(first1, last1, first2, result, op)：将[first1, last1)区间内的元素和[first2, …)区间内的元素进行op操作，并将结果存储到[result, …)区间内。

climits

中定义的常量主要有以下几种：

  1. 整数类型的最大值和最小值：INT_MAX、INT_MIN、LONG_MAX、LONG_MIN、SHRT_MAX、SHRT_MIN等等。
  2. 字符类型的最大值和最小值：CHAR_MAX、CHAR_MIN、SCHAR_MAX、SCHAR_MIN、UCHAR_MAX等等。
  3. 位数相关的常量：CHAR_BIT、INT_BIT、LONG_BIT等等。
  4. 其他常量：MB_LEN_MAX表示一个多字节字符的最大长度，FLT_MAX、FLT_MIN、DBL_MAX、DBL_MIN等等表示浮点类型的最大值和最小值。

set

set 是C++ STL中的关联容器，具有以下特点：

  • 自动排序：元素按升序排列（默认）
  • 唯一性：不允许重复元素
  • 高效查找：基于红黑树实现，查找、插入、删除时间复杂度为 O(log n)

头文件和声明

1
2
3
4
5
6
7
8
9
10
11
#include <set>
#include <iostream>

// 基本声明
std::set<int> mySet;

// 自定义比较函数
std::set<int, std::greater<int>> descendingSet;

// 自定义类型
std::set<std::string> stringSet;

基本操作

1. 插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <set>
#include <iostream>

int main() {
    std::set<int> mySet;
    
    // insert方法
    mySet.insert(10);
    mySet.insert(20);
    mySet.insert(5);
    mySet.insert(10);  // 重复元素不会插入
    
    // 插入多个元素
    mySet.insert({1, 3, 7, 9});
    
    // 输出结果：1 3 5 7 9 10 20（自动排序且去重）
    for(const auto& elem : mySet) {
        std::cout << elem << " ";
    }
    
    return 0;
}

2. 查找元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <set>
#include <iostream>

int main() {
    std::set<int> mySet = {1, 3, 5, 7, 9};
    
    // find方法 - 返回迭代器
    auto it = mySet.find(5);
    if(it != mySet.end()) {
        std::cout << "找到元素: " << *it << std::endl;
    } else {
        std::cout << "未找到元素" << std::endl;
    }
    
    // count方法 - 返回0或1
    if(mySet.count(7)) {
        std::cout << "元素7存在" << std::endl;
    }
    
    // contains方法 (C++20)
    // if(mySet.contains(7)) {
    //     std::cout << "元素7存在" << std::endl;
    // }
    
    return 0;
}

3. 删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <set>
#include <iostream>

int main() {
    std::set<int> mySet = {1, 2, 3, 4, 5};
    
    // 删除指定值
    mySet.erase(3);
    
    // 删除迭代器指向的元素
    auto it = mySet.find(4);
    if(it != mySet.end()) {
        mySet.erase(it);
    }
    
    // 删除范围
    auto first = mySet.find(1);
    auto last = mySet.find(5);
    if(first != mySet.end() && last != mySet.end()) {
        mySet.erase(first, last);  // 删除[1,5)范围
    }
    
    return 0;
}

utility:

在 C++ 中，pair 是标准模板库（STL）中的一种模板类，定义在头文件 <utility> 中，用于将两个值（可以是不同类型）组合成一个单元。

🧩 一、基本定义

1
2
3
4
#include <utility>  // 必须包含的头文件
using namespace std;

pair<T1, T2> p;
  • T1：第一个元素的类型
  • T2：第二个元素的类型
  • p.first：访问第一个元素
  • p.second：访问第二个元素

✅ 二、创建 pair 的几种方式

  1. 直接初始化
1
pair<int, string> p1(10, "hello");
  1. 使用 make_pair（自动推导类型）
1
auto p2 = make_pair(20, "world");  // 类型自动推导为 pair<int, const char*>

✅ 推荐使用 make_pair，简洁且避免手动写类型。

  1. 使用花括号初始化（C++11 起）
1
pair<int, double> p3{30, 3.14};
  1. 赋值构造
1
2
pair<string, int> p4;
p4 = make_pair("age", 25);

🔍 三、访问元素

1
2
cout << p1.first << endl;   // 输出: 10
cout << p1.second << endl;  // 输出: hello

🔄 四、比较操作

pair 支持 ==, !=, <, <=, >, >=，比较规则是：

  1. 先比较 first
  2. 如果 first 相等，再比较 second
1
2
3
4
5
6
pair<int, string> a(1, "apple");
pair<int, string> b(1, "banana");
pair<int, string> c(2, "apple");

cout << (a < b) << endl; // true —— first 相同，"apple" < "banana"
cout << (a < c) << endl; // true —— 1 < 2

✅ 这使得 pair 非常适合用作 map 的键、或在 set、priority_queue 中排序。

📦 五、常用场景

  1. 作为函数返回多个值
1
2
3
4
5
6
7
8
pair<int, int> getMinMax(vector<int>& nums) {
    int minVal = *min_element(nums.begin(), nums.end());
    int maxVal = *max_element(nums.begin(), nums.end());
    return make_pair(minVal, maxVal);
}

auto result = getMinMax({3, 1, 4, 1, 5});
cout << "Min: " << result.first << ", Max: " << result.second << endl;
  1. 在 map 中遍历键值对
1
2
3
4
5
6
7
8
map<string, int> ages = {{"Alice", 30}, {"Bob", 25}};

for (const auto& p : ages) {
    cout << p.first << " is " << p.second << " years old." << endl;
}
// 输出：
// Alice is 30 years old.
// Bob is 25 years old.

💡 map::value_type 就是 pair<const Key, T>

  1. 优先队列中自定义优先级
1
2
3
4
5
6
7
8
9
10
11
12
13
priority_queue<pair<int, string>> pq; // 默认按 first 降序
pq.push(make_pair(10, "low"));
pq.push(make_pair(30, "high"));
pq.push(make_pair(20, "medium"));

while (!pq.empty()) {
    cout << pq.top().first << ": " << pq.top().second << endl;
    pq.pop();
}
// 输出：
// 30: high
// 20: medium
// 10: low

🆚 六、pair vs tuple

特性 pair<T1, T2> tuple<T1, T2, T3, ...>
元素个数 固定 2 个 任意多个
访问方式 .first, .second get<0>(t), get<1>(t)…
使用场景 简单二元组（键值对、坐标等） 多返回值、复杂组合

✅ 如果只需要两个值，优先用 pair —— 语义清晰、访问方便。

🧠 七、小技巧

结构化绑定（C++17 起）

1
2
3
4
auto p = make_pair(100, "OK");
auto [value, message] = p;  // 解构赋值

cout << value << ", " << message << endl; // 输出: 100, OK

✅ 非常适合用于循环或函数返回值解包：

1
2
3
for (const auto& [key, val] : myMap) {
    cout << key << " => " << val << endl;
}

📚 八、完整示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 创建 pair
    pair<int, string> p1 = make_pair(1, "apple");
    pair<int, string> p2{2, "banana"};

    // 访问
    cout << p1.first << ": " << p1.second << endl;

    // 比较
    if (p1 < p2) {
        cout << "p1 < p2" << endl;
    }

    // 用在 vector 中
    vector<pair<int, string>> vec;
    vec.push_back(p1);
    vec.push_back(p2);

    // 排序（默认按 first 升序）
    sort(vec.begin(), vec.end());

    for (const auto& p : vec) {
        cout << p.first << " - " << p.second << endl;
    }

    // C++17 结构化绑定
    for (const auto& [id, name] : vec) {
        cout << "ID: " << id << ", Name: " << name << endl;
    }

    return 0;
}

✅ 总结

pair 是 C++ 中轻量级的“二元组”容器，用于捆绑两个相关值，广泛用于返回多值、map 遍历、排序、优先队列等场景。

📌 记住：

  • 包含头文件：#include <utility>
  • 创建：make_pair(a, b) 或 {a, b}
  • 访问：.first, .second
  • 支持比较、可作 map 键
  • C++17 支持结构化绑定：auto [x, y] = p;

掌握 pair，是用好 STL 和现代 C++ 的基础技能之一！

迭代器操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <set>
#include <iostream>

int main() {
    std::set<int> mySet = {10, 20, 30, 40, 50};
    
    // 正向遍历
    std::cout << "正向遍历: ";
    for(auto it = mySet.begin(); it != mySet.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 反向遍历
    std::cout << "反向遍历: ";
    for(auto it = mySet.rbegin(); it != mySet.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 范围for循环
    std::cout << "范围循环: ";
    for(const auto& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

容量和属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <set>
#include <iostream>

int main() {
    std::set<int> mySet = {1, 2, 3};
    
    // 大小
    std::cout << "大小: " << mySet.size() << std::endl;
    
    // 是否为空
    std::cout << "是否为空: " << (mySet.empty() ? "是" : "否") << std::endl;
    
    // 最大大小
    std::cout << "最大大小: " << mySet.max_size() << std::endl;
    
    return 0;
}

自定义比较函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <set>
#include <iostream>
#include <string>

// 方法1：函数对象
struct Compare {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.length() < b.length();  // 按长度排序
    }
};

// 方法2：函数指针
bool compareLength(const std::string& a, const std::string& b) {
    return a.length() < b.length();
}

int main() {
    // 按字符串长度排序
    std::set<std::string, Compare> lengthSet;
    lengthSet.insert("apple");
    lengthSet.insert("hi");
    lengthSet.insert("banana");
    lengthSet.insert("cat");
    
    // 输出: hi cat apple banana (按长度排序)
    for(const auto& str : lengthSet) {
        std::cout << str << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

实际应用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <set>
#include <iostream>
#include <vector>
#include <algorithm>

// 去除vector中的重复元素
std::vector<int> removeDuplicates(const std::vector<int>& vec) {
    std::set<int> uniqueSet(vec.begin(), vec.end());
    return std::vector<int>(uniqueSet.begin(), uniqueSet.end());
}

// 查找两个集合的交集
std::set<int> intersection(const std::set<int>& set1, const std::set<int>& set2) {
    std::set<int> result;
    std::set_intersection(set1.begin(), set1.end(),
                         set2.begin(), set2.end(),
                         std::inserter(result, result.begin()));
    return result;
}

int main() {
    // 去重示例
    std::vector<int> numbers = {1, 2, 2, 3, 3, 4, 5, 5};
    std::vector<int> uniqueNumbers = removeDuplicates(numbers);
    
    std::cout << "去重后: ";
    for(int num : uniqueNumbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 交集示例
    std::set<int> set1 = {1, 2, 3, 4, 5};
    std::set<int> set2 = {3, 4, 5, 6, 7};
    std::set<int> intersect = intersection(set1, set2);
    
    std::cout << "交集: ";
    for(int num : intersect) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

multiset 简介

如果需要允许重复元素，可以使用 multiset：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <set>
#include <iostream>

int main() {
    std::multiset<int> multiSet;
    
    multiSet.insert(10);
    multiSet.insert(20);
    multiSet.insert(10);  // 允许重复
    
    std::cout << "multiset大小: " << multiSet.size() << std::endl;  // 输出: 3
    
    // 统计特定元素出现次数
    std::cout << "10出现次数: " << multiSet.count(10) << std::endl;  // 输出: 2
    
    return 0;
}

性能特点

  • 插入: O(log n)
  • 删除: O(log n)
  • 查找: O(log n)
  • 空间复杂度: O(n)

set 是处理需要排序且唯一性要求的场景的理想选择！

设置输出精度

设置输出精度为1位小数

cout << fixed << setprecision(1) << ans << endl

设置输出位数

printf(“%02d”,&)

前面补零，两位，不够两位就补零

KMP

KMP 算法详解 - 知乎 (zhihu.com)

(427条消息) 从头到尾彻底理解KMP（2014年8月22日版）_kmp算法难吗是什么级别_v_JULY_v的博客-CSDN博客

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//next
void GetNext(char* p,int next[])
{
	int pLen = strlen(p);
	next[0] = -1;
	int k = -1;
	int j = 0;
	while (j < pLen - 1)
	{
		//p[k]表示前缀，p[j]表示后缀
		if (k == -1 || p[j] == p[k]) 
		{
			++k;
			++j;
			next[j] = k;
		}
		else 
		{
			k = next[k];
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//kmp
int KmpSearch(char* s, char* p)
{
	int i = 0;
	int j = 0;
	int sLen = strlen(s);
	int pLen = strlen(p);
	while (i < sLen && j < pLen)
	{
		//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++    
		if (j == -1 || s[i] == p[j])
		{
			i++;
			j++;
		}
		else
		{
			//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]    
			//next[j]即为j所对应的next值      
			j = next[j];
		}
	}
	if (j == pLen)
		return i - j;
	else
		return -1;
}

动态规划

最大连续子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int dp[1000001];
int nums[1000001];
int main(){
	int N;
	while(cin>>N){
		if (N==EOF)break;
		int maxnum=INT_MIN;
		for (int i=1;i<=N;i++){
			cin>>nums[i];
		}
		dp[1]=nums[1];
		if (N==1){
			cout<<dp[1]<<endl;
			break;
		}
		for (int i=2;i<=N;i++){
			dp[i]=max(nums[i],dp[i-1]+nums[i]);
			maxnum=max(dp[i],maxnum);
		}
		cout<<maxnum<<endl;
		
	}
	return 0;
}

最大子矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <algorithm>
using namespace std;

int dp[101];
int matrix[101][101];
int support[101][101];
int arr[101];

int hangmax(int n){
	int maxnum;
	for (int i=1;i<=n;i++){
		dp[i]=max(arr[i],dp[i-1]+arr[i]);
		maxnum=max(maxnum,dp[i]);
	}
	return maxnum;
}

int allmax(int n){
	int maxnum;
	for (int i=1;i<=n;i++){
		for (int j=i;j<=n;j++){
			for (int k=1;k<=n;k++){
				if (i==1){
					arr[k]=support[j][k];
				}else{
					arr[k]=support[j][k]-support[i-1][k];
				}
			}
			maxnum=max(hangmax(n),maxnum);
			
		}
	}
	return maxnum;
}

int main(){
	int n;
	cin>>n;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			cin>>matrix[i][j];
			
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			if (i==1)support[i][j]=matrix[i][j];
			else{
				support[i][j]=matrix[i][j]+support[i-1][j];
			}
		}
	}
	int maxnum;
	maxnum=allmax(n);
	cout<<maxnum<<endl;
	return 0;
	
	
}

最长递增/减序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>
using namespace std;

int dp[26];
int daodan[26];

int countmax(int n){
	int maxnum=0;
	for (int i=1;i<=n;i++){
		dp[i]=1;
	}
	for (int i=2;i<=n;i++){
		for (int j=1;j<i;j++){
			if (daodan[i]<=daodan[j])
			dp[i]=max(1,dp[j]+1);
			maxnum=max(maxnum,dp[i]);
		}
	}
	return maxnum;
}

int main(){
	int n;
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>daodan[i];
	}
	int maxnum;
	maxnum=countmax(n);
	cout<<maxnum<<endl;
	return 0;
}

最大上升子序列和（O(N^2)）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <algorithm>
using namespace std;

int dp[1001];
int nums[1001];

int countmax(int n){
	int maxsum;
	for (int i=1;i<=n;i++){
		dp[i]=nums[i];
	}
	for (int i=2;i<=n;i++){
		for (int j=1;j<i;j++){
			if (nums[i]>nums[j])
			dp[i]=max(nums[i],dp[j]+nums[i]);
			maxsum=max(maxsum,dp[i]);
		}
	}
	return maxsum;
}

int main(){
	int n;
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>nums[i];
	}
	int maxsum;
	if (n==1){
		cout<<nums[1];
		return 0;
	}
	maxsum=countmax(n);
	cout<<maxsum<<endl;
	return 0;
}

最长公共子序列（LCS）

1
7
3
5
9
4
8
3

(461条消息) 最长公共子序列 (LCS) 详解+例题模板（全）_lxt_Lucia的博客-CSDN博客

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

string s1;
string s2;

int countmax(string s1,string s2){
	int length1=s1.size();
	int length2=s2.size();
	int dp[length1][length2];
	for (int i=0;i<length1;i++){
		for (int j=0;j<length2;j++){
			dp[i][j]=0;
		}
	}
	int maxnum=0;
	for (int i=0;i<length1;i++){
		for (int j=0;j<length2;j++){
			if (s1[i]==s2[j]){
				if (i==0||j==0){
					dp[i][j]=1;
				}else{
					dp[i][j]=dp[i-1][j-1]+1;
				}
			}else{
				if (i==0||j==0){
					dp[i][j]=0;
				}else{
					dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
				}
				
			}
			maxnum=max(maxnum,dp[i][j]);
		}
	}
	return maxnum;
}
int main(){
	while(cin>>s1>>s2){
		int maxnum=countmax(s1,s2);
		cout<<maxnum<<endl;
		
	}
	return 0;
}

LIS（Nlogn）

(465条消息) 最长上升子序列 (LIS) 详解+例题模板 (全)_lxt_Lucia的博客-CSDN博客

01背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;

struct d{
	int price;
	int score;
};

int main(){
	int C,N;
	while (cin>>C>>N){
		if (C==0&&N==0)break;
		int dp[C+1];
		d deal[N];
		for (int i=0;i<=C;i++){
			dp[i]=0;
		}
		for (int i=0;i<N;i++){
			int price;
			int score;
			cin>>price>>score;
			deal[i].price=price;
			deal[i].score=score;
		}
		for (int i=0;i<N;i++){
			for (int j=C;j>=1;j--){
				if (j>=deal[i].price){
					dp[j]=max(dp[j-deal[i].price]+deal[i].score,dp[j]);
				}			
		}
	}
		cout<<dp[C]<<endl;
		
	}
	return 0;
}

有个背包的变种

(465条消息) 复旦大学2021年计算机学院机试题解_复旦oj_PyKt的博客-CSDN博客

这里是直接顺序的

DFS BFS

排序

归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
void merge(int* a, int low, int mid, int hight)  //合并函数
{
	int* b = new int[hight - low + 1];  //用 new 申请一个辅助函数
	int i = low, j = mid + 1, k = 0;    // k为 b 数组的小标
	while (i <= mid && j <= hight)  
	{
		if (a[i] <= a[j])
		{
			b[k++] = a[i++];  //按从小到大存放在 b 数组里面
		}
		else
		{
			b[k++] = a[j++];
		}
	}
	while (i <= mid)  // j 序列结束，将剩余的 i 序列补充在 b 数组中 
	{
		b[k++] = a[i++];
	}
	while (j <= hight)// i 序列结束，将剩余的 j 序列补充在 b 数组中 
	{
		b[k++] = a[j++];
	}
	k = 0;  //从小标为 0 开始传送
	for (int i = low; i <= hight; i++)  //将 b 数组的值传递给数组 a
	{
		a[i] = b[k++];
	}
	delete[]b;     // 辅助数组用完后，将其的空间进行释放（销毁）
}
void mergesort(int* a, int low, int hight) //归并排序
{
	if (low < hight)
	{
		int mid = (low + hight) / 2;
		mergesort(a, low, mid);          //对 a[low,mid]进行排序
		mergesort(a, mid + 1, hight);    //对 a[mid+1,hight]进行排序
		merge(a, low, mid, hight);       //进行合并操作
	}
}
int main()
{
	int n, a[100];
	cout << "请输入数列中的元素个数 n 为：" << endl;
	cin >> n;
	cout << "请依次输入数列中的元素：" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	mergesort(a, 0, n-1);
	cout << "归并排序结果" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void QuickSort(int arr[], int begin, int end)
{
    //只有一个数或者区间不存在时
    if (begin >= end) return;
    int left = begin;
    int right = end;
    //选取左边第一个为key
    int key = begin;
    while (begin<end)
    {
        //右边选小
        while (arr[end] >= arr[key] && begin < end)
        {
            end--;
        }
        //左边选大
        while (arr[begin] <= arr[key] && begin < end)
        {
            begin++;
        }
        swap(arr[begin], arr[end]);
    }
    //此时left和right指针已经相遇
    swap(arr[key], arr[end]);
    //递归左右区间
    key = end;
    QuickSort(arr, left, key - 1);
    QuickSort(arr, key + 1, right);
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
const long long m=1e9+7;
long long quickpow(long long a,long long b){
	long long sum=1;
	while(b){
		if(b&1)//与运算，可判断奇偶，详细见注释
		sum=sum*a%m;//取模运算
		a=a*a%m;
		b>>=1;//位运算，右移，相当于除以2
	}
	return sum;
}

模拟问题

就是找规律，还行

日期问题

要预处理

最大公因数/最小公倍数

最小公倍数=a*b/c

c为最大公因数

1
2
3
4
5
6
7
8
9
//最大公因数
int biggest(int a,int b){
	return b!=0?biggest(b,a%b):a;
}
//最小公倍数
int smallest(int a, int b){
   	int big=biggest(a,b);
    return a*b/big;
}

素数筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
using namespace std;
int n;

int main(){
	while (cin>>n){

		if (n==0)break;
		if (n==2){
			cout<<-1<<endl;
			continue;
		}
		bool sushu[n+1];
		for (int i=2;i<=n;i++){
			sushu[i]=true;
		}
		for (int i=2;i<=n;i++){
			if (sushu[i]==false)continue;
			for (int j=i;j*i<=n;j++){ //j直接从i开始，提高效率
				if (j*i<n){
					sushu[j*i]=false;
				}
			}
		}
		for (int i=2;i<n;i++){
			if (sushu[i]){
				if (i%10==1){
					cout<<i<<" ";
				}
			}
		
		}
		cout<<endl;
		
	}
	return 0;
}

对于一个数n，其质因数最多只有一个大于其平方根！

矩阵乘法（构造函数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
using namespace std;

struct Matrix{
	int matrix[10][10];
	int row;
	int col;
	Matrix(int a,int b):row(a),col(b){}//注意构造函数的写法
};
Matrix Multiply(Matrix a,Matrix b){
	Matrix ans=Matrix(a.row,b.col);
	for (int i=0;i<a.row;i++){
		for (int j=0;j<b.col;j++){
			int temp=0;
			for (int k=0;k<a.col;k++){
				temp+=a.matrix[i][k]*b.matrix[k][j];
			}
			ans.matrix[i][j]=temp;
		}
	}
	return ans;
}

void printMatrix(Matrix m){
	int row=m.row;
	int col=m.col;
	for (int i=0;i<row;i++){
		for (int j=0;j<col;j++){
			if (j!=0){
				cout<<" ";
			}
			cout<<m.matrix[i][j];
		}
		cout<<endl;
	}
}


int main(){
	Matrix a=Matrix(2,3);
	Matrix b=Matrix(3,2);
	for (int i=0;i<2;i++){
		for (int j=0;j<3;j++){
			cin>>a.matrix[i][j];
		}
	}
	for (int i=0;i<3;i++){
		for (int j=0;j<2;j++){
			cin>>b.matrix[i][j];
		}
	}
	Matrix c=Multiply(a,b);
	printMatrix(c);
	return 0;
	
}

高精度

最小生成树

prim算法求最小生成树- CSDN搜索

kruscal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <queue>
using namespace std;

struct edge{
	int a;
	int b;
	int weight;
	bool operator>(edge c)const{
		return weight>c.weight;
	}
	edge(int q,int w,int e):a(q),b(w),weight(e){}
};

priority_queue<edge,vector<edge>,greater<edge>>edges;
int graph[100];


int find(int x){
	if (graph[x]==-1)return x;
	else{
		int temp;
	temp=find(graph[x]);
	graph[x]=temp;
	return temp;
	}
	
}

int main(){
	int n;
	while (cin>>n){
		if (n==0)break;
		int a,b,weight;
		int num=n*(n-1)/2;
		memset(graph,-1,sizeof(graph));
		for (int i=1;i<=n;i++){
			graph[i]=-1;
		}
		while (num--){
			cin>>a>>b>>weight;
			edge edge1=edge(a,b,weight);
			edges.push(edge1);
		}
		int sum=0;
		int count=0;
		while (!edges.empty()&&count<n-1){
			edge temp=edges.top();
			edges.pop();
			int a=find(temp.a);
			int b=find(temp.b);
			int weight=temp.weight;
			if (a!=b){
				graph[a]=b;
				count++;
				sum+=weight;
			}
		}
		cout<<sum<<endl;
	}
	return 0;
}

弗洛伊德

1
2
3
4
5
6
7
8
9
for (int k = 1;k <= n;k ++) { 
 for (int i = 1;i <= n;i ++) { 
 for (int j = 1;j <= n;j ++) { 
 if (ans[i][k] == 无穷 || ans[k][j] == 无穷) continue; 
 if (ans[i][j] == 无穷 || ans[i][k] + ans[k][j] < ans[i][j]) 
 ans[i][j] = ans[i][k] + ans[k][j]; 
 } 
 } 
 }

迪杰斯特拉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
for (int i = 1;i <= n;i ++) { //初始化
 Dis[i] = -1; //所有距离为-1，即不可达
 mark[i] = false; //所有结点不属于集合K
 } 
 Dis[1] = 0; //得到最近的点为结点1,长度为0
 mark[1] = true; //将结点1加入集合K
 int newP = 1; //集合K中新加入的点为结点1 
 for (int i = 1;i < n;i ++) { //循环n-1次,按照最短路径递增的顺序确定其他n-1个点的最短路径长度
 for (int j = 0;j < edge[newP].size();j ++) { //遍历与该新加入集合
K中的结点直接相邻的边
 int t = edge[newP][j].next; //该边的另一个结点
 int c = edge[newP][j].c; //该边的长度
 if (mark[t] == true) continue; //若另一个结点也属于集合K,则跳过
 if (Dis[t] == - 1 || Dis[t] > Dis[newP] + c) //若该结点尚不可
达,或者该结点从新加入的结点经过一条边到达时比以往距离更短
 Dis[t] = Dis[newP] + c; //更新其距离信息
 } 
 int min = 123123123; //最小值初始化为一个大整数,为找最小值做准备
 for (int j = 1;j <= n;j ++) { //遍历所有结点
 if (mark[j] == true) continue; //若其属于集合K则跳过
 if (Dis[j] == -1) continue; //若该结点仍不可达则跳过
 if (Dis[j] < min) { //若该结点经由结点1至集合K中的某点在经过一条
边到达时距离小于当前最小值
 min = Dis[j]; //更新其为最小值
 newP = j; //新加入的点暂定为该点
 }

欧拉回路（hierholzer）

(462条消息) 欧拉回路（hierholzer算法）_逐步插入回路法_run around的博客-CSDN博客

关键路径（AOE网）

最早开始时间=最晚开始时间

用拓扑图

最早开始时间（所有先序活动的最晚完成时间）

最晚开始时间（所有后续活动的最早开始时间减去该活动花费的时间）

注意源点的最早开始时间不一定为0，要初始化

汇点的最晚开始时间初始化为totalTime-该汇点任务的时间

非汇点的最晚开始时间为无穷

如果只是要求关键路径的长度，其实在earliest[i]初始化的时候就设置为任务的时间就行，但如果要算其他的，就还是设置为0

7 5
11 20 17 10 11 17 17
5 4
6 1
7 3
2 4
2 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#define yushu 1e9+7
using namespace std;

queue<int>zero;
vector<int>re;
struct edge{
	int to;
	int weight;
};
int in[100001];
vector<edge>edges[100001];
int task[100001];
int earliest[100001];
int latest[100001];

int max(int a,int b){
	return a>b?a:b;
}
int min(int a,int b){
	return a<b?a:b;
}

int main(){
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		in[i]=0;
		cin>>task[i];
	}
	int num=m;
	int allTime=0;
	cout<<"input edge"<<endl;
	while (num--){
		int a,b;
		cin>>a>>b;
		in[b]++;
		edge temp;
		temp.to=b;
		temp.weight=task[b];
		edges[a].push_back(temp);
	}
	cout<<"input finished."<<endl;
	for (int i=1;i<=n;i++){
		cout<<"earliest["<<i<<"]:"<<earliest[i]<<endl;
		if (in[i]==0){
			zero.push(i);


		}
	}
	while (!zero.empty()){
		int node=zero.front();
		cout<<"zero:"<<node<<endl;
		zero.pop();
		re.push_back(node);
		for (int i=0;i<edges[node].size();i++){
			int to=edges[node][i].to;
			int weight=edges[node][i].weight;
			cout<<"edge:"<<node<<"-"<<to<<":"<<weight<<endl;
			earliest[to]=max(earliest[to],earliest[node]+task[node]);
			cout<<"earliest["<<to<<"]:"<<earliest[to]<<endl;
			in[to]--;
			if (in[to]==0){
				zero.push(to);
			}
		}
	}
	for (int i=1;i<=n;i++){
		allTime=max(allTime,earliest[i]+task[i]);
	}
	cout<<"reverse:"<<endl;
	for (int i=re.size()-1;i>=0;i--){
		int u=re[i];
		if (edges[u].size()==0){
			latest[u]=allTime-task[u];
			cout<<"latest:["<<u<<"]:"<<latest[u]<<endl;
		}else{
			latest[u]=99999999;
		
		}
		for (int j=0;j<edges[u].size();j++){
			int to=edges[u][j].to;
			int weight=edges[u][j].weight;
			latest[u]=min(latest[u],latest[to]-task[u]);
			cout<<"latest:["<<u<<"]:"<<latest[u]<<endl;
		}
	
	}
	
	cout<<endl;
	for (int i=1;i<=n;i++){
			cout<<"earliest["<<i<<"]:"<<earliest[i]<<endl;
			cout<<"latest["<<i<<"]:"<<latest[i]<<endl;
	}
	

	int sum=1;

	for (int i=1;i<=n;i++){
		sum*=(latest[i]-earliest[i]+1);
	}
	cout<<allTime<<endl;
	cout<<sum<<endl;
	return 0;
	
	
}

(466条消息) AOE问题总结_DrCrypto的博客-CSDN博客

(466条消息) AOE网关键路径求解例题_关键路径例题图解_HardyDragon_CC的博客-CSDN博客

数位dp

(443条消息) 2019年南京大学计算机考研复试机试真题_南大计算机专业考研机试_yc_cy1999的博客-CSDN博客

一个整数可以变为多少个整数相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N];//存所有状态
int main()
{
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; i ++)
        for(int j = i; j <= n; j ++)//j是容量
            f[j] = (f[j] + f[j - i]) % mod;
    cout << f[n] << endl;
    return 0;
}

状压DP

(462条消息) 291. 蒙德里安的梦想（状压dp）_seez的博客-CSDN博客

[(462条消息) 状压dp] 蒙德里安的梦想(模板题+状压dp)_状压dp模板题_Ypuyu的博客-CSDN博客

(462条消息) C++笔试题模版汇总(五)动态规划/贪心_c++笔试题 考动态规划么_ai_XZP_master的博客-CSDN博客

状态压缩DP学习总结+经典例题精解_状压dp-CSDN博客

汉诺塔问题

结论：把i个盘子移到另一个柱面上，需要2^i-1步

关于汉诺塔问题 - 知乎 (zhihu.com)

放置街灯（Placing Lampposts, UVa 10859）:star:

image-20230515221130204

经典贪心

(450条消息) UVA-10382经典贪心问题，区间覆盖_uva 10382_KXL5180的博客-CSDN博客

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//酸奶工程
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//定义long long，防止爆int
ll n,s;
ll c[10010],y[10010];//存储费用和交互数量
ll f[10010];
ll sum=0;
int main(){
    scanf("%lld%lld",&n,&s);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&c[i],&y[i]);
    }
    for(int i=1;i<=n;i++){
        if(i==1){
            f[i]=c[i];
        }
        else{
            f[i]=min(c[i],f[i-1]+s);
        }
        sum=sum+f[i]*y[i];
    }
    printf("%lld",sum);
}

跳跃问题

(462条消息) Leetcode——跳跃问题II_跳跃问题2_Purple.''的博客-CSDN博客

分发糖果

(462条消息) 「leetcode」135.分发糖果【贪心算法】详细图解_代码随想录的博客-CSDN博客

线段树

(462条消息) 线段树 从入门到进阶（超清晰，简单易懂）_线段树进阶_繁凡さん的博客-CSDN博客

匈牙利算法

(462条消息) 匈牙利算法详解_Amelie_xiao的博客-CSDN博客

一个二分图中的最大匹配数等于这个图中的最小点覆盖数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int M, N;            //M, N分别表示左、右侧集合的元素数量
int Map[MAXM][MAXN]; //邻接矩阵存图
int p[MAXN];         //记录当前右侧元素所对应的左侧元素
bool vis[MAXN];      //记录右侧元素是否已被访问过
bool match(int i)
{
    for (int j = 1; j <= N; ++j)
        if (Map[i][j] && !vis[j]) //有边且未访问
        {
            vis[j] = true;                 //记录状态为访问过
            if (p[j] == 0 || match(p[j])) //如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
            {
                p[j] = i;    //当前左侧元素成为当前右侧元素的新匹配
                return true; //返回匹配成功
            }
        }
    return false; //循环结束，仍未找到匹配，返回匹配失败
}
int Hungarian()
{
    int cnt = 0;
    for (int i = 1; i <= M; ++i)
    {
        memset(vis, 0, sizeof(vis)); //重置vis数组
        if (match(i))
            cnt++;
    }
    return cnt;
}

回溯

[(462条消息) 2018南京大学计算机夏令营机试第二题（回溯）_只会写臭虫的博客-CSDN博客](https://blog.csdn.net/weixin_43175029/article/details/94670710?ops_request_misc=&request_id=&biz_id=102&utm_term=Missing number Given a positi&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-94670710.142^v88^control_2,239^v2^insert_chatgpt&spm=1018.2226.3001.4187)

回溯就是dfs，并且在每次dfs时记得恢复原状态；如果只需要输出一种状态，设置flag标志位

N皇后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
using namespace std;
const int N = 20; 
 
// bool数组用来判断搜索的下一个位置是否可行
// col列，dg对角线，udg反对角线
// g[N][N]用来存路径
 
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
 
void dfs(int u) {
    // u == n 表示已经搜了n行，故输出这条路径
    if (u == n) {
        for (int i = 0; i < n; i ++ ) puts(g[i]);   // 等价于cout << g[i] << endl;
        puts("");  // 换行
        return;
    }
 
    // 枚举u这一行，搜索合法的列
    int x = u;
    for (int y = 0; y < n; y ++ )
        // 剪枝(对于不满足要求的点，不再继续往下搜索)  
        // 这里y-x+n是左上角到右下角,y+x是左下角到右上角
        if (col[y] == false && dg[y - x + n] == false && udg[y + x] == false) {
            col[y] = dg[y - x + n] = udg[y + x] = true;
            g[x][y] = 'Q';
            dfs(x + 1);
            g[x][y] = '.';  // 恢复现场
            col[y] = dg[y - x + n] = udg[y + x] = false;
        }
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';
 
    dfs(0);
 
    return 0;
}

建立索引树

[(462条消息) 2020北航计算机夏令营机试题目个人理解_北航夏令营 机试_四处碰壁嘤嘤怪的博客-CSDN博客](https://blog.csdn.net/Bernie_double/article/details/118190022?ops_request_misc={"request_id"%3A"168715279416800185829257"%2C"scm"%3A"20140713.130102334.."}&request_id=168715279416800185829257&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-5-118190022-null-null.142^v88^control_2,239^v2^insert_chatgpt&utm_term=北航夏令营 机试&spm=1018.2226.3001.4187)

注意 建树不一定要指针，数组也可

4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

hot 100

49. 字母异位词分组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdlib.h>

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    map<string, vector<string>> mapSet;
    vector<vector<string>> ans;
    // 添加
    for (string s : strs) {
        string temp = s;
        sort(temp.begin(), temp.end());
        if (mapSet.find(temp) != mapSet.end()) {
            mapSet[temp].push_back(s);
        } else {
            mapSet[temp] = vector<string>{s};
        }
    }
    // 遍历map，以key作为一个list
    for (auto item = mapSet.begin(); item != mapSet.end(); item++) {
        ans.push_back(item->second);
    }
    return ans;
}

// 添加函数来打印结果
void printResult(const vector<vector<string>>& result) {
    cout << "[";
    for (size_t i = 0; i < result.size(); ++i) {
        if (i > 0) cout << ",";
        cout << "[";
        for (size_t j = 0; j < result[i].size(); ++j) {
            if (j > 0) cout << ",";
            cout << "\"" << result[i][j] << "\"";
        }
        cout << "]";
    }
    cout << "]" << endl;
}

int main() {
    vector<string> list = {"eat", "tea", "tan", "ate", "nat", "bat"};
    vector<vector<string>> ans = groupAnagrams(list);
    printResult(ans);  // 使用自定义函数打印
    return 0;
}

763. 划分字母区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> partitionLabels(string s) {
    int last[26];
    int length = s.size();
    for (int i = 0; i < length; i++) {
        last[s[i] - 'a'] = i;
    }
    vector<int> partition;
    int start = 0, end = 0;
    for (int i = 0; i < length; i++) {
        end = max(end, last[s[i] - 'a']);
        if (i == end) {
            partition.push_back(end - start + 1);
            start = end + 1;
        }
    }
    return partition;
}

int main() {
    string s;
    cin >> s;
    vector<int> ans = partitionLabels(s);
    for (auto item : ans) {
        cout << " " << item;
    }
    return 0;
}

32. 最长有效括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <stack>
#include <string>

using namespace std;

int longestValidParentheses(string s) {
    stack<int> stk;
    int num = 0;
    int ans = 0;
    int len = s.size();
    stk.push(-1);
    for (int i = 0; i < len; i++) {
        if (s[i] == '(') {
            stk.push(i);
        } else {
            stk.pop();
            if (stk.empty()) {
                stk.push(i);
            } else {
                num = i - stk.top();
                ans = max(num, ans);
            }
        }
    }
    return ans;
}

int max(int a, int b) {
    if (a > b) {
        return a;
    }
    return b;
}

int main() {
    string s = ")()())";
    int ans = longestValidParentheses(s);
    cout << ans;
}

84. 矩形图中的最大面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <stack>
#include <vector>

using namespace std;
int largestRectangleArea(vector<int>& heights) {
    stack<int> stk;
    int ans = 0;
    for (int i = 0; i < heights.size(); i++) {
        if (stk.empty() || heights[i] > heights[stk.top()]) {
            stk.push(i);
        } else {
            while (!stk.empty() && heights[stk.top()] > heights[i]) {
                int length = heights[stk.top()];
                stk.pop();
                int weight = i;
                if (!stk.empty()) {
                    weight = i - stk.top() - 1;
                }
                ans = max(ans, length * weight);
            }
            stk.push(i);
        }
    }
    int right = heights.size();
    while (!stk.empty()) {
        int h = heights[stk.top()];
        stk.pop();
        if (!stk.empty()) {
            int left = stk.top();
            ans = max(ans, h * (right - left - 1));
        } else {
            ans = max(right * h, ans);
        }
    }
    return ans;
}

int max(int a, int b) {
    if (a > b) {
        return a;
    }
    return b;
}

int main() {
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    int ans = largestRectangleArea(heights);
    cout << ans << endl;
}

LCR 153. 二叉树中和为目标值的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathTarget(TreeNode* root, int target) {
        cur(root,target);
        return ans;
    }
private:
    vector<int>path;
    vector<vector<int>>ans;
    void cur(TreeNode* node,int target){
        if (node == nullptr) return;
        path.push_back(node->val);
        target = target-node->val;
        if (target==0&&node->left==nullptr&&node->right==nullptr){
            ans.push_back(path);
        }
        cur(node->left,target);
        cur(node->right,target);
        path.pop_back();
    }
};

153. 寻找旋转排序数组中的最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findMin(vector<int>& nums) {
        int i =0;
        int j = nums.size()-1;
        while(i<j){
            int middle = (i+j)/2;
            if (nums[middle]<nums[j]){
                j = middle;
            }else{
                i = middle+1;
            }
        }
        return nums[i];
    }
};

33. 搜索旋转排序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = (int)nums.size();
        if (!n) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) return mid;
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
};

76. 最小覆盖子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
private:
 
public:
    unordered_map<char,int> m1,m2;
    string minWindow(string s, string t) {
        int len=s.size()+100;
        int ans_left = -1;
        int left=0;
        int right =-1;
        for (int i=0;i<t.size();i++){
            m1[t[i]]++;
        }
        while (right<s.size()){
            if (m1.find(s[++right])!=m1.end()){
                m2[s[right]]++;
            }
            while(checkReady()&&left<=right){
                if(right-left+1<len){
                    len = right-left+1;
                    ans_left = left;
                }
                if (m1.find(s[left])!=m1.end()){
                    m2[s[left]]--;
                }
                left++;
            }
        }
        if (ans_left!=-1){
            return s.substr(ans_left,len);
        }
        return "";
    }
    bool checkReady(){
        for (auto it=m1.begin();it!=m1.end();it++){
            if (m2[it->first]<it->second){
                return false;
            }
        }
        return true;
    }
};

LRU

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class LRUCache {
private:
    struct Node {
        int key, value;
        Node* prev;
        Node* next;
        Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };
    
    int capacity;
    std::unordered_map<int, Node*> cache;
    Node* head;
    Node* tail;
    
    // 删除节点
    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    
    // 在头部添加节点
    void addToHead(Node* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    
    // 移动节点到头部
    void moveToHead(Node* node) {
        removeNode(node);
        addToHead(node);
    }
    
    // 删除尾部节点
    Node* removeTail() {
        Node* node = tail->prev;
        removeNode(node);
        return node;
    }
    
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        }
        
        Node* node = cache[key];
        // 移动到头部
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (cache.find(key) == cache.end()) {
            // 新节点
            Node* node = new Node(key, value);
            cache[key] = node;
            addToHead(node);
            
            if (cache.size() > capacity) {
                // 超出容量，删除尾部节点
                Node* tail = removeTail();
                cache.erase(tail->key);
                delete tail;
            }
        } else {
            // 更新现有节点
            Node* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }
};

三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    ans.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        return ans;
    }
};

无重复字符的最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int>m;
        int left =0;
        int right = 0;
        int ans=0;
        while(left<=right&&right<s.size()){
            m[s[right]]++;
            if (m[s[right]]>1){
                while(left<=right){
                    m[s[left]]--;
                    left++;
                    if (m[s[right]]==1){
                        break;
                    }
                }
            }else{
                ans = max(ans,right-left+1);
            }
            right++;
        }
        return ans;
        
    }
};

和为k的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        vector<int>prifix_sum(nums.size()+1);
        for (int i=0;i<nums.size();i++){
            prifix_sum[i+1] = prifix_sum[i]+nums[i];
        }
        int ans = 0;
        unordered_map<int,int> m ;
        for (int i=0;i<prifix_sum.size();i++){
            if (m.find(prifix_sum[i]-k)!=m.end()){
                ans =ans+m[prifix_sum[i]-k];
            }
            m[prifix_sum[i]]++;
        }
        return ans;
    }
};

二叉树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    TreeNode* ans;
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return false;
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);
        if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
            ans = root;
        } 
        return lson || rson || (root->val == p->val || root->val == q->val);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }
};

每日一题

3227.字符串元音游戏

感觉就是个博弈问题。

如果当前剩下的所有的字符中包含元音个数为奇数个，她直接赢，反之就是小明赢。

1935. 可以输入的最大单词数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int canBeTypedWords(string text, string brokenLetters) {
        set<char> s;
        for (int i=0;i<brokenLetters.size();i++){
            s.insert(brokenLetters[i]);
        }
        bool flag = true;
        int ans =0;
        for (int i=0;i<text.size();i++){
            if (text[i]==' '){
                if (flag){
                    ans++;
                }
                flag = true;
            }else{
                if (s.find(text[i])!=s.end()){
                    flag = false;
                }
            }
        }
        if (flag){
            ans++;
        }
        return ans;
    }
};

2197. 替换数组中的非互质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        vector<int> ans;
        
        for (int num : nums) {
            ans.push_back(num);
            
            // 持续合并非互质相邻元素
            while (ans.size() > 1) {
                int g = gcd(ans[ans.size()-1], ans[ans.size()-2]);
                if (g > 1) {
                    long long lcm = (long long)ans[ans.size()-1] * ans[ans.size()-2] / g;
                    ans.pop_back();
                    ans.pop_back();
                    ans.push_back(lcm);
                } else {
                    break;
                }
            }
        }
        
        return ans;
    }
    
private:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};

2349. 设计数字容器系统

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class NumberContainers {
private:
    unordered_map<int, int> nums;
    unordered_map<int, set<int>> us;
public:
    NumberContainers() {
        
    }
    
    void change(int index, int number) {
        if (nums[index] != 0) {
            us[nums[index]].erase(index);
        }
        us[number].insert(index);
        nums[index] = number;
    }
    
    int find(int number) {
        if (us[number].empty()) {
            return -1;
        }
        return *us[number].begin();
    }
};

另一个办法是优先队列

3408. 设计任务管理器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class TaskManager {
private:
    unordered_map<int, pair<int, int>> taskInfo;
    priority_queue<pair<int, int>> heap;
    
public:
    TaskManager(vector<vector<int>> tasks) {
        for (auto& task : tasks) {
            int userId = task[0], taskId = task[1], priority = task[2];
            taskInfo[taskId] = {priority, userId};
            pair<int,int> p {priority,taskId};
            heap.push(p);
        }
    }
    
    void add(int userId, int taskId, int priority) {
        taskInfo[taskId] = {priority, userId};
        pair<int,int> p {priority,taskId};
        heap.push(p);
    }
    
    void edit(int taskId, int newPriority) {
        if (taskInfo.find(taskId) != taskInfo.end()) {
            taskInfo[taskId].first = newPriority;
            pair<int,int> p {newPriority,taskId};
            heap.push(p);
        }
    }
    
    void rmv(int taskId) {
        taskInfo.erase(taskId);
    }
    
    int execTop() {
        while (!heap.empty()) {
            auto [priority, taskId] = heap.top();
            heap.pop();
            
            if (taskInfo.find(taskId) != taskInfo.end() && 
                taskInfo[taskId].first == priority) {
                int userId = taskInfo[taskId].second;
                taskInfo.erase(taskId);
                return userId;
            }
        }
        return -1;
    }
};