头文件
万能头文件
1
2
| #include <bits/stdc++.h>
using namespace std;
|
完整头文件
1
2
3
4
5
6
7
8
9
10
11
12
| #include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
using namespace std;
|
I/O
保留三位小数
1
2
3
4
5
6
7
8
| while(cin >> n >> s >> m) {
cout << "n = " << n << ", s = " << s << ", m = " << m << endl;
cin.clear();
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}
|
简单模拟
- DreamJudge 1133 求 1 到 n 的和
- DreamJudge 1043 计算 Sn
- DreamJudge 1040 利润提成
- DreamJudge 1722 身份证校验
链表类问题
- 猴子报数
- 21. 合并两个有序链表 - 力扣（LeetCode）
- 剑指 Offer 24. 反转链表 - 力扣（LeetCode）
链表定义、输入、输出模板
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
|
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* inputList() {
int n;
std::cin >> n;
ListNode* head = nullptr;
ListNode* tail = nullptr;
for (int i = 0; i < n; ++i) {
int x;
std::cin >> x;
ListNode* node = new ListNode(x);
if (tail == nullptr) {
head = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
}
return head;
}
void outputList(ListNode* head) {
while (head != nullptr) {
std::cout << head->val << " ";
head = head->next;
}
std::cout << std::endl;
}
|
回溯算法
回溯三部曲
在回溯算法中，我的习惯是函数起名字为backtracking，这个起名大家随意。
回溯算法中函数返回值一般为void。
再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
但后面的回溯题目的讲解中，为了方便大家理解，我在一开始就帮大家把参数确定下来。
回溯函数伪代码如下：
既然是树形结构，那么我们在讲解二叉树的递归的时候，就知道遍历树形结构一定要有终止条件。
所以回溯也有要终止条件。
什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。
所以回溯函数终止条件伪代码如下：
1
2
3
4
| if (终止条件) {
存放结果;
return;
}
|
在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
如图：
注意图中，我特意举例集合大小和孩子的数量是相等的！
回溯函数遍历过程伪代码如下：
1
2
3
4
5
| for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
|
for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
分析完过程，回溯算法模板框架如下：
1
2
3
4
5
6
7
8
9
10
11
12
| void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
|
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
| void BFS(Node root,int target)
{
queue<Node> q;
unordered_set<Node> visited;
q.push(root);
visted(root);
int step;
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; ++i) {
Node cur = q.top();
q.pop();
if (cur == target) {
return step;
}
for (Node &e : Graph[root]) {
if(visited.find(e) != visited.end()) {
q.push(e);
visited.insert(e);
}
}
}
step++;
}
}
|
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
| #include<iostream>
#include<cmath>
using namespace std;
int p[10]={0};
bool vis[10]={0};
int n;
void dfs(int x)
{
if (x==n+1)
{
for(int i=1;i<=n;i++)
cout<<p[i]<<" ";
cout<<endl;
return ;
}
for (int i=1;i<=n;i++)
{
if (vis[i]==false && i>p[x])
{
p[x] = i;
vis[i] = true;
dfs(x+1);
vis[i] = false;
}
}
}
int main()
{
n=4;
dfs(1);
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
|
int n, G[MAXV][MAXV];
bool vis[MAXV] = { false };
void dfs(int u, int depth){
vis[u] = true;
for (int v = 0; v < n; v++){
if (vis[v] == false && G[u][v] != INF){
dfs(v, depth + 1);
}
}
}
void dfsTrave(){
for (int u = 0; u < n; u++){
if (vis[u] == false){
dfs(u, 1);
}
}
}
void dfs(int x){
if(判断终止条件){
根据题目条件处理
return;
}
if(判断是否不可能状态){
减枝
return;
}
if(判断是否越界){
return;
}
for(搜索相邻节点){
if(没有访问过){
根据题目条件处理
v[i]=1;
dfs(x+1);
v[i]=0;
}
}
return;
}
|
回溯
用于解决组合、切割、子集、排列（强调元素的顺序）、棋盘等问题。
回溯法都可以抽象为树形结构，一般抽象为n叉树，数的宽度为处理的问题的大小，用for来处理；深度就是递归的深度，使用递归处理。
模板
1
2
3
4
5
6
7
8
9
10
11
12
| void backtracking(参数){
if(终止条件){
收集结果;
return;
}
for(集合的元素集){
处理节点;
递归函数;
回溯操作;
}
}
|
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
| class Solution {
private:
vector<vector<string>> result;
vector<string> path;
void backtracking (const string& s, int startIndex) {
if (startIndex >= s.size()) {
result.push_back(path);
return;
}
for (int i = startIndex; i < s.size(); i++) {
if (isPalindrome(s, startIndex, i)) {
string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
} else {
continue;
}
backtracking(s, i + 1);
path.pop_back();
}
}
bool isPalindrome(const string& s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
public:
vector<vector<string>> partition(string s) {
result.clear();
path.clear();
backtracking(s, 0);
return result;
}
};
|
