数据结构与算法
[(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在字符串中最后一次出现的位置，返回该位置的索引值。
to_string：将数字转化成字符串
stoi(将字符串转化成整数数字) stod(将字符串转化成浮点数)
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返回）。
vector<int>nums;
sort(nums.begin(),nums.end());
sort(nums.begin(),nums.end(),std::greater<int>());
sort(nums.begin(),nums.end(),[](vector<int>a, vector<int>b){
return a[1]<v[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 3. reverse(first, last)：对[first, last)区间内的元素进行翻转。 4. find(first, last, val)：在[first, last)区间内查找值为val的元素，返回该元素的迭代器。如果没有找到，返回last。 5. find_if(first, last, pred)：在[first, last)区间内查找满足条件pred的第一个元素，返回该元素的迭代器。如果没有找到，返回last。 6. count(first, last, val)：统计[first, last)区间内值为val的元素个数。 7. count_if(first, last, pred)：统计[first, last)区间内满足条件pred的元素个数。 8. accumulate(first, last, init)：对[first, last)区间内的元素进行累加，初始值为init。 9. max_element(first, last)：返回[first, last)区间内的最大元素的迭代器。 10. min_element(first, last)：返回[first, last)区间内的最小元素的迭代器。 11. unique(first, last)：对[first, last)区间内的元素去重，返回去重后的末尾迭代器。 12. remove(first, last, val)：删除[first, last)区间内值为val的元素，返回删除后的末尾迭代器。 13. remove_if(first, last, pred)：删除[first, last)区间内满足条件pred的元素，返回删除后的末尾迭代器。 14. for_each(first, last, func)：对[first, last)区间内的元素执行操作func。 15. transform(first1, last1, first2, result, op)：将[first1, last1)区间内的元素和[first2, ...)区间内的元素进行op操作，并将结果存储到[result, ...)区间内。 ### climits <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 unordered_set ** ** `set` 是C++ STL中的关联容器，具有以下特点： - **自动排序**：元素按升序排列（默认） - **唯一性**：不允许重复元素 - **高效查找**：基于红黑树实现，查找、插入、删除时间复杂度为 O(log n) **头文件和声明** ```cpp #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.19
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : bool canConstruct (string ransomNote, string magazine) map<char ,int >m1; map<char ,int >m2; for (char c : ransomNote){ m1[c]++; } for (char c: magazine){ m2[c]++; } for (auto [k,v]: m1){ if (m2[k]<v){ return false ; } } return true ; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : bool isIsomorphic (string s, string t) map<char ,char >mapping1; map<char ,char >mapping2; for (int i=0 ;i<s.size ();i++){ if (mapping1. count (s[i])==0 &&mapping2. count (t[i])==0 ){ mapping1[s[i]]=t[i]; mapping2[t[i]]=s[i]; }else if (mapping1[s[i]]!=t[i]||mapping2[t[i]]!=s[i]){ return false ; } } return true ; } };
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 class Solution : def wordPattern (self, pattern: str, s: str) -> bool : s_list = s.split () # 长度不匹配直接返回False if len (pattern) ! = len (s_list): return False mapping1 = {} # pattern -> word mapping2 = {} # word -> pattern for i in range (len (pattern)): p = pattern[i] w = s_list[i] # 检查双向映射是否一致 if p in mapping1: if mapping1[p] != w: return False else : mapping1[p] = w if w in mapping2: if mapping2[w] != p: return False else : mapping2[w] = p return True
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 : bool isAnagram (string s, string t) int len1 = s.size (); int len2 = t.size (); if (len1 != len2){ return false ; } map<char ,int >mapping1; map<char ,int >mapping2; for (char c: s){ mapping1[c]++; } for (char c:t){ mapping2[c]++; } for (auto [k,v]: mapping1){ if (mapping2[k]!=v){ return false ; } } return true ; } };,
这波属于是要sort(str.begin(),str.end());
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 class Solution {public : vector<int > twoSum (vector<int >& nums, int target) { vector<int >ans; map<int ,int >map_index; int length = nums.size (); for (int i=0 ;i<length;i++){ if (map_index.count (target-nums[i])!=0 ){ ans.push_back (i); ans.push_back (map_index[target-nums[i]]); return ans; }else { map_index[nums[i]]=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 27 28 29 class Solution {public : bool isHappy (int n) int slow=n; int fast =n; bool flag=false ; while (slow!=1 &&fast!=1 ){ if (flag){ if (slow==fast){ return false ; } } flag=true ; slow=compute_n (slow); fast=compute_n (fast); fast=compute_n (fast); } return true ; } int compute_n (int n) int res=0 ; while (n>0 ){ int temp = n%10 ; res+=temp*temp; n/=10 ; } return res; } };
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 : bool containsNearbyDuplicate (vector<int >& nums, int k) map<int ,int >mapping; int length = nums.size (); for (int i=0 ;i<length;i++){ if (mapping.count (nums[i])!=0 ){ if (abs (mapping[nums[i]]-i)<=k){ return true ; } } mapping[nums[i]]=i; } return false ; } int abs (int a) if (a<0 ){ return -a; } return a; } };
注意set的使用
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 class Solution {public : int longestConsecutive (vector<int >& nums) int ans=0 ; unordered_set<int >us; for (auto num:nums){ us.insert (num); } for (auto num: us){ if (us.count (num-1 )==0 ){ int cn=num; int len=1 ; while (us.count (cn+1 )){ cn++; len++; } ans = max (ans,len); } } return ans; } int max (int a,int b) if (a>b){ return a; } return b; } };
12.20
注意to_string，数字转字符串
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 Solution {public : vector<string> summaryRanges (vector<int >& nums) { vector<string>ans; int slow=0 ; int fast=0 ; int length = nums.size (); while (fast<length&&fast>=slow){ if (fast+1 <length){ if (nums[fast]+1 ==nums[fast+1 ]){ fast++; continue ; }else { if (fast==slow){ string temp = to_string (nums[fast]); ans.push_back (temp); fast++; slow++; }else { string s1 = to_string (nums[slow]); string s2 = to_string (nums[fast]); string temp = s1+"->" +s2; ans.push_back (temp); fast++; slow=fast; } } }else { if (fast==slow){ string temp = to_string (nums[fast]); ans.push_back (temp); }else { string s1 = to_string (nums[slow]); string s2 = to_string (nums[fast]); string temp = s1+"->" +s2; ans.push_back (temp); } 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 class Solution {public : vector<vector<int >> merge (vector<vector<int >>& intervals) { int max_num = -INT_MAX; int size = intervals.size (); if (size ==1 ){ return intervals; } sort (intervals.begin (),intervals.end ()); vector<vector<int >>ans; int slow=0 ; int fast=0 ; max_num=intervals[0 ][1 ]; while (fast<size&&fast>=slow){ if (intervals[fast][0 ]<=max_num){ max_num = max (max_num,intervals[fast][1 ]); fast++; continue ; }else { int num1 = intervals[slow][0 ]; vector<int >temp={num1,max_num}; ans.push_back (temp); slow=fast; max_num=intervals[fast][1 ]; } } vector<int >temp = {intervals[slow][0 ],max_num}; ans.push_back (temp); 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 findMinArrowShots (vector<vector<int >>& points) sort (points.begin (),points.end (),[](vector<int >a,vector<int >b){ return a[1 ]<b[1 ]; }); int length = points.size (); if (length==1 ){ return 1 ; } int ans =0 ; int slow =0 ,fast= 0 ; while (fast<length&&fast>=slow){ if (points[fast][0 ]<=points[slow][1 ]){ fast++; }else { ans++; slow=fast; } } 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 class Solution {public : vector<vector<int >> insert (vector<vector<int >>& intervals, vector<int >& newInterval) { vector<vector<int >>ans; intervals.push_back (newInterval); sort (intervals.begin (),intervals.end ()); int slow=0 ; int fast =0 ; int size=intervals.size (); if (size==1 ){ return intervals; } int max_right = intervals[0 ][1 ]; while (fast>=slow&&fast<size){ if (max_right>=intervals[fast][0 ]){ max_right=max (max_right,intervals[fast][1 ]); fast++; }else { vector<int >temp = {intervals[slow][0 ],max_right}; ans.push_back (temp); max_right = intervals[fast][1 ]; slow=fast; } } vector<int >temp = {intervals[slow][0 ],max_right}; ans.push_back (temp); 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 class Solution {public : bool isValid (string s) stack<char >c_stack; for (char c:s){ if (c=='(' ||c=='{' ||c=='[' ){ c_stack.push (c); }else { if (c==')' ){ if (c_stack.empty ()||c_stack.top ()!='(' ){ return false ; }else { c_stack.pop (); } }else if (c=='}' ){ if (c_stack.empty ()||c_stack.top ()!='{' ){ return false ; }else { c_stack.pop (); } }else if (c==']' ){ if (c_stack.empty ()||c_stack.top ()!='[' ){ return false ; }else { c_stack.pop (); } } } } return c_stack.size ()==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 class Solution {public : string simplifyPath (string path) { string ans; int index = 0 ; string dir = "" ; vector<string> st; path += '/' ; while (index < path.size ()){ char & ch = path[index]; if (ch != '/' ){ dir += ch; index++; continue ; } else if (dir == ".." && !st.empty ()){ st.pop_back (); } else if (dir != ".." && dir != "." && dir != "" ){ st.push_back (dir); } dir = "" ; index++; } for (auto & dir : st){ ans += '/' ; ans += dir; } return ans == "" ? "/" : 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 class MinStack { stack<int >s; stack<int >min_s; public : MinStack () { min_s.push (INT_MAX); } void push (int val) s.push (val); min_s.push (min (min_s.top (),val)); } void pop () s.pop (); min_s.pop (); } int top () return s.top (); } int getMin () return min_s.top (); } };
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 : int evalRPN (vector<string>& tokens) stack<int >num_s; for (string token: tokens){ if (token != "+" && token != "-" && token != "*" && token != "/" ){ int num = stoi (token); num_s.push (num); }else { int num1 = num_s.top (); num_s.pop (); int num2 = num_s.top (); num_s.pop (); if (token=="/" ){ int temp = num2/num1; num_s.push (temp); }else if (token=="+" ){ int temp = num2+num1; num_s.push (temp); }else if (token=="-" ){ int temp = num2-num1; num_s.push (temp); }else { int temp = num2*num1; num_s.push (temp); } } } return num_s.top (); } };
妈的这里只有+和-，用信号转化的方式还是没太容易想到。
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 class Solution {public : int calculate (string s) int sig = 1 ; int ans=0 ; stack<int >ops; ops.push (1 ); int size = s.size (); for (int i =0 ;i<size;i++){ char c = s[i]; if (c==' ' ){ continue ; } if (c=='+' ){ sig=ops.top (); }else if (c=='-' ){ sig = -ops.top (); }else if (c=='(' ){ ops.push (sig); }else if (c==')' ){ ops.pop (); }else { long num = 0 ; while (i<size&&s[i]-'0' <=9 &&s[i]-'0' >=0 ){ num = num*10 +(s[i]-'0' ); i++; } i--; ans+=sig*num; } } 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 : bool hasCycle (ListNode *head) if (head == NULL || head->next == NULL ){ return false ; } ListNode *fast = head->next; ListNode *slow = head; while (fast!=NULL ){ if (fast==slow){ return true ; } fast = fast->next; if (fast==NULL ){ return false ; } fast = fast->next; slow = slow->next; } return false ; } };
这里注意
结构体指针取当中的值用->
根据其构造函数创建新的结构体用new e.g. new ListNode(10);
ListNode(): val(0),next(nullptr) {}
ListNode(int x): val(x), next(nullptr) {}
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 /** * Definition for singly-linked list. * 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) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* c1 = l1; ListNode* c2 = l2; int pre=0; ListNode* ans = NULL; ListNode* tail =NULL; while (c1 !=NULL || c2 != NULL){ int cur = 0; if (c1){ cur +=c1->val; c1=c1->next; } if (c2){ cur += c2->val; c2=c2->next; } cur+=pre; pre = cur/10; if (ans == NULL){ ans =new ListNode(cur%10); tail = ans; }else{ tail->next =new ListNode(cur%10); tail=tail->next; } } if (pre>0){ tail->next =new ListNode(pre); } 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 class Solution {public : ListNode* mergeTwoLists (ListNode* list1, ListNode* list2) { ListNode* dummy = new ListNode (-1 ); ListNode* tail = dummy; while (list1 != nullptr && list2 != nullptr ) { if (list1->val <= list2->val) { tail->next = list1; list1 = list1->next; } else { tail->next = list2; list2 = list2->next; } tail = tail->next; } tail->next = (list1 != nullptr ) ? list1 : list2; ListNode* result = dummy->next; delete dummy; return result; } };
这题有点意思
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 : Node* copyRandomList (Node* head) { if (head==NULL ){ return NULL ; } map<Node*,Node*>mapping; Node* cur =head; while (cur !=NULL ){ Node *temp = new Node (cur->val); mapping[cur]=temp; cur=cur->next; } cur = head; while (cur!=NULL ){ Node * map_cur = mapping[cur]; map_cur->random = mapping[cur->random]; map_cur->next = mapping[cur->next]; cur=cur->next; } return mapping[head]; } };
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 : ListNode* reverseList (ListNode* head) { ListNode* pre = nullptr ; ListNode* cur = head; while (cur){ ListNode* next = cur->next; cur->next = pre; pre=cur; cur=next; } return pre; } };
用vector的解法
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 : ListNode* reverseBetween (ListNode* head, int left, int right) { vector<ListNode*>ns; ListNode*cur =head; ListNode*dump = new ListNode (-1 ); ns.push_back (dump); dump->next = head; while (cur !=NULL ){ ns.push_back (cur); cur= cur->next; } for (int i=left;i<right;i++){ ns[i+1 ]->next = ns[i]; } ns[left-1 ]->next=ns[right]; ns[left]->next=right+1 <ns.size ()?ns[right+1 ]:NULL ; return dump->next; } };
这种原地转圈的巨恶心：
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 : ListNode* reverseBetween (ListNode* head, int left, int right) { ListNode* dummy = new ListNode (-1 ); dummy->next = head; ListNode* pre = dummy; for (int i=0 ;i<left-1 ;i++){ pre = pre->next; } ListNode *cur = pre->next; ListNode *next; for (int i=0 ;i<right-left;i++){ next = cur->next; cur->next =next->next ; next->next = pre->next; pre->next = next; } return dummy->next; } };
12.21
vector的做法
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 : ListNode* reverseKGroup (ListNode* head, int k) { ListNode * dummy = new ListNode (-1 ); dummy->next = head; vector<ListNode*>nodes; ListNode *temp = dummy->next; while (temp!=NULL ){ nodes.push_back (temp); temp=temp->next; } int i = 0 ; int n = nodes.size (); ListNode* prev_tail = dummy; for (int i = 0 ; i + k <= n; i += k) { int start = i; int end = i + k - 1 ; for (int j = end; j > start; j--) { nodes[j]->next = nodes[j - 1 ]; } prev_tail->next = nodes[end]; nodes[start]->next = (end + 1 < n) ? nodes[end + 1 ] : nullptr ; prev_tail = nodes[start]; } return dummy->next; } int min (int a, int b) if (a>b){ return b; } return a; } };
空间复杂度为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 class Solution {public : pair<ListNode*, ListNode*> myReverse (ListNode* head, ListNode* tail) { ListNode* prev = tail->next; ListNode* p = head; while (prev != tail) { ListNode* nex = p->next; p->next = prev; prev = p; p = nex; } return {tail, head}; } ListNode* reverseKGroup (ListNode* head, int k) { ListNode* hair = new ListNode (0 ); hair->next = head; ListNode* pre = hair; while (head) { ListNode* tail = pre; for (int i = 0 ; i < k; ++i) { tail = tail->next; if (!tail) { return hair->next; } } ListNode* nex = tail->next; tie (head, tail) = myReverse (head, tail); pre->next = head; tail->next = nex; pre = tail; head = tail->next; } return hair->next; } };
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 : ListNode* removeNthFromEnd (ListNode* head, int n) { vector<ListNode*>nodes; ListNode *temp = head; while (temp!=NULL ){ nodes.push_back (temp); temp=temp->next; } int index = nodes.size ()-n; if (index!=0 ){ nodes[index-1 ]->next = nodes[index]->next; return head; }else { return head->next; } return NULL ; } };
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 : ListNode* deleteDuplicates (ListNode* head) { ListNode* dummy = new ListNode (0 ); dummy->next = head; ListNode* prev = dummy; while (head) { bool isDuplicate = false ; while (head->next && head->val == head->next->val) { isDuplicate = true ; head = head->next; } if (isDuplicate) { prev->next = head->next; } else { prev = head; } head = head->next; } return dummy->next; } };
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 : ListNode* rotateRight (ListNode* head, int k) { vector<ListNode*>nodes; while (head){ nodes.push_back (head); head=head->next; } int n = nodes.size (); if (n==0 ){ return NULL ; } k = k%nodes.size (); nodes[n-k-1 ]->next =NULL ; if (k!=0 ){ nodes[n-1 ]->next=nodes[0 ]; } return nodes[n-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 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 {public : ListNode* partition (ListNode* head, int x) { if (!head) return nullptr ; vector<ListNode*> small; vector<ListNode*> big; while (head) { if (head->val < x) { small.push_back (head); } else { big.push_back (head); } head = head->next; } ListNode* ans = nullptr ; if (!small.empty ()) { for (int i = 0 ; i < (int )small.size () - 1 ; i++) { small[i]->next = small[i + 1 ]; } ans = small[0 ]; if (!big.empty ()) { small.back ()->next = big[0 ]; } else { small.back ()->next = nullptr ; } } if (!big.empty ()) { for (int i = 0 ; i < (int )big.size () - 1 ; i++) { big[i]->next = big[i + 1 ]; } big.back ()->next = nullptr ; if (small.empty ()) { ans = big[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 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 struct DoubleListNode { int key; int val; DoubleListNode *pre; DoubleListNode *next; DoubleListNode ():val (0 ),next (nullptr ),pre (nullptr ){} DoubleListNode (int x):val (x),next (nullptr ),pre (nullptr ){} DoubleListNode (int x,int y): key (x),val (y),next (nullptr ),pre (nullptr ){} }; class LRUCache { map<int ,DoubleListNode*>mapping; int capacity; int current_size=0 ; DoubleListNode* head; DoubleListNode* tail; public : LRUCache (int capacity) { this ->capacity=capacity; this ->current_size=0 ; this ->head = new DoubleListNode (-100 ); this ->tail = new DoubleListNode (-100 ); head->next= tail; tail->pre=head; } void erase_node (DoubleListNode *node) node->pre->next=node->next; if (node->next) node->next->pre=node->pre; } void move_to_head (DoubleListNode* node) node->next = head->next; if (head->next) head->next->pre=node; head->next= node; node->pre=head; } int get (int key) int ans = -1 ; if (mapping.count (key)){ ans = mapping[key]->val; erase_node (mapping[key]); move_to_head (mapping[key]); } return ans; } void put (int key, int value) if (mapping.count (key)){ mapping[key]->val=value; erase_node (mapping[key]); move_to_head (mapping[key]); }else { if (this ->current_size==this ->capacity){ DoubleListNode *node = tail->pre; erase_node (node); mapping.erase (node->key); }else { this ->current_size++; } DoubleListNode* new_node = new DoubleListNode (key,value); mapping[key]=new_node; move_to_head (new_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 class Solution {public : int maxDepth (TreeNode* root) int depth = 0 ; return getDepth (root,depth); } int getDepth (TreeNode* node,int cur_depth) if (!node){ return cur_depth; } cur_depth++; int left_depth = getDepth (node->left,cur_depth); int right_depth = getDepth (node->right,cur_depth); return left_depth>right_depth?left_depth:right_depth; } };
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 : bool isSameTree (TreeNode* p, TreeNode* q) if (p==nullptr && q==nullptr ){ return true ; }else if (p==nullptr ||q==nullptr ){ return false ; }else if ( p->val!=q->val){ return false ; }else { return isSameTree (p->left,q->left)&&isSameTree (p->right,q->right); } } };
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 : TreeNode* invertTree (TreeNode* root) { exchangeNode (root); return root; } void exchangeNode (TreeNode* node) if (node==NULL )return ; TreeNode* temp = node->left; node->left = node->right; node->right = temp; exchangeNode (node->left); exchangeNode (node->right); } };
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 class Solution {public : bool check (TreeNode* node1, TreeNode* node2) if (!node1 && !node2){ return true ; } if (!node1 || !node2){ return false ; } if (node1->val != node2->val){ return false ; } return check (node1->left,node2->right)&&check (node1->right,node2->left); } bool isSymmetric (TreeNode* root) return check (root->left,root->right); } };
这个和下一题都记住各自的原则，先序的第一个对应根节点，后序的第一个对应根节点，然后都要维护各自list的边界范围（左右子树）
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 class Solution { unordered_map<int , int > index; public : TreeNode* recurisve_buildTree (vector<int >& preorder, vector<int >& inorder,int leftp,int rightp,int leftin,int rightin) { if (leftp>rightp){ return nullptr ; } int inorder_index = index[preorder[leftp]]; TreeNode *root = new TreeNode (preorder[leftp]); int left_nodes_num = inorder_index-leftin; root->left = recurisve_buildTree (preorder,inorder,leftp+1 ,leftp+left_nodes_num,leftin,inorder_index-1 ); root->right = recurisve_buildTree (preorder,inorder,leftp+left_nodes_num+1 ,rightp,inorder_index+1 ,rightin); return root; } TreeNode* buildTree (vector<int >& preorder, vector<int >& inorder) { int n = preorder.size (); for (int i=0 ;i<n;i++){ index[inorder[i]]=i; } return recurisve_buildTree (preorder,inorder,0 ,n-1 ,0 ,n-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 class Solution { unordered_map<int ,int >mapping; public : TreeNode* recursive_build_tree (vector<int >& inorder, vector<int >& postorder,int post_left,int post_right,int in_left,int in_right) { if (post_left>post_right){ return nullptr ; } int in_index= mapping[postorder[post_right]]; int num_right_nodes = in_right-in_index; int num_left_nodes = in_index-in_left; TreeNode *root = new TreeNode (postorder[post_right]); root->left= recursive_build_tree (inorder,postorder,post_left,post_right-num_right_nodes-1 ,in_left,in_index-1 ); root->right = recursive_build_tree (inorder,postorder,post_right-num_right_nodes,post_right-1 ,in_index+1 ,in_right); return root; } TreeNode* buildTree (vector<int >& inorder, vector<int >& postorder) { int n = inorder.size (); for (int i=0 ;i<n;i++){ mapping[inorder[i]]=i; } return recursive_build_tree (inorder,postorder,0 ,n-1 ,0 ,n-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 class Solution {public : Node* connect (Node* root) { if (!root){ return root; } map<int ,vector<Node*>>mapping; vector<Node*>start={root}; mapping[0 ]=start; for (auto [k,nodes]:mapping){ for (auto node: nodes){ if (node->left){ if (!mapping.count (k+1 )){ vector<Node*>temp; temp.push_back (node->left); mapping[k+1 ]=temp; }else { mapping[k+1 ].push_back (node->left); } } if (node->right){ if (!mapping.count (k+1 )){ vector<Node*>temp; temp.push_back (node->right); mapping[k+1 ]=temp; }else { mapping[k+1 ].push_back (node->right); } } } } for (auto [k,v]:mapping){ if (v.size ()>1 ){ for (int i=0 ;i<v.size ()-1 ;i++){ v[i]->next=v[i+1 ]; } } } return root; } };
更简单的解法：
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 class Solution {public : Node* connect (Node* root) { if (!root) { return nullptr ; } queue<Node*> q; q.push (root); while (!q.empty ()) { int n = q.size (); Node *last = nullptr ; for (int i = 1 ; i <= n; ++i) { Node *f = q.front (); q.pop (); if (f->left) { q.push (f->left); } if (f->right) { q.push (f->right); } if (i != 1 ) { last->next = f; } last = f; } } return root; } };
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 class Solution { vector<TreeNode*>nodes; public : void flatten (TreeNode* root) if (root==nullptr ){ return ; } pre (root); int size = nodes.size (); for (int i=0 ;i<size-1 ;i++){ nodes[i]->left=nullptr ; nodes[i]->right=nodes[i+1 ]; } nodes[size-1 ]->left=nullptr ; nodes[size-1 ]->right=nullptr ; } void pre (TreeNode* root) if (!root){ return ; } nodes.push_back (root); pre (root->left); pre (root->right); } };
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 { bool flag= false ; public : bool hasPathSum (TreeNode* root, int targetSum) getSum (root,0 ,targetSum); return flag; } void getSum (TreeNode* node,int sum,int targetSum) if (!node){ return ; } sum=sum+node->val; if (node->left==nullptr && node->right==nullptr && sum==targetSum){ flag=true ; } getSum (node->left,sum,targetSum); getSum (node->right,sum,targetSum); } };
依旧注意stoi用法
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 { int sum=0 ; public : int sumNumbers (TreeNode* root) string cur="" ; getSum (root,cur); return sum; } void getSum (TreeNode* node,string cur) if (!node){ return ; } cur +=to_string (node->val); if (node->left==nullptr && node->right==nullptr ){ sum+=stoi (cur); } getSum (node->left,cur); getSum (node->right,cur); } };
我嘞个最大贡献值
其实这个最大贡献值就看成从这个节点往下走能够sum到的最大值就行了
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 { int max_num = -INT_MAX; public : int maxGain (TreeNode*node) if (node==nullptr ){ return 0 ; } int max_left = max (maxGain (node->left),0 ); int max_right = max (maxGain (node->right),0 ); max_num = max (max_num,node->val+max_left+max_right); return node->val+max (max_left,max_right); } int maxPathSum (TreeNode* root) maxGain (root); return max_num; } };
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 class BSTIterator { vector<TreeNode*>nodes; int index =0 ; int size=-1 ; public : BSTIterator (TreeNode* root) { inorder (root); this ->size=nodes.size (); } void inorder (TreeNode *node) if (node==nullptr ){ return ; } inorder (node->left); nodes.push_back (node); inorder (node->right); } int next () int ans = nodes[this ->index]->val; this ->index++; return ans; } bool hasNext () if (index<size){ return true ; } return false ; } };
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 { int num=0 ; public : int countNodes (TreeNode* root) pre (root); return num; } void pre (TreeNode* node) if (node==nullptr ){ return ; } num++; pre (node->left); pre (node->right); } };
这是递归
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; } };
还有一种就是记录父节点的，设置一个visited模块，从下往上找就行
12.23
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 Solution {public : vector<int > rightSideView (TreeNode* root) { map<int ,vector<TreeNode*>>mapping; vector<int >ans; if (!root){ return ans; } vector<TreeNode*>start={root}; mapping[0 ]=start; for (auto [k,vs]:mapping){ for (auto v:vs){ if (v->left){ if (!mapping.count (k+1 )){ vector<TreeNode*>temp={v->left}; mapping[k+1 ]=temp; }else { mapping[k+1 ].push_back (v->left); } } if (v->right){ if (!mapping.count (k+1 )){ vector<TreeNode*>temp={v->right}; mapping[k+1 ]=temp; }else { mapping[k+1 ].push_back (v->right); } } } } for (auto [k,v]:mapping){ ans.push_back (v[v.size ()-1 ]->val); } 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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 class Solution {public : vector<double > averageOfLevels (TreeNode* root) { vector<double >ans; if (!root){ return ans; } map<int ,vector<TreeNode*>>mapping; vector<TreeNode*>start={root}; mapping[0 ]=start; for (auto [k,vs]:mapping){ for (auto v:vs){ if (v->left){ if (!mapping.count (k+1 )){ vector<TreeNode*>temp={v->left}; mapping[k+1 ]=temp; }else { mapping[k+1 ].push_back (v->left); } } if (v->right){ if (!mapping.count (k+1 )){ vector<TreeNode*>temp={v->right}; mapping[k+1 ]=temp; }else { mapping[k+1 ].push_back (v->right); } } } } for (auto [k,v]:mapping){ double temp_num = get_avg (v); ans.push_back (temp_num); } return ans; } double get_avg (vector<TreeNode*>nodes) double sum=0.0 ; for (auto node:nodes){ sum+=double (node->val); } return double (sum/nodes.size ()); } };
下面的才是最简单的做法：
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<double > averageOfLevels (TreeNode* root) { auto counts = vector <int >(); auto sums = vector <double >(); dfs (root, 0 , counts, sums); auto averages = vector <double >(); int size = sums.size (); for (int i = 0 ; i < size; i++) { averages.push_back (sums[i] / counts[i]); } return averages; } void dfs (TreeNode* root, int level, vector<int > &counts, vector<double > &sums) if (root == nullptr ) { return ; } if (level < sums.size ()) { sums[level] += root->val; counts[level] += 1 ; } else { sums.push_back (1.0 * root->val); counts.push_back (1 ); } dfs (root->left, level + 1 , counts, sums); dfs (root->right, level + 1 , counts, sums); } };
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 {public : vector<vector<int >> levelOrder (TreeNode* root) { vector<vector<int >>ans; if (!root){ return ans; } map<int ,vector<TreeNode*>>mapping; vector<TreeNode*>start={root}; mapping[0 ]=start; for (auto [k,vs]:mapping){ for (auto v:vs){ if (v->left){ if (!mapping.count (k+1 )){ vector<TreeNode*>temp={v->left}; mapping[k+1 ]=temp; }else { mapping[k+1 ].push_back (v->left); } } if (v->right){ if (!mapping.count (k+1 )){ vector<TreeNode*>temp={v->right}; mapping[k+1 ]=temp; }else { mapping[k+1 ].push_back (v->right); } } } } for (auto [k,vs]: mapping){ vector<int >temp; for (auto v:vs){ temp.push_back (v->val); } ans.push_back (temp); } 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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 class Solution {public : vector<vector<int >> zigzagLevelOrder (TreeNode* root) { vector<vector<int >>ans; if (root==nullptr ){ return ans; } int flag=0 ; map<int ,vector<TreeNode*>>mapping; vector<TreeNode*>start={root}; mapping[0 ]=start; for (auto [k,vs]:mapping){ for (auto v:vs){ if (v->left){ if (!mapping.count (k+1 )){ vector<TreeNode*>temp={v->left}; mapping[k+1 ]=temp; }else { mapping[k+1 ].push_back (v->left); } } if (v->right){ if (!mapping.count (k+1 )){ vector<TreeNode*>temp={v->right}; mapping[k+1 ]=temp; }else { mapping[k+1 ].push_back (v->right); } } } } for (auto [k,vs]: mapping){ vector<int >temp; if (flag==1 ){ reverse (vs.begin (),vs.end ()); flag=0 ; }else { flag=1 ; } for (auto v:vs){ temp.push_back (v->val); } ans.push_back (temp); } return ans; } };
12.24
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 { vector<int >nums; public : int getMinimumDifference (TreeNode* root) getNums (root); int ans = INT_MAX; for (int i=0 ;i<nums.size ()-1 ;i++){ int temp = abs (nums[i],nums[i+1 ]); ans = min (temp,ans); } return ans; } int min (int a, int b) return a>b?b:a; } int abs (int a, int b) int res = a-b; if (res>0 ){ return res; } return -res; } void getNums (TreeNode* node) if (node==nullptr ){ return ; } getNums (node->left); nums.push_back (node->val); getNums (node->right); } };
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 { vector<int >nums; public : int kthSmallest (TreeNode* root, int k) getNums (root); return nums[k-1 ]; } void getNums (TreeNode* node) if (node==nullptr ){ return ; } getNums (node->left); nums.push_back (node->val); getNums (node->right); } };
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 class Solution { vector<int >nums; public : bool isValidBST (TreeNode* root) getNums (root); if (nums.size ()==1 ){ return true ; } for (int i=0 ;i<nums.size ()-1 ;i++){ if (nums[i]>=nums[i+1 ]){ return false ; } } return true ; } void getNums (TreeNode* node) if (node==nullptr ){ return ; } getNums (node->left); nums.push_back (node->val); getNums (node->right); } };
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 numIslands (vector<vector<char >>& grid) int m = grid.size (); int n = grid[0 ].size (); bool visited[m][n]; memset (visited,false ,sizeof (visited)); int ans =0 ; for (int i=0 ;i<m;i++){ for (int j=0 ;j<n;j++){ if (grid[i][j]=='1' ){ ans++; dfs (grid,i,j,m,n); } } } return ans; } void dfs (vector<vector<char >>& grid,int i ,int j,int m,int n) grid[i][j]='0' ; if (i-1 >=0 &&grid[i-1 ][j]=='1' )dfs (grid,i-1 ,j,m,n); if (i+1 <m&&grid[i+1 ][j]=='1' )dfs (grid,i+1 ,j,m,n); if (j-1 >=0 &&grid[i][j-1 ]=='1' )dfs (grid,i,j-1 ,m,n); if (j+1 <n&&grid[i][j+1 ]=='1' )dfs (grid,i,j+1 ,m,n); } };
还有点小巧思，先dfs周围的
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 : void solve (vector<vector<char >>& board) int m = board.size (); int n = board[0 ].size (); for (int i=0 ;i<m;i++){ dfs (board,i,0 ); dfs (board,i,n-1 ); } for (int i=1 ;i<n-1 ;i++){ dfs (board,0 ,i); dfs (board,m-1 ,i); } for (int i=0 ;i<m;i++){ for (int j=0 ;j<n;j++){ if (board[i][j]=='O' ){ board[i][j]='X' ; }else if (board[i][j]=='C' ){ board[i][j]='O' ; } } } return ; } void dfs (vector<vector<char >>& board,int i,int j) int m=board.size (); int n =board[0 ].size (); if (i<0 ||j<0 ||i>=m||j>=n||board[i][j]!='O' ){ return ; } board[i][j]='C' ; dfs (board,i+1 ,j); dfs (board,i-1 ,j); dfs (board,i,j-1 ); dfs (board,i,j+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 class Solution { map<Node*,Node*>mapping; public : Node* cloneGraph (Node* node) { if (node==nullptr ){ return nullptr ; } Node* start= new Node (node->val); mapping[node]=start; queue<Node*>q; q.push (node); while (!q.empty ()){ Node* temp = q.front (); q.pop (); for (auto n: temp->neighbors){ if (!mapping.count (n)){ Node* neighbor_node = new Node (n->val); mapping[n]=neighbor_node; q.push (n); } mapping[temp]->neighbors.push_back (mapping[n]); } } return mapping[node]; } };
这里掌握两种解法，一种是并查集，一种是直接bfs
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 66 67 68 69 70 class Solution {public : vector<double > calcEquation (vector<vector<string>>& equations, vector<double >& values, vector<vector<string>>& queries) { unordered_map<string, unordered_map<string, double >> graph; for (int i = 0 ; i < equations.size (); i++) { string a = equations[i][0 ]; string b = equations[i][1 ]; double val = values[i]; graph[a][b] = val; graph[b][a] = 1.0 / val; } vector<double > ans; for (auto query : queries) { string start = query[0 ]; string end = query[1 ]; if (!graph.count (start) || !graph.count (end)) { ans.push_back (double (-1.0 )); continue ; } if (start == end) { ans.push_back (1.0 ); continue ; } bool found = false ; unordered_set<string> visited; queue<pair<string, double >> q; q.push ({ start, 1.0 }); visited.insert (start); while (!q.empty () && !found) { auto curQ = q.front (); q.pop (); string curNode = curQ.first; double sum = curQ.second; for (auto neighbor : graph[curNode]) { string nextNode = neighbor.first; double nextVal = neighbor.second; if (nextNode == end) { ans.push_back (sum * nextVal); found = true ; break ; } if (!visited.count (nextNode)) { visited.insert (nextNode); q.push ({ nextNode, sum * nextVal }); } } } if (!found)ans.push_back (-1.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 26 27 28 #include <iostream> #include <vector> using namespace std;int main () int n,m; while (cin>>n>>m){ int t = n; vector<int > v (n+1 ,-1 ) ; while (m--){ int x,y; cin>>x>>y; int a=x,b=y; while (v[a]!=-1 ) a=v[a]; while (v[b]!=-1 ) b=v[b]; if (a==b) continue ; else { v[b]=x; t-=1 ; } } v.clear (); cout<<t-1 <<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 39 40 41 42 class Solution {public : bool canFinish (int numCourses, vector<vector<int >>& prerequisites) vector<int >indgree (numCourses,0 ); map<int ,vector<int >>mapping; for (auto v:prerequisites){ int start=v[1 ]; int end=v[0 ]; if (!mapping.count (start)){ vector<int >temp; temp.push_back (end); mapping[start]=temp; }else { mapping[start].push_back (end); } indgree[end]++; } queue<int >q; for (int i=0 ;i<numCourses;i++){ if (indgree[i]==0 ){ q.push (i); } } while (!q.empty ()){ int course = q.front (); q.pop (); for (auto end:mapping[course]){ indgree[end]--; if (indgree[end]==0 ){ q.push (end); } } } for (int i=0 ;i<numCourses;i++){ if (indgree[i]>0 ){ return false ; } } return true ; } };
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 class Solution {public : vector<int > findOrder (int numCourses, vector<vector<int >>& prerequisites) { vector<int >indgree (numCourses,0 ); map<int ,vector<int >>mapping; vector<int >ans; for (auto v:prerequisites){ int start=v[1 ]; int end=v[0 ]; if (!mapping.count (start)){ vector<int >temp; temp.push_back (end); mapping[start]=temp; }else { mapping[start].push_back (end); } indgree[end]++; } queue<int >q; for (int i=0 ;i<numCourses;i++){ if (indgree[i]==0 ){ q.push (i); ans.push_back (i); } } while (!q.empty ()){ int course = q.front (); q.pop (); for (auto end:mapping[course]){ indgree[end]--; if (indgree[end]==0 ){ q.push (end); ans.push_back (end); } } } for (int i=0 ;i<numCourses;i++){ if (indgree[i]>0 ){ vector<int >nothing; return nothing; } } return ans; } };
12.25
其实不难，就是题意描述得有点恶心
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 { pair<int , int > id2rc (int id, int n) { int r = (id - 1 ) / n, c = (id - 1 ) % n; if (r % 2 == 1 ) { c = n - 1 - c; } return {n - 1 - r, c}; } public : int snakesAndLadders (vector<vector<int >> &board) int n = board.size (); vector<int > vis (n * n + 1 ) ; queue<pair<int , int >> q; q.emplace (1 , 0 ); while (!q.empty ()) { auto p = q.front (); q.pop (); for (int i = 1 ; i <= 6 ; ++i) { int nxt = p.first + i; if (nxt > n * n) { break ; } auto rc = id2rc (nxt, n); if (board[rc.first][rc.second] > 0 ) { nxt = board[rc.first][rc.second]; } if (nxt == n * n) { return p.second + 1 ; } if (!vis[nxt]) { vis[nxt] = true ; q.emplace (nxt, p.second + 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 43 44 45 class Solution {public : int minMutation (string start, string end, vector<string>& bank) unordered_set<string> cnt; unordered_set<string> visited; char keys[4 ] = {'A' , 'C' , 'G' , 'T' }; for (auto & w : bank) { cnt.emplace (w); } if (start == end) { return 0 ; } if (!cnt.count (end)) { return -1 ; } queue<string> qu; qu.emplace (start); visited.emplace (start); int step = 1 ; while (!qu.empty ()) { int sz = qu.size (); for (int i = 0 ; i < sz; i++) { string curr = qu.front (); qu.pop (); for (int j = 0 ; j < 8 ; j++) { for (int k = 0 ; k < 4 ; k++) { if (keys[k] != curr[j]) { string next = curr; next[j] = keys[k]; if (!visited.count (next) && cnt.count (next)) { if (next == end) { return step; } qu.emplace (next); visited.emplace (next); } } } } } step++; } 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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 class Solution {public : unordered_map<string, int > wordId; vector<vector<int >> edge; int nodeNum = 0 ; void addWord (string& word) if (!wordId.count (word)) { wordId[word] = nodeNum++; edge.emplace_back (); } } void addEdge (string& word) addWord (word); int id1 = wordId[word]; for (char & it : word) { char tmp = it; it = '*' ; addWord (word); int id2 = wordId[word]; edge[id1].push_back (id2); edge[id2].push_back (id1); it = tmp; } } int ladderLength (string beginWord, string endWord, vector<string>& wordList) for (string& word : wordList) { addEdge (word); } addEdge (beginWord); if (!wordId.count (endWord)) { return 0 ; } vector<int > dis (nodeNum, INT_MAX) ; int beginId = wordId[beginWord], endId = wordId[endWord]; dis[beginId] = 0 ; queue<int > que; que.push (beginId); while (!que.empty ()) { int x = que.front (); que.pop (); if (x == endId) { return dis[endId] / 2 + 1 ; } for (int & it : edge[x]) { if (dis[it] == INT_MAX) { dis[it] = dis[x] + 1 ; que.push (it); } } } 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 class Trie { vector<Trie*>children; bool isEnd; Trie* searchPrefix (string prefix) { Trie* node =this ; for (char ch: prefix){ ch-='a' ; if (node->children[ch]!=nullptr ){ node=node->children[ch]; }else { return nullptr ; } } return node; } public : Trie (){ this ->children= vector <Trie*>(26 ,nullptr ); this ->isEnd=false ; } void insert (string word) Trie* node = this ; for (char ch:word){ ch -='a' ; if (node->children[ch]==nullptr ){ node->children[ch]=new Trie (); } node = node->children[ch]; } node->isEnd=true ; } bool search (string word) Trie* node = searchPrefix (word); return node!=nullptr &&node->isEnd; } bool startsWith (string prefix) Trie* node = searchPrefix (prefix); return node!=nullptr ; } };
这个也还可以，前缀树+dfs
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 class WordDictionary { private Trie root; public WordDictionary () root = new Trie (); } public void addWord (String word) root.insert (word); } public boolean search (String word) return dfs (word, 0 , root); } private boolean dfs (String word, int index, Trie node) if (index == word.length ()) { return node.isEnd (); } char ch = word.charAt (index); if (Character.isLetter (ch)) { int childIndex = ch - 'a' ; Trie child = node.getChildren ()[childIndex]; if (child != null && dfs (word, index + 1 , child)) { return true ; } } else { for (int i = 0 ; i < 26 ; i++) { Trie child = node.getChildren ()[i]; if (child != null && dfs (word, index + 1 , child)) { return true ; } } } return false ; } } class Trie { private Trie[] children; private boolean isEnd; public Trie () children = new Trie[26 ]; isEnd = false ; } public void insert (String word) Trie node = this ; for (int i = 0 ; i < word.length (); i++) { char ch = word.charAt (i); int index = ch - 'a' ; if (node.children[index] == null) { node.children[index] = new Trie (); } node = node.children[index]; } node.isEnd = true ; } public Trie[] getChildren () { return children; } public boolean isEnd () return isEnd; } }
12.27
可以，代码手撕很简单，就是想思路挺难
前缀树+
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 struct Trie { string word; map<char ,Trie*>children; Trie (){ this ->word="" ; } }; void insertWord (Trie* root,string word) Trie* node = root; for (char c: word){ if (!node->children.count (c)){ node->children[c]= new Trie (); } node=node->children[c]; } node->word=word; } class Solution { vector<vector<int >>steps={ {1 ,0 }, {-1 ,0 }, {0 ,-1 }, {0 ,1 } }; public : void dfs (Trie* root,vector<vector<char >>& board,int i,int j,set<string>&res) Trie*node =root; char c = board[i][j]; if (!node->children.count (board[i][j])){ return ; } node=node->children[board[i][j]]; if (node->word.size ()>0 ){ res.insert (node->word); } board[i][j]='#' ; int m =board.size (); int n = board[0 ].size (); for (int k=0 ;k<4 ;k++){ int nextX=i+steps[k][0 ]; int nextY=j+steps[k][1 ]; if (nextX>=0 &&nextY>=0 &&nextX<m&&nextY<n&&board[nextX][nextY]!='#' ){ dfs (node,board,nextX,nextY,res); } } board[i][j]=c; return ; } vector<string> findWords (vector<vector<char >>& board, vector<string>& words) { Trie* root = new Trie (); for (auto word:words){ insertWord (root,word); } int m =board.size (); int n = board[0 ].size (); set<string>res; vector<string>ans; for (int i=0 ;i<m;i++){ for (int j=0 ;j<n;j++){ dfs (root,board,i,j,res); } } for (auto word:res){ ans.emplace_back (word); } 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 class Solution { map<char ,vector<string>>mapping; public : void dfs (string temp,string digits,int i,vector<string>&res) string start = temp; if (i>=digits.size ()){ return ; } for (auto v:mapping[digits[i]]){ temp+=v; if (i==digits.size ()-1 ){ res.push_back (temp); } dfs (temp,digits,i+1 ,res); temp=temp.substr (0 ,temp.size ()-1 ); } return ; } vector<string> letterCombinations (string digits) { mapping['2' ]={"a" ,"b" ,"c" }; mapping['3' ]={"d" ,"e" ,"f" }; mapping['4' ]={"g" ,"h" ,"i" }; mapping['5' ]={"j" ,"k" ,"l" }; mapping['6' ]={"m" ,"n" ,"o" }; mapping['7' ]={"p" ,"q" ,"r" ,"s" }; mapping['8' ]={"t" ,"u" ,"v" }; mapping['9' ]={"w" ,"x" ,"y" ,"z" }; vector<string>ans; string temp="" ; dfs ("" ,digits,0 ,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 class Solution {public : void dfs (int n,int i,vector<int >cur, int k,vector<vector<int >>&ans) if (cur.size ()==k){ ans.push_back (cur); return ; } if (i>n||cur.size () + (n - i + 1 ) < k){ return ; } cur.push_back (i); dfs (n,i+1 ,cur,k,ans); cur.pop_back (); dfs (n,i+1 ,cur,k,ans); return ; } vector<vector<int >> combine (int n, int k) { vector<vector<int >>ans; vector<int >start; dfs (n,1 ,start,k,ans); return ans; } };
其实会往底层去想，这个为什么就是全排列了
我们定义递归函数 backtrack(first,output) 表示从左往右填到第 first 个位置，当前排列为 output。 那么整个递归函数分为两个情况：
如果 first=n，说明我们已经填完了 n 个位置（注意下标从 0 开始），找到了一个可行的解，我们将 output 放入答案数组中，递归结束。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { vector<vector<int >>ans; public : void backtrack (vector<int >temp,int start) if (start==temp.size ()){ ans.emplace_back (temp); return ; } for (int i=start;i<temp.size ();i++){ swap (temp[i],temp[start]); backtrack (temp,start+1 ); swap (temp[i],temp[start]); } } vector<vector<int >> permute (vector<int >& nums) { backtrack (nums,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 26 27 28 29 30 31 32 33 34 35 class Solution { vector<vector<int >>ans; public : int sum (vector<int >nums) int res = 0 ; for (int num:nums){ res+=num; } return res; } void backtrack (int target,int i,vector<int >& candidates,vector<int >&temp) if (i>=candidates.size ())return ; if (sum (temp)==target){ ans.push_back (temp); return ; } if (sum (temp)>target){ return ; } backtrack (target,i+1 ,candidates,temp); if (target-sum (temp)-candidates[i]>=0 ){ temp.push_back (candidates[i]); backtrack (target,i,candidates,temp); temp.pop_back (); } } vector<vector<int >> combinationSum (vector<int >& candidates, int target) { sort (candidates.begin (),candidates.end ()); vector<int >temp; backtrack (target,0 ,candidates,temp); return ans; } };
12.28
按照三种set进行区分就行
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 {public : vector<vector<string>> solveNQueens (int n) { vector<vector<string>>ans; unordered_set<int >columns; unordered_set<int >t_pie; unordered_set<int >t_na; vector<int >queens=vector <int >(n,-1 ); backtrack (0 ,ans,columns,t_pie,t_na,queens,n); return ans; } void backtrack (int row,vector<vector<string>>&ans,unordered_set<int >&columns,unordered_set<int >&t_pie,unordered_set<int >&t_na,vector<int >&queens,int n) if (row==n){ vector<string>temp = print_board (queens,n); ans.push_back (temp); }else { for (int i=0 ;i<n;i++){ int index1=i; if (columns.count (index1)){ continue ; } int index2 = row-i; if (t_na.count (index2)){ continue ; } int index3 = row+i; if (t_pie.count (index3)){ continue ; } queens[row]=i; columns.insert (index1); t_na.insert (index2); t_pie.insert (index3); backtrack (row+1 ,ans,columns,t_pie,t_na,queens,n); columns.erase (index1); t_na.erase (index2); t_pie.erase (index3); } } } vector<string>print_board (vector<int >&queens,int n){ vector<string>res; for (int i=0 ;i<n;i++){ string temp=string (n,'.' ); temp[queens[i]]='Q' ; res.push_back (temp); } return res; } };
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 class Solution {public : int totalNQueens (int n) auto ans=solveNQueens (n); return ans.size (); } vector<vector<string>> solveNQueens (int n) { vector<vector<string>>ans; unordered_set<int >columns; unordered_set<int >t_pie; unordered_set<int >t_na; vector<int >queens=vector <int >(n,-1 ); backtrack (0 ,ans,columns,t_pie,t_na,queens,n); return ans; } void backtrack (int row,vector<vector<string>>&ans,unordered_set<int >&columns,unordered_set<int >&t_pie,unordered_set<int >&t_na,vector<int >&queens,int n) if (row==n){ vector<string>temp = print_board (queens,n); ans.push_back (temp); }else { for (int i=0 ;i<n;i++){ int index1=i; if (columns.count (index1)){ continue ; } int index2 = row-i; if (t_na.count (index2)){ continue ; } int index3 = row+i; if (t_pie.count (index3)){ continue ; } queens[row]=i; columns.insert (index1); t_na.insert (index2); t_pie.insert (index3); backtrack (row+1 ,ans,columns,t_pie,t_na,queens,n); columns.erase (index1); t_na.erase (index2); t_pie.erase (index3); } } } vector<string>print_board (vector<int >&queens,int n){ vector<string>res; for (int i=0 ;i<n;i++){ string temp=string (n,'.' ); temp[queens[i]]='Q' ; res.push_back (temp); } return res; } };
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 : vector<string> generateParenthesis (int n) { vector<string>ans; string temp="" ; backtrack (ans,temp,0 ,n,0 ,0 ); return ans; } void backtrack (vector<string>&ans,string &temp,int i,int n,int left_num,int right_num) if (i==2 *n){ ans.push_back (temp); } if (left_num<n&&left_num>=right_num){ temp+="(" ; backtrack (ans,temp,i+1 ,n,left_num+1 ,right_num); temp=temp.substr (0 ,temp.size ()-1 ); } if (left_num>right_num){ temp+=")" ; backtrack (ans,temp,i+1 ,n,left_num,right_num+1 ); temp=temp.substr (0 ,temp.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 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 struct Trie { string word; map<char ,Trie*>children; Trie (){ this ->word="" ; } }; void insert_word (Trie* root,string word) for (auto ch :word){ if (!root->children.count (ch)){ root->children[ch]=new Trie (); } root=root->children[ch]; } root->word = word; } class Solution { bool flag =false ; vector<vector<int >>steps={ {1 ,0 }, {-1 ,0 }, {0 ,1 }, {0 ,-1 } }; public : bool exist (vector<vector<char >>& board, string word) Trie* root = new Trie (); insert_word (root,word); int m = board.size (); int n = board[0 ].size (); for (int i=0 ;i<m;i++){ for (int j=0 ;j<n;j++){ dfs (board,word,0 ,root,i,j); if (flag){ return flag; } } } return flag; } void dfs (vector<vector<char >>& board,string word,int index,Trie* node,int i,int j) if (!node->children.count (board[i][j]))return ; char ch = board[i][j]; node=node->children[board[i][j]]; if (node->word==word){ flag=true ; return ; } for (int k=0 ;k<4 ;k++){ int nextX = i+steps[k][0 ]; int nextY = j+steps[k][1 ]; board[i][j]='#' ; if (nextX>=0 &&nextY>=0 &&nextX<board.size ()&&nextY<board[0 ].size ()&&board[nextX][nextY]!='#' ){ dfs (board,word,index+1 ,node,nextX,nextY); } board[i][j]=ch; } } };
注意这里是平衡二叉搜索树
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 TreeNode* insert_node (vector<int >nums,int left,int right) { if (left>right){ return nullptr ; } int mid = (left+right)/2 ; int num = nums[mid]; TreeNode * root = new TreeNode (num); root->left = insert_node (nums,left,mid-1 ); root->right = insert_node (nums,mid+1 ,right); return root; } class Solution {public : TreeNode* sortedArrayToBST (vector<int >& nums) { int size = nums.size (); TreeNode* root = insert_node (nums,0 ,size-1 ); return root; } };
唯一需要注意的是这里的sort的用法
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 : ListNode* sortList (ListNode* head) { vector<ListNode*>nodes; if (head == nullptr || head->next == nullptr ) { return head; } ListNode* temp = head; while (temp!=nullptr ){ nodes.push_back (temp); temp=temp->next; } sort (nodes.begin (),nodes.end (),[](ListNode*a ,ListNode*b){ return a->val<b->val; }); for (int i=0 ;i<nodes.size ()-1 ;i++){ nodes[i]->next=nodes[i+1 ]; } nodes.back ()->next = nullptr ; return nodes[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 class Solution { public ListNode sortList (ListNode head) return sortList (head, null); } public ListNode sortList (ListNode head, ListNode tail) if (head == null) { return head; } if (head.next == tail) { head.next = null; return head; } ListNode slow = head, fast = head; while (fast != tail) { slow = slow.next; fast = fast.next; if (fast != tail) { fast = fast.next; } } ListNode mid = slow; ListNode list1 = sortList (head, mid); ListNode list2 = sortList (mid, tail); ListNode sorted = merge (list1, list2); return sorted; } public ListNode merge (ListNode head1, ListNode head2) ListNode dummyHead = new ListNode (0 ); ListNode temp = dummyHead, temp1 = head1, temp2 = head2; while (temp1 != null && temp2 != null) { if (temp1. val <= temp2. val) { temp.next = temp1; temp1 = temp1. next; } else { temp.next = temp2; temp2 = temp2. next; } temp = temp.next; } if (temp1 != null) { temp.next = temp1; } else if (temp2 != null) { temp.next = temp2; } return dummyHead.next; } }
最大难度在于读懂题目
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 Node* dfs (vector<vector<int >>& grid,int r0,int c0,int r1,int c1) { for (int i=r0;i<r1;i++){ for (int j=c0;j<c1;j++){ if (grid[i][j]!=grid[r0][c0]){ return new Node ( true ,false , dfs (grid,r0, c0, (r0 + r1) / 2 , (c0 + c1) / 2 ), dfs (grid,r0, (c0 + c1) / 2 , (r0 + r1) / 2 , c1), dfs (grid,(r0 + r1) / 2 , c0, r1, (c0 + c1) / 2 ), dfs (grid,(r0 + r1) / 2 , (c0 + c1) / 2 , r1, c1) ); } } } return new Node (grid[r0][c0],true ); } class Solution {public : Node* construct (vector<vector<int >>& grid) { return dfs (grid,0 ,0 ,grid.size (),grid.size ()); } };
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 class Solution {public : ListNode* mergeKLists (vector<ListNode*>& lists) { if (lists.size ()==0 ){ return nullptr ; } int flag =0 ; for (int i=0 ;i<lists.size ();i++){ if (lists[i]!=nullptr ){ flag++; } } if (flag==0 ){ return nullptr ; } vector<ListNode*>nodes; for (auto n:lists){ auto head = n; while (head){ nodes.push_back (head); head=head->next; } } sort (nodes.begin (),nodes.end (),[](ListNode* node_a,ListNode* node_b){ return node_a->val<node_b->val; }); for (int i=0 ;i<nodes.size ();i++){ if (i+1 <nodes.size ()){ nodes[i]->next=nodes[i+1 ]; } } nodes[nodes.size ()-1 ]->next=nullptr ; return nodes[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 class Solution {public : ListNode* merge_2_lists (ListNode* a,ListNode* b) { ListNode* head = new ListNode (-1 ); ListNode* tail = head; ListNode* ptra = a; ListNode* ptrb = b; while (ptra&&ptrb){ if (ptra->val<ptrb->val){ tail->next = ptra; ptra=ptra->next; }else { tail->next = ptrb; ptrb=ptrb->next; } tail=tail->next; } if (ptra!=nullptr ){ tail->next=ptra; } if (ptrb!=nullptr ){ tail->next=ptrb; } return head->next; } ListNode* merge_all (vector<ListNode*>& lists,int left,int right) { if (left>right){ return nullptr ; } if (left==right){ return lists[left]; } int mid=(left+right)/2 ; return merge_2_lists (merge_all (lists,left,mid),merge_all (lists,mid+1 ,right)); } ListNode* mergeKLists (vector<ListNode*>& lists) { return merge_all (lists,0 ,lists.size ()-1 ); } };
1 2 3 4 5 6 7 8 9 10 11 12 class Solution {public : int maxSubArray (vector<int >& nums) int pre = 0 , maxAns = nums[0 ]; for (const auto &x: nums) { pre = max (pre + x, x); maxAns = max (maxAns, pre); } return maxAns; } };
01.01
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : int maxSubarraySumCircular (vector<int >& nums) int curMax = 0 ; int maxSum = nums[0 ]; int curMin = 0 ; int minSum = nums[0 ]; int total =0 ; for (auto num : nums){ curMax = max (curMax+num,num); maxSum = max (curMax,maxSum); curMin = min (num,curMin+num); minSum = min (curMin,minSum); total += num; } if (maxSum<0 )return maxSum; return max (maxSum,total-minSum); } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution {public : int searchInsert (vector<int >& nums, int target) int left = 0 ; int right = nums.size () - 1 ; while (left <= right) { int mid = left + (right - left) / 2 ; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1 ; } else { right = mid - 1 ; } } return left; } };
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 : bool searchMatrix (vector<vector<int >>& matrix, int target) for (int i=0 ;i<matrix.size ();i++){ if (target>matrix[i][matrix[0 ].size ()-1 ])continue ; return searchVector (matrix[i],target); } return false ; } bool searchVector (vector<int >nums,int target) int left =0 ; int right = nums.size ()-1 ; while (left<=right){ int mid = left+(right-left)/2 ; if (nums[mid]==target){ return true ; } if (nums[mid]>target){ right = mid-1 ; }else { left = mid+1 ; } } return false ; } };
阴的没边了，这玩意儿靠一个证明，即上升趋势，进行一个爬坡
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : int findPeakElement (vector<int >& nums) int left = 0 ; int right = nums.size ()-1 ; while (left<right){ int mid = left+(right-left)/2 ; if (nums[mid]>nums[mid+1 ]){ right = mid; }else { left=mid+1 ; } } return left; } };
搜索旋转排序数组:star:
这个也挺阴的
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 class Solution {public : int search (vector<int >& nums, int target) int l =0 ; int r = nums.size ()-1 ; int n = nums.size (); if (n==0 )return -1 ; while (l<=r){ int mid = l + (r-l)/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 ; } };
01.02
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 binary_search (vector<int >&nums,int target,bool lower) int left =0 ; int right = nums.size ()-1 ; int ans = nums.size (); while (left<=right){ int mid = left + (right-left)/2 ; if (nums[mid]>target||(lower&&nums[mid]>=target)){ right = mid-1 ; ans = mid; }else { left = mid +1 ; } } return ans; } vector<int > searchRange (vector<int >& nums, int target) { int left = binary_search (nums,target,true ); int right = binary_search (nums,target,false )-1 ; if (left<=right&&right<nums.size ()&&nums[right]==target&&nums[left]==target){ return {left,right}; } return {-1 ,-1 }; } };
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 left =0 ; int right = nums.size ()-1 ; while (left<right){ int mid = left +(right-left)/2 ; if (nums[mid]<nums[right]){ right = mid; }else { left = mid+1 ; } } return nums[left]; } };
这里得注意边界条件，left < right
巨恶心
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 class Solution { public double findMedianSortedArrays (int [] nums1, int [] nums2) int length1 = nums1.l ength, length2 = nums2.l ength; int totalLength = length1 + length2; if (totalLength % 2 == 1 ) { int midIndex = totalLength / 2 ; double median = getKthElement (nums1, nums2, midIndex + 1 ); return median; } else { int midIndex1 = totalLength / 2 - 1 , midIndex2 = totalLength / 2 ; double median = (getKthElement (nums1, nums2, midIndex1 + 1 ) + getKthElement (nums1, nums2, midIndex2 + 1 )) / 2.0 ; return median; } } public int getKthElement (int [] nums1, int [] nums2, int k) int length1 = nums1.l ength, length2 = nums2.l ength; int index1 = 0 , index2 = 0 ; int kthElement = 0 ; while (true ) { if (index1 == length1) { return nums2[index2 + k - 1 ]; } if (index2 == length2) { return nums1[index1 + k - 1 ]; } if (k == 1 ) { return Math.min (nums1[index1], nums2[index2]); } int half = k / 2 ; int newIndex1 = Math.min (index1 + half, length1) - 1 ; int newIndex2 = Math.min (index2 + half, length2) - 1 ; int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2]; if (pivot1 <= pivot2) { k -= (newIndex1 - index1 + 1 ); index1 = newIndex1 + 1 ; } else { k -= (newIndex2 - index2 + 1 ); index2 = newIndex2 + 1 ; } } } }
01.11
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int findKthLargest (vector<int >& nums, int k) priority_queue<int >q; for (auto num : nums){ q.push (num); } for (int i=0 ;i<k-1 ;i++){ q.pop (); } return q.top (); } };
就稍微还好吧，记住大小顶堆以及pair sort的用法
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 typedef pair<int ,int > pii;class Solution {public : int findMaximizedCapital (int k, int w, vector<int >& profits, vector<int >& capital) int n = profits.size (); int curr = 0 ; priority_queue<int , vector<int >, less<int >> pq; vector<pii> arr; for (int i = 0 ; i < n; ++i) { arr.push_back ({capital[i], profits[i]}); } sort (arr.begin (), arr.end ()); for (int i = 0 ; i < k; ++i) { while (curr < n && arr[curr].first <= w) { pq.push (arr[curr].second); curr++; } if (!pq.empty ()) { w += pq.top (); pq.pop (); } else { break ; } } return w; } };
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 struct Pair_num { int val1; int val2; int i; int j; int sum; Pair_num (int v1, int v2, int idx1, int idx2): val1 (v1), val2 (v2), i (idx1), j (idx2), sum (v1 + v2) {} Pair_num (int s): sum (s) {} bool operator >(const Pair_num& other) const { return sum > other.sum; } }; class Solution {public : vector<vector<int >> kSmallestPairs (vector<int >& nums1, vector<int >& nums2, int k) { int m = nums1. size (); int n = nums2. size (); vector<vector<int >> ans; if (m == 0 || n == 0 ) return ans; auto cmp = [](const Pair_num& a, const Pair_num& b) { return a.sum > b.sum; }; priority_queue<Pair_num, vector<Pair_num>, decltype (cmp)> pq (cmp); for (int i = 0 ; i < min (k, m); i++) { pq.emplace (nums1[i], nums2[0 ], i, 0 ); } while (k-- > 0 && !pq.empty ()) { Pair_num curr = pq.top (); pq.pop (); ans.push_back ({curr.val1, curr.val2}); if (curr.j + 1 < n) { int next_j = curr.j + 1 ; pq.emplace (nums1[curr.i], nums2[next_j], curr.i, next_j); } } 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 #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; } };
