数据结构与算法
[(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 int *nums;nums=(*int )malloc (10 *sizeof (int )); long long a;scanf ("%lld" ,&a);printf ("%lld" ,a);
scanf还会返回成功输入的变量的个数,因此可判定EOF
Floyd判圈法很吊
1.lower_bound(v.begin(), v.end(), key)-v.begin()返回有序序列中大于等于key的第一个值的位置())-v.begin()返回有序序列中小于等于key的第一个值的位置())-v.begin()返回有序序列中小于key的第一个值的位置
文件操作
1 2 freopen ("1.in" ,"r" ,stdin);freopen ("1.out" ,"w" ,stdout);
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) {} * };
一些常用的库
algorithm
vector
map
queue
iostream
string
bits/stdc++.h（带上就对了，不过mac的clang不支持，GCC支持）
cmath(sqrt之类的)
climits（INT_MAX INT_MIN）
STL内置find()复杂度 ：algorithm的find 复杂度是O(n)，对vector，string等 顺序查询。map::find 和 set::find 复杂度是O(logn)，因为map和set底层都是红黑树。
vector: 下面是一些常用的vector方法：
push_back：在vector的末尾添加一个元素。
pop_back：删除vector末尾的一个元素。
size：返回vector中元素的个数。
clear：删除vector中所有的元素。
empty：判断vector是否为空。
at：返回vector中指定位置的元素。
front：返回第一个元素。
back：返回最后一个元素。
erase：删除vector中指定位置的元素。
insert：在vector中指定位置插入一个元素或多个元素。
std::vector<int> vec = {1, 2, 3};
// 在开头插入3个值为0的元素
vec.insert(vec.begin(), 3, 0);
1 2 3 4 5 6 7 8 9 11. `resize`：改变vector的大小。 12. `reserve`：为vector预留一定的空间。 ```c++ reverse(a.begin(),a.end());
swap：交换两个vector中的元素。
begin：返回指向vector第一个元素的迭代器。
end：返回指向vector最后一个元素之后的迭代器。 这些方法能够满足大部分情况下的需求，可以根据具体的使用场景选择合适的方法进行操作。
要取迭代器的值，直接*指针取值
对于向量(vector)，它是一种支持随机访问的容器，因此可以直接通过下标访问向量中的元素 。
1 2 3 4 5 vector<int > v = {1 , 2 , 3 , 4 , 5 }; for (auto it = v.begin (); it != v.end (); it++) { cout << *it << " " ; }
vector不能直接使用sort函数进行排序，需要传入一个迭代器指定排序的范围。修改代码如下：
sort(v.begin(),v.end(),com);
map 以下是C++中map类的常用方法：
insert(make_pair<key, value>)：向map中插入一个键值对。
erase(key) ：删除map中指定键的元素。
clear() ：清空map中所有元素。
size()：返回map中元素的个数。
empty()：返回map是否为空。
find(key)：查找map中是否存在指定键的元素，如果存在则返回指向该元素的迭代器，否则返回end()迭代器。
常常和end联合起来用判断找到没。(这个适合动态查找，底层红黑树实现 )
e.g. if (m.find(key)!=m.end())
count(key)：返回指定键在map中出现的次数，如果不存在则返回0或1。
begin()：返回指向map第一个元素的迭代器。
end()：返回指向map最后一个元素后面的位置的迭代器。
operator[]：通过键访问map中的元素，如果键不存在，则自动插入一个新的键值对并返回对应的值。
lower_bound(key)：返回第一个大于或等于指定键的元素的迭代器。
upper_bound(key)：返回第一个大于指定键的元素的迭代器。
equal_range(key)：返回一个pair对象，其中包含lower_bound和upper_bound返回的迭代器。
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 }}; for (auto it = m.begin (); it != m.end (); it++) { cout << it->first << ": " << it->second << endl; }
pair
这里注意pair的用法
1 2 3 4 5 6 7 8 const pair<int,int>mapping[]={ {1:2}, {2:3}, } const auto &[k,v] : mapping{ }
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的常用方法：
push(element)：将一个元素加入队列的尾部。
pop()：将队列头部的元素弹出，但没有返回值。
front()：返回队列头部的元素。
back()：返回队列尾部的元素。
empty()：判断队列是否为空。
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 >, 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是必须要有的
注意这里的重载运算符跟后面的想要大顶堆还是小顶堆有关系。如果要小顶堆,greater这里,其实要重写的就只有operator>,如果是大顶堆，要重写operator<
string C++中的string类是一个封装了字符串操作的类，提供了一系列方法来处理和操作字符串。以下是常用的string类方法：
length()：返回字符串的长度。
size()：返回字符串的长度。
clear()：清空字符串。
empty()：判断字符串是否为空。
assign(str)：将字符串的值设置为str。
assign(str, pos, len)：将字符串的值设置为str中从pos位置开始的长度为len的子串。
append(str)：在字符串的末尾添加str。
append(str, pos, len)：在字符串的末尾添加str中从pos位置开始的长度为len的子串。
push_back(ch)：在字符串的末尾添加一个字符。
insert(pos, str)：在字符串的pos位置插入str。
erase(pos, len)：删除从pos位置开始长度为len的子串。
erase(n):删除indexn后面的字符
replace(pos, len, str)：替换从pos位置开始长度为len的子串为str。
substr(pos, len)：返回从pos位置开始长度为len的子串。
find(str)：查找str在字符串中第一次出现的位置，返回该位置的索引值。 (找不到就是-1)
rfind(str)：查找str在字符串中最后一次出现的位置，返回该位置的索引值。
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 position = s.find ("jk" ); if (position != s.npos) { cout << "position: " << position << endl; } else { cout << "Not found the flag" << endl; }
如果输入的字符串有空格，那么用如下代码
可以直接通过下标修改字符
删除字符串内重复字符:
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 ());
1 2 #include <string> string::erase (begin,end)：删除[begin,end)之间的所有值c
在Find the Smallest Number中，我发现string的超出index一位的位置依然可以访问，但是没有数
algorithm C++标准库中的algorithm库提供了许多常用的算法，这些算法可以用于处理容器中的数据，例如排序、查找、遍历等。以下是algorithm库中常用的方法：
sort(first, last, func)：对[first, last)区间内的元素进行升/降序排序（取决于func返回）。
reverse(first, last)：对[first, last)区间内的元素进行翻转。
find(first, last, val)：在[first, last)区间内查找值为val的元素，返回该元素的迭代器。如果没有找到，返回last。
find_if(first, last, pred)：在[first, last)区间内查找满足条件pred的第一个元素，返回该元素的迭代器。如果没有找到，返回last。
count(first, last, val)：统计[first, last)区间内值为val的元素个数。
count_if(first, last, pred)：统计[first, last)区间内满足条件pred的元素个数。
accumulate(first, last, init)：对[first, last)区间内的元素进行累加，初始值为init。
max_element(first, last)：返回[first, last)区间内的最大元素的迭代器。
min_element(first, last)：返回[first, last)区间内的最小元素的迭代器。
unique(first, last)：对[first, last)区间内的元素去重，返回去重后的末尾迭代器。
remove(first, last, val)：删除[first, last)区间内值为val的元素，返回删除后的末尾迭代器。
remove_if(first, last, pred)：删除[first, last)区间内满足条件pred的元素，返回删除后的末尾迭代器。
for_each(first, last, func)：对[first, last)区间内的元素执行操作func。
transform(first1, last1, first2, result, op)：将[first1, last1)区间内的元素和[first2, …)区间内的元素进行op操作，并将结果存储到[result, …)区间内。
climits
中定义的常量主要有以下几种：
整数类型的最大值和最小值：INT_MAX、INT_MIN、LONG_MAX、LONG_MIN、SHRT_MAX、SHRT_MIN等等。
字符类型的最大值和最小值：CHAR_MAX、CHAR_MIN、SCHAR_MAX、SCHAR_MIN、UCHAR_MAX等等。
位数相关的常量：CHAR_BIT、INT_BIT、LONG_BIT等等。
其他常量：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; mySet.insert (10 ); mySet.insert (20 ); mySet.insert (5 ); mySet.insert (10 ); mySet.insert ({1 , 3 , 7 , 9 }); 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 }; auto it = mySet.find (5 ); if (it != mySet.end ()) { std::cout << "找到元素: " << *it << std::endl; } else { std::cout << "未找到元素" << std::endl; } if (mySet.count (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); } return 0 ; }
utility:
在 C++ 中，pair模板类 ，定义在头文件 <utility> 中，用于将两个值（可以是不同类型）组合成一个单元 。
🧩 一、基本定义
1 2 3 4 #include <utility> using namespace std;pair<T1, T2> p;
T1：第一个元素的类型T2：第二个元素的类型p.first：访问第一个元素p.second：访问第二个元素
✅ 二、创建 pair 的几种方式
直接初始化
1 pair<int , string> p1 (10 , "hello" ) ;
使用 make_pair（自动推导类型）
1 auto p2 = make_pair (20 , "world" );
✅ 推荐使用 make_pair，简洁且避免手动写类型。
使用花括号初始化（C++11 起）
1 pair<int , double > p3{30 , 3.14 };
赋值构造
1 2 pair<string, int > p4; p4 = make_pair ("age" , 25 );
🔍 三、访问元素
1 2 cout << p1.f irst << endl; cout << p1. second << endl;
🔄 四、比较操作
pair 支持 ==, !=, <, <=, >, >=，比较规则是：
先比较 first
如果 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; cout << (a < c) << endl;
✅ 这使得 pair 非常适合用作 map 的键、或在 set、priority_queue 中排序。
📦 五、常用场景
作为函数返回多个值
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;
在 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; }
💡 map::value_type 就是 pair<const Key, T>
优先队列中自定义优先级
1 2 3 4 5 6 7 8 9 10 11 12 13 priority_queue<pair<int , string>> pq; 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 (); }
🆚 六、pair vs tuple
特性
pair<T1, T2>tuple<T1, T2, T3, ...>
元素个数
固定 2 个
任意多个
访问方式
.first, .secondget<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;
✅ 非常适合用于循环或函数返回值解包：
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<int , string> p1 = make_pair (1 , "apple" ); pair<int , string> p2{2 , "banana" }; cout << p1.f irst << ": " << p1. second << endl; if (p1 < p2) { cout << "p1 < p2" << endl; } vector<pair<int , string>> vec; vec.push_back (p1); vec.push_back (p2); sort (vec.begin (), vec.end ()); for (const auto & p : vec) { cout << p.first << " - " << p.second << endl; } 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; 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> struct Compare { bool operator () (const std::string& a, const std::string& b) const return a.length () < b.length (); } }; 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" ); 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> 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; std::cout << "10出现次数: " << multiSet.count (10 ) << std::endl; 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 void GetNext (char * p,int next[]) int pLen = strlen (p); next[0 ] = -1 ; int k = -1 ; int j = 0 ; while (j < pLen - 1 ) { 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 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) { if (j == -1 || s[i] == p[j]) { i++; j++; } else { 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
(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 ]; int i = low, j = mid + 1 , k = 0 ; while (i <= mid && j <= hight) { if (a[i] <= a[j]) { b[k++] = a[i++]; } else { b[k++] = a[j++]; } } while (i <= mid) { b[k++] = a[i++]; } while (j <= hight) { b[k++] = a[j++]; } k = 0 ; for (int i = low; i <= hight; i++) { 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); mergesort (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; 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]); } 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 ; } 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++){ 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 ; mark[i] = false ; } Dis[1 ] = 0 ; mark[1 ] = true ; int newP = 1 ; for (int i = 1 ;i < n;i ++) { 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 ; 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 ; if (Dis[j] == -1 ) continue ; if (Dis[j] < min) { 边到达时距离小于当前最小值 min = Dis[j]; newP = j; }
欧拉回路（hierholzer）
(462条消息) 欧拉回路（hierholzer算法）_逐步插入回路法_run around的博客-CSDN博客
关键路径（AOE网）
最早开始时间=最晚开始时间
用拓扑图
最早开始时间（所有先序活动的最晚完成时间）
最晚开始时间（所有后续活动的最早开始时间减去该活动花费的时间）
注意源点的最早开始时间不一定为0，要初始化
汇点的最晚开始时间初始化为totalTime-该汇点任务的时间
非汇点的最晚开始时间为无穷
如果只是要求关键路径的长度，其实在earliest[i]初始化的时候就设置为任务的时间就行，但如果要算其他的，就还是设置为0
7 5
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 ++) 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:
经典贪心
(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;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; 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)); 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 ; int n;char g[N][N];bool col[N], dg[N], udg[N]; void dfs (int u) if (u == n) { for (int i = 0 ; i < n; i ++ ) puts (g[i]); puts ("" ); return ; } int x = u; for (int y = 0 ; y < n; y ++ ) 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
hot 100+面试经典150
12.13-12.14
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 Solution {public : void merge (vector<int >& nums1, int m, vector<int >& nums2, int n) int tail1=m-1 ; int tail2=n-1 ; int tail=m+n-1 ; while (tail1>=0 ||tail2>=0 ){ if (tail1==-1 ){ nums1[tail]=nums2[tail2]; tail2--; }else if (tail2==-1 ){ nums1[tail]=nums1[tail1]; tail1--; }else if (nums1[tail1]>=nums2[tail2]){ nums1[tail]=nums1[tail1]; tail1--; }else if (nums1[tail1]<nums2[tail2]){ nums1[tail]=nums2[tail2]; tail2--; } tail--; } return ; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : int removeElement (vector<int >& nums, int val) int k = 0 ; for (int i = 0 ; i < nums.size (); i++) { if (nums[i] != val) { nums[k] = nums[i]; k++; } } return k; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : int removeDuplicates (vector<int >& nums) int size = nums.size (); if (size<=2 ){ return size; } int slow=2 ; int fast=2 ; while (fast<size){ if (nums[slow-2 ]!=nums[fast]){ nums[slow]=nums[fast]; slow++; } fast++; } return slow; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution {public : int majorityElement (vector<int >& nums) int size=nums.size (); map<int ,int >mapping; for (int num : nums){ mapping[num]+=1 ; if (mapping[num]>size/2 ){ return num; } } 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 class Solution {public : void rotate (vector<int >& nums, int k) k = k%nums.size (); if (k==0 ){ return ; } vector<int >temp; for (int i=nums.size ()-k;i<nums.size ();i++){ temp.push_back (nums[i]); } int start = nums.size ()-k-1 ; int i = nums.size ()-1 ; while (start>=0 ){ nums[i]=nums[start]; start--; i--; } for (int i=0 ;i<k;i++){ nums[i]=temp[i]; } return ; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution {public : int maxProfit (vector<int >& prices) if (prices.size ()==1 ){ return 0 ; } const int size = prices.size (); int max_num=0 ; int ans=0 ; for (int i=prices.size ()-1 ;i>=0 ;i--){ if (prices[i]>max_num){ max_num=prices[i]; } if (i>=1 ){ if (max_num-prices[i-1 ]>ans){ ans = max_num-prices[i-1 ]; } } } return ans; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : int maxProfit (vector<int >& prices) int size = prices.size (); if (size==1 ){ return 0 ; } int dp[size][2 ]; dp[0 ][1 ]=-prices[0 ]; dp[0 ][0 ]=0 ; for (int i=1 ;i<size;i++){ dp[i][1 ]=max (dp[i-1 ][1 ],dp[i-1 ][0 ]-prices[i]); dp[i][0 ]=max (dp[i-1 ][0 ],dp[i-1 ][1 ]+prices[i]); } return dp[size-1 ][0 ]; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : bool canJump (vector<int >& nums) int size = nums.size (); vector<bool > reach (size,false ) ; reach[0 ]=true ; for (int i=0 ;i<size;i++){ if (reach[i]){ int maxJump = min (i + nums[i], size - 1 ); for (int j=i;j<=maxJump;j++){ reach[j]=true ; } } } return reach[size-1 ]; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : int jump (vector<int >& nums) int size =nums.size (); vector<bool >reach (size,false ); reach[0 ]=true ; vector<int >dp (size,size); dp[0 ]=0 ; for (int i=0 ;i<size;i++){ if (reach[i]){ int max_jump = min (size-1 ,i+nums[i]); for (int j=i;j<=max_jump;j++){ reach[j]=true ; dp[j]=min (dp[j],dp[i]+1 ); } } } return dp[size-1 ]; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: int hIndex(vector<int>& citations) { int count[1000+1]={0}; for (int num: citations){ count[num]++; } int suffix_sum[1001]={0}; for (int i=1000;i>=0;i--){ if (i==1000){ suffix_sum[i]=count[i]; }else{ suffix_sum[i]=count[i]+suffix_sum[i+1]; } if (suffix_sum[i]>=i){ return i; } } 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 class RandomizedSet {public : RandomizedSet () { } bool insert (int val) if (indexs.count (val) == 1 ){ return false ; } nums.push_back (val); indexs[val] = nums.size () - 1 ; return true ; } bool remove (int val) if (!indexs.count (val)){ return false ; } int index = indexs[val]; int last = nums.back (); nums[index] = last; nums.pop_back (); indexs[last] = index; indexs.erase (val); return true ; } int getRandom () int index = rand () % nums.size (); return nums[index]; } private : vector<int > nums; unordered_map<int , int > indexs; };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution {public : vector<int > productExceptSelf (vector<int >& nums) { int size=nums.size (); vector<int >left (size+1 ,0 ); vector<int >right (size+1 ,0 ); left[0 ]=1 ; right[size]=1 ; for (int i=0 ;i<size;i++){ left[i+1 ]=left[i]*nums[i]; } for (int i=size-1 ;i>=0 ;i--){ right[i]=right[i+1 ]*nums[i]; } vector<int >ans (size,0 ); for (int i=0 ;i<size;i++){ ans[i]=left[i]*right[i+1 ]; } 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 canCompleteCircuit (vector<int >& gas, vector<int >& cost) int n = gas.size (); int i = 0 ; while (i < n) { int sumOfGas = 0 , sumOfCost = 0 ; int cnt = 0 ; while (cnt < n) { int j = (i + cnt) % n; sumOfGas += gas[j]; sumOfCost += cost[j]; if (sumOfCost > sumOfGas) { break ; } cnt++; } if (cnt == n) { return i; } else { i = i + cnt + 1 ; } } 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 32 class Solution {public : int candy (vector<int >& ratings) int n = ratings.size (); int pre = 1 ; int ans = 1 ; int inc =1 ; int dec = 0 ; for (int i=1 ;i<n;i++){ if (ratings[i]>ratings[i-1 ]){ pre = pre+1 ; ans +=pre; inc = pre; dec =0 ; }else if (ratings[i]==ratings[i-1 ]){ pre =1 ; ans+=pre; inc=pre; dec =0 ; }else { dec++; if (dec==inc){ dec++; } ans +=dec; pre = 1 ; } } return ans; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : int trap (vector<int >& height) int size = height.size (); vector<int >left_max (size,0 ); vector<int >right_max (size,0 ); for (int i=1 ;i<size;i++){ left_max[i]=max (left_max[i-1 ],height[i-1 ]); } for (int i=size-2 ;i>=0 ;i--){ right_max[i]=max (right_max[i+1 ],height[i+1 ]); } int ans=0 ; for (int i=0 ;i<size;i++){ ans+=max (0 ,(min (left_max[i],right_max[i])-height[i])); } 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 {private : map<char ,int >mapping={ {'I' ,1 }, {'V' , 5 }, {'X' , 10 }, {'L' , 50 }, {'C' , 100 }, {'D' , 500 }, {'M' , 1000 }, }; public : int romanToInt (string s) int ans =0 ; int size = s.size (); for (int i=0 ;i<size;i++){ int v = mapping[s[i]]; if (i<size-1 &&v<mapping[s[i+1 ]]){ ans-=v; }else { ans+=v; } } 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 27 28 29 30 31 32 const pair<int ,string>mapping[]={ {1000 , "M" }, {900 , "CM" }, {500 , "D" }, {400 , "CD" }, {100 , "C" }, {90 , "XC" }, {50 , "L" }, {40 , "XL" }, {10 , "X" }, {9 , "IX" }, {5 , "V" }, {4 , "IV" }, {1 , "I" }, }; class Solution { public : string intToRoman (int num) { string ans; for (const auto & [k,v]: mapping){ while (num>=k){ num-=k; ans+=v; } if (num==0 ){ break ; } } 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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution {public : string longestCommonPrefix (vector<string>& strs) { if (strs.size ()==0 ){ return "" ; } int length =1 ; string ans="" ; while (1 ){ if (length > strs[0 ].size ()) { return ans; } string prefix = strs[0 ].substr (0 , length); bool match = true ; for (int i = 1 ; i < strs.size (); i++) { if (length > strs[i].size () || strs[i].substr (0 , length) != prefix) { match = false ; break ; } } if (match) { ans = prefix; length++; } else { break ; } } return ans; } };
这里c++很不好做，Python两行搞定
1 2 3 4 5 class Solution : def lengthOfLastWord (self, s: str ) -> int : ss = s.split() return len (ss[len (ss)-1 ])
这里的s.split是默认去掉所有空格
依旧python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution : def reverseWords (self, s: str ) -> str : ss = s.split() ss.reverse() ans="" for i,s in enumerate (ss): if i==len (ss)-1 : ans=ans+s else : ans=ans+s+" " return ans class Solution : def reverseWords (self, s: str ) -> str : ss = s.split() ss.reverse() return " " .join(ss)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution {public : string convert (string s, int numRows) { if (numRows==1 ){ return s; } vector<string>ss (numRows); int i=0 ; int flag=-1 ; for (char c : s){ ss[i].push_back (c); if (i==0 || i==numRows-1 ){ flag=-flag; } i=i+flag; } string ans="" ; for (string temp: ss){ ans+=temp; } return ans; }};
std::string 是字符容器
std::string 本质上是一个存储 char 类型的容器它提供了类似于 std::vector<char> 的接口
1 2 3 4 ss[i].push_back (c); ss[i] += c; ss[i].append (1 , c);
但字符不能直接跟字符拼接
1 2 3 4 5 6 class Solution {public : int strStr (string haystack, string needle) return haystack.find (needle); } };
原来string初始化能直接string(length,char)的吗
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 class Solution { string blank (int n) { return string (n, ' ' ); } string join (vector<string> &words, int left, int right, string sep) { string s = words[left]; for (int i = left + 1 ; i < right; ++i) { s += sep + words[i]; } return s; } public : vector<string> fullJustify (vector<string> &words, int maxWidth) { vector<string> ans; int right = 0 , n = words.size (); while (true ) { int left = right; int sumLen = 0 ; while (right < n && sumLen + words[right].length () + right - left <= maxWidth) { sumLen += words[right++].length (); } if (right == n) { string s = join (words, left, n, " " ); ans.emplace_back (s + blank (maxWidth - s.length ())); return ans; } int numWords = right - left; int numSpaces = maxWidth - sumLen; if (numWords == 1 ) { ans.emplace_back (words[left] + blank (numSpaces)); continue ; } int avgSpaces = numSpaces / (numWords - 1 ); int extraSpaces = numSpaces % (numWords - 1 ); string s1 = join (words, left, left + extraSpaces + 1 , blank (avgSpaces + 1 )); string s2 = join (words, left + extraSpaces + 1 , right, blank (avgSpaces)); ans.emplace_back (s1 + blank (avgSpaces) + s2); } } };
这种模拟题就纯恶心来着
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : bool isPalindrome (string s) string sgood; for (char ch: s) { if (isalnum (ch)) { sgood += tolower (ch); } } string sgood_rev (sgood.rbegin(), sgood.rend()) ; return sgood == sgood_rev; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution {public : bool isSubsequence (string s, string t) int m = s.size (); int n = t.size (); int j=0 ; for (int i=0 ;i<n;i++){ if (s[j]==t[i]){ j++; } } return j==m; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : vector<int > twoSum (vector<int >& numbers, int target) { map<int ,int >mapping; vector<int >ans; for (int i=0 ;i<numbers.size ();i++){ if (mapping.count (target-numbers[i])!=0 ){ if (mapping[target-numbers[i]]!=i){ ans.push_back (mapping[target-numbers[i]]+1 ); ans.push_back (i+1 ); return ans; } } mapping[numbers[i]]=i; } return ans; } };
这里注意数据范围，暴力必定超时，直接双指针就好
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : int maxArea (vector<int >& height) int size = height.size (); int left = 0 ; int right = size-1 ; int ans=0 ; while (left<right){ ans = max (ans,(right-left)*min (height[left],height[right])); if (height[left]<height[right]){ left++; }else { right--; } } 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 27 28 29 30 31 class Solution {public : vector<vector<int >> threeSum (vector<int >& nums) { int size = nums.size (); sort (nums.begin (),nums.end ()); vector<vector<int >>ans; for (int first=0 ;first<size;first++){ if (first>0 &&nums[first]==nums[first-1 ]){ continue ; } int third=size-1 ; int target = -nums[first]; for (int second=first+1 ;second<size;second++){ if (second>first+1 && nums[second]==nums[second-1 ]){ continue ; } while (second<third&&nums[second]+nums[third]>target){ third--; } 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 class Solution {public : int minSubArrayLen (int target, vector<int >& nums) int size = nums.size (); vector<int > prefix_sum (size+1 ,0 ) ; for (int i=1 ;i<=size;i++){ prefix_sum[i]+=prefix_sum[i-1 ]+nums[i-1 ]; } int slow=0 ,fast=1 ; int ans = size+1 ; while (fast<=size){ if (prefix_sum[fast]-prefix_sum[slow]>=target){ ans = min (ans,fast-slow); slow++; }else { fast++; } } if (ans==size+1 ){ return 0 ; } 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 class Solution {public : int lengthOfLongestSubstring (string s) map<char ,int >mapping; int slow =0 ; int fast=0 ; int size =s.size (); int ans = 0 ; while (fast<size){ if (mapping.count (s[fast])==0 ){ mapping[s[fast]]=1 ; fast++; ans = max (ans,fast-slow); }else { while (s[slow]!=s[fast]){ mapping.erase (s[slow]); slow++; } mapping.erase (s[slow]); slow++; } } return ans; } };
12.15
滑动窗口挺有意思
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 class Solution {public : vector<int > findSubstring (string s, vector<string>& words) { int size = words.size (); int length = s.size (); int word_size = words[0 ].size (); vector<int >ans; for (int i=0 ;i<word_size&&i+size*word_size<=length;i++){ map<string,int >mapping; for (int j=0 ;j<size;j++){ mapping[s.substr (i+j*word_size,word_size)]++; } for (string word : words){ mapping[word]--; if (mapping[word]==0 ){ mapping.erase (word); } } for (int start=i;start<length-size*word_size+1 ;start+=word_size){ if (start!=i){ string temp=s.substr (start-word_size,word_size); if (--mapping[temp]==0 ){ mapping.erase (temp); } temp = s.substr (start+word_size*(size-1 ),word_size); if (++mapping[temp]==0 ){ mapping.erase (temp); } } if (mapping.empty ()){ ans.push_back (start); } } } 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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution {public : string minWindow (string s, string t) { unordered_map<char ,int >mapping_t ; unordered_map<char ,int >current; for (char c : t){ mapping_t [c]+=1 ; } int length = s.size ()+1 ; int l=0 ; int r=0 ; int ans_l=-1 ; while (r<s.size ()){ if (mapping_t .find (s[r])!=mapping_t .end ()){ current[s[r]]++; } while (check_ok (mapping_t ,current)&&l<=r){ if (r-l+1 <length){ length=r-l+1 ; ans_l=l; } if (mapping_t .find (s[l])!=mapping_t .end ()){ current[s[l]]--; } l++; } r++; } if (length==s.size ()+1 ){ return "" ; } return s.substr (ans_l,length); } bool check_ok (unordered_map<char ,int > t,unordered_map<char ,int > current) for (auto [k,v]:t){ if (current[k]<v){ return false ; } } return true ; } };
12.16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution {public : bool isValidSudoku (vector<vector<char >>& board) vector<vector<int >>rows (9 ,vector <int >(9 ,0 )); vector<vector<int >>cols (9 ,vector <int >(9 ,0 )); vector<vector<vector<int >>>kuang (3 ,vector<vector<int >>(3 ,vector <int >(9 ,0 ))); for (int i=0 ;i<9 ;i++){ for (int j=0 ;j<9 ;j++){ if (board[i][j]!='.' ){ int index = board[i][j]-'0' -1 ; rows[i][index]+=1 ; cols[j][index]+=1 ; kuang[i/3 ][j/3 ][index]+=1 ; if (rows[i][index]>1 ||cols[j][index]>1 ||kuang[i/3 ][j/3 ][index]>1 ){ return false ; } } } } return true ; } };
这里另一种方式是
1 2 3 4 5 6 7 int rows[9 ][9 ];int columns[9 ][9 ];int subboxes[3 ][3 ][9 ];memset (rows,0 ,sizeof (rows));memset (columns,0 ,sizeof (columns));memset (subboxes,0 ,sizeof (subboxes));
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<int > spiralOrder (vector<vector<int >>& matrix) { int m = matrix.size (); int n = matrix[0 ].size (); vector<vector<bool >>visited (m,vector <bool >(n,false )); vector<int >ans; int step=0 ; int total=m*n; int direction=0 ; map<int , vector<int >> mapping = { {0 , {0 , 1 }}, {1 , {1 , 0 }}, {2 , {0 , -1 }}, {3 , {-1 , 0 }} }; int current_x=0 ; int current_y=0 ; while (step<total){ ans.push_back (matrix[current_x][current_y]); visited[current_x][current_y]=true ; step++; if (direction==0 &&(current_y==n-1 ||visited[current_x][current_y+1 ])){ direction=1 ; }else if (direction==1 &&(current_x==m-1 ||visited[current_x+1 ][current_y])){ direction=2 ; }else if (direction==2 &&(current_y==0 ||visited[current_x][current_y-1 ])){ direction=3 ; }else if (direction==3 &&(current_x==0 ||visited[current_x-1 ][current_y])){ direction=0 ; } current_x+=mapping[direction][0 ]; current_y+=mapping[direction][1 ]; } return ans; } };
这里注意mapping中的vector初始化是{}
在 C++ 中，初始化 vector、map、array 等容器，请始终使用 {}，而不是 [] 。[] 只用于访问元素 （如 vec[0]），不能用于初始化 。
倒不是说有多难，就是找准位置关系，水平翻转+对角线翻转
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : void rotate (vector<vector<int >>& matrix) int n = matrix.size (); for (int i = 0 ; i < n / 2 ; ++i) { for (int j = 0 ; j < n; ++j) { swap (matrix[i][j], matrix[n - i - 1 ][j]); } } for (int i = 0 ; i < n; ++i) { for (int j = 0 ; j < i; ++j) { swap (matrix[i][j], matrix[j][i]); } } } };
12.17
有点过于简单了
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 : void setZeroes (vector<vector<int >>& matrix) int m=matrix.size (); int n=matrix[0 ].size (); vector<pair<int ,int >>zeros; for (int i = 0 ;i<m;i++){ for (int j=0 ;j<n;j++){ if (matrix[i][j]==0 ){ zeros.push_back (pair <int ,int >(i,j)); } } } for (auto [i,j]:zeros){ setZero (i,j,matrix); } return ; } void setZero (int i,int j,vector<vector<int >>& matrix) int m=matrix.size (); int n=matrix[0 ].size (); for (int q=0 ;q<m;q++){ matrix[q][j]=0 ; } for (int p=0 ;p<n;p++){ matrix[i][p]=0 ; } return ; } };
ez
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 class Solution {public : void gameOfLife (vector<vector<int >>& board) int m=board.size (); int n= board[0 ].size (); vector<vector<int >>state (m,vector <int >(n,0 )); for (int i=0 ;i<m;i++){ for (int j=0 ;j<n;j++){ int live_count=count_live (i,j,board); if (board[i][j]){ if (live_count<2 ||live_count>3 ){ state[i][j]=0 ; }else { state[i][j]=1 ; } }else { if (live_count==3 ){ state[i][j]=1 ; } } } } for (int i=0 ;i<m;i++){ for (int j=0 ;j<n;j++){ board[i][j]=state[i][j]; } } } int count_live (int i,int j,vector<vector<int >>& board) int ans=0 ; int m=board.size (); int n= board[0 ].size (); if (i>0 ) ans+=board[i-1 ][j]; if (i>0 &&j>0 ) ans+=board[i-1 ][j-1 ]; if (i>0 &&j<n-1 ) ans+=board[i-1 ][j+1 ]; if (i<m-1 &&j>0 ) ans+=board[i+1 ][j-1 ]; if (i<m-1 &&j<n-1 ) ans+=board[i+1 ][j+1 ]; if (i<m-1 ) ans+=board[i+1 ][j]; if (j>0 ) ans+=board[i][j-1 ]; if (j<n-1 ) ans+=board[i][j+1 ]; return ans; } };
12.18
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}; } } 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 ; }
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; }
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 : 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 (); } };
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]; } };
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 ; } };
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.f ind(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.f ind(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; for (int first = 0 ; first < n; ++first) { if (first > 0 && nums[first] == nums[first - 1 ]) { continue ; } int third = n - 1 ; int target = -nums[first]; for (int second = first + 1 ; second < n; ++second) { if (second > first + 1 && nums[second] == nums[second - 1 ]) { continue ; } while (second < third && nums[second] + nums[third] > target) { --third; } 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.字符串元音游戏
感觉就是个博弈问题。
如果当前剩下的所有的字符中包含元音个数为奇数个，她直接赢，反之就是小明赢。
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; } };
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); } };
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 (); } };
另一个办法是优先队列
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 ; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution {public : int smallestNumber (int n) if (n==1 )return 1 ; int small = get_small (n); int big = small*2 ; if (big == n){ return big*2 -1 ; }else { return big-1 ; } } int get_small ( int num) int i=1 ; while (i<num){ i=i*2 ; } return i/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 class Solution {public : int candy (vector<int >& ratings) int n = ratings.size (); int pre = 1 ; int ans = 1 ; int inc =1 ; int dec = 0 ; for (int i=1 ;i<n;i++){ if (ratings[i]>ratings[i-1 ]){ pre = pre+1 ; ans +=pre; inc = pre; dec =0 ; }else if (ratings[i]==ratings[i-1 ]){ pre =1 ; ans+=pre; inc=pre; dec =0 ; }else { dec++; if (dec==inc){ dec++; } ans +=dec; pre = 1 ; } } return ans; } };
这个题有点巧妙，证明用差分数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : int minNumberOperations (vector<int >& target) int length = target.size (); int ans =target[0 ]; for (int i=1 ;i<length;i++){ ans +=max (0 ,target[i]-target[i-1 ]); } return ans; } int max (int a, int b) if (a>b){ return a; } return b; } };
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 class Solution {public : int maxCandies (vector<int >& status, vector<int >& candies, vector<vector<int >>& keys, vector<vector<int >>& containedBoxes, vector<int >& initialBoxes) int n = status.size (); vector<bool > has_key (n, false ) , has_box (n, false ) , opened (n, false ) ; queue<int > q; int ans = 0 ; for (int b : initialBoxes) { has_box[b] = true ; if (status[b] == 1 ) q.push (b); } while (!q.empty ()) { int box = q.front (); q.pop (); if (opened[box]) continue ; opened[box] = true ; ans += candies[box]; for (int k : keys[box]) { if (!has_key[k]) { has_key[k] = true ; if (has_box[k] && !opened[k]) q.push (k); } } for (int b : containedBoxes[box]) { if (!has_box[b]) has_box[b] = true ; if ((status[b] == 1 || has_key[b]) && !opened[b]) q.push (b); } } return ans; } };
