description和keywords都是给爬虫看的

写轮眼

map myMap键值对，键唯一，按照键的大小自动排序

1
2
3
4
5
6
7
8
9
10
11
12
13
//插入，访问，查找，删除
myMap.insert(make_pair(1, 100)) #make_pair打包键值对
myMap[2] = 200;
myMap.insert({{3, 300}, {4, 400}}); 

auto it = myMap.find(3);
if (it != myMap.end()) {
    a= it->first;
    b= it->second ;
} else {
}

myMap.erase(1);

str.size()获取列表长度

string定义字符串

unordered_map：适合对元素顺序没有要求，且需要快速访问的场景，尤其是在元素数量较多且频繁进行查找、插入和删除操作时。

.push_back（），在vector后面添加元素

vector> ans 多维数组

unordered_set 只允许存储唯一的元素，列表去重

1
2
3
4
for(int&num:nums){
    //C++新型for循环
    st.count(num-1)//查询元素是否存在
}

哈希表：

数组,哈希范围可控，数值较小的情况

,set数值很大

,map键值对

三种set

uordered_set自动去重

​

KMP算法

那么什么是前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

所以字符串a的最长相等前后缀为0。 字符串aa的最长相等前后缀为1。 字符串aaa的最长相等前后缀为2。 等等…..。

const string&str来代替string str直接传参，减少内存开销，避免完整拷贝，占用额外空间。

栈和队列

栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。

所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构

deque 是双端队列

1
std::stack<int, std::vector<int> > third;  // 使用vector为底层容器的栈

队列中先进先出的数据结构，同样不允许有遍历行为，不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。

1
std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列

队列的底层容器不能用vector

vector的pop_front()是O(n)（需要移动所有元素），而deque和list的pop_front()是O(1)

栈操作

stackst

函数 功能 返回类型 时间复杂度
push(const T& val) 元素入栈 void O(1)
pop() 移除栈顶元素 void O(1)
top() 返回栈顶元素（不删除） T&（可修改）或 const T&（只读） O(1)
empty() 判断栈是否为空 bool（true 为空） O(1)
size() 返回栈中元素数量 size_t（无符号整数） O(1)

队列操作

queue que

操作 函数 返回类型 注意事项
入队 push() / emplace() void emplace 更高效
出队 pop() void 需先调用 front()
访问队首 front() T& 或 const T& 可修改或只读
访问队尾 back() T& 或 const T& 可修改或只读
判空 empty() bool true 表示空
大小 size() size_t 元素数量

字符串拼接可以用pushback也可以直接＋；

1
2
3
4
5
6
//字符串配套使用
string result;

result+=st.top();

reverse(result.begin(),result.end());//反转字符串

switch不支持string判别

哈希表转vector

vector> sortedPairs(hashMap.begin(), hashMap.end());

sort按照容器自定义排序 []中是引用外部变量，也是三种传参方式

1
2
3
4
5
6
7
std::sort(
    sortedPairs.begin(),   // 起始迭代器
    sortedPairs.end(),     // 结束迭代器
    [](const auto& a, const auto& b) {  // Lambda 比较函数
        return a.second < b.second;     // 按 pair 的 second（Value）升序
    }
);
1
2
3
4
5
6
7
8
9
std::sort(nums.begin(), nums.end(), [threshold](int a, int b) {
       bool a_gt = (a > threshold);
       bool b_gt = (b > threshold);
       if (a_gt != b_gt) {
           return a_gt > b_gt; // 先排大于阈值的数
       } else {
           return a < b;       // 同组内升序
       }
   });

multimap只能用.insert传参，因为可以包含重复键值对，但是multimap是有序的默认升序，都是按照键来排序

传参直接用{，}

1
2
3
4
std::multimap<int, std::string> sortedMap;
for (const auto& pair : hashMap) {   //遍历哈希表的方法
    sortedMap.insert({pair.second, pair.first});
}

multimap实现降值排序,map同样适用

1
2
3
4
5
6
7
// 使用 std::greater<int> 实现降序
    std::multimap<int, std::string, std::greater<int>> mmap = {
        {3, "Banana"},
        {1, "Apple"},
        {2, "Avocado"},
        {1, "Apricot"}
    };

判断multimap是否有重复

1
if (mmap.count(1) > 1)

哈希表转数组，注意数组变量的前后要用->来引用，

注意从后向前遍历，可以用rbegin()和rend()

1
2
3
4
5
6
7
//哈希表转数组
  vector<pair<int, int>> sortedPairs(sortmap.begin(), sortmap.end());
  vector<int>result;
  for(auto it =sortedPairs.rbegin();it<sortedPairs.rbegin()+k;it++)
 {
   result.push_back(it->second);
 }

快速排序

通过一趟排序将待排数据分割成独立的两部分，其中一部分的所有元素均比另一部分小，然后递归地对这两部分继续排序，最终完成整个序列的排序

快速排序 O(n log n) 不稳定 O(log n) 通用、数据量大
归并排序 O(n log n) 稳定 O(n) 需要稳定排序或外部排序

大顶堆和小顶堆

优先级队列

其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

比较规则的作用

返回值决定顺序

return a.first > b.first的布尔结果会告诉priority_queue

如果为 true：a 应该排在 b 的后面（即 a 的优先级更低）。

如果为 false：a 应该排在 b 的前面或保持原顺序（即 a 的优先级更高或相等）。

优先级队列的操作

操作 正确性 说明
pri_que.push(it) ❌ 错误 类型不匹配，且可能引发悬空指针。
pri_que.push(*it) ✅ 可用 隐式转换 pair<const int, int> 为 pair<int, int>。
pri_que.push({it->first, it->second}) ✅ 推荐 显式构造 pair<int, int>，明确类型转换，避免潜在问题。

auto it = map.begin()

it的类型是std::unordered_map::iterator

特性 迭代器 (std::unordered_map::iterator) 指针 (T*)
本质 类对象（可能包含复杂逻辑） 内存地址的数值
解引用 *it 返回 std::pair<const int, int>& 返回指向的对象
成员访问 it-> 访问键值对的成员（如 it->first） 访问结构体/类的成员
失效风险 容器修改（如插入/删除）可能导致迭代器失效 仅当内存释放后失效
算术运算 不支持 it + 1（无序容器） 支持指针算术（如 ptr + 1）

关于用->second访问还是用.second来访问

，如果是引用，则用->，是成员的话用.

双端队列常用函数deque

函数 作用 时间复杂度
front() 返回首元素引用 O(1)
back() 返回尾元素引用 O(1)
operator[] 通过下标访问元素（无边界检查） O(1)
at(index) 通过下标访问元素（有边界检查） O(1)
push_front(val) 头部插入元素 O(1)
push_back(val) 尾部插入元素 O(1)
pop_front() 删除头部元素 O(1)
pop_back() 删除尾部元素 O(1)
insert(pos, val) 在指定位置插入元素 O(n)
erase(pos) 删除指定位置元素 O(n)
size() 返回当前元素数量
empty() 判断是否为空
resize(n) 调整容器大小
clear() 清空所有元素

二叉树

堆是一个完全二叉树

二叉树的存储方式：

链式存储：指针

顺序存储：数组

数组：2i+1是左子，2i+2是右子

二叉树的节点定义

1
2
//默写代码 (链表构造)

1
2
3
4
5
6
7
8
9
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int a):val(a),left(NULL),right(NULL){}//构造函数
}

//使用
TreeNode* newtree = new TreeNode(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
//默写
//前序遍历
void traversal(TreeNode * cur,vector<int>& vec){
    if(cur==NULL)return;
    vec.push_back(cur->val);   //处理阶段
    traversal(cur->left,vec);
    traversal(cur->right,vec);
}
//中序遍历
void traversal(TreeNode * cur,vector<int>& vec){
    if(cur==NULL)return;
    traversal(cur->left,vec);
    vec.push_back(cur->val);    //处理阶段
    traversal(cur->right,vec);
}
    
//后续遍历
void traversal(TreeNode * cur,vector<int>& vec){
    if(cur==NULL)return;
    traversal(cur->left,vec);
    traversal(cur->right,vec);
    vec.push_back(cur->val);  //处理阶段
}



二叉树递归遍历（三种顺序：中左右，左中右，左右中）

image-20250824224906680

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//前序遍历  从上到下
void traversal(TreeNode* cur,vector<int>& vec)   //输入输出
{
    if (cur == NULL) return;
    vec.push_back(cur->val);    // 中   处理节点
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
}
//中序遍历  从下到上
void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    vec.push_back(cur->val);    // 中    处理节点
    traversal(cur->right, vec); // 右
}
//后序遍历  从下到上  
void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
    vec.push_back(cur->val);    // 中    处理节点  相当于左右节点都遍历完之后再处理中间节点，1.都为空，把当前节点塞进去，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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//默写
//前序遍历
vector<int> pretraversal(TreeNode* root){
    stack<TreeNode*>st;
    vector<int>result;
    TreeNode* cur = root;
    st.push(root)
    while(!st.empty())
    {
		cur = st.top();
        st.pop();
        result.push_back(cur->val)
        if(cur->right!=NULL)st.push(cur->right);
        if(cur->left!=NULL)st.push(cur->left);
    }
    return result
}
//中序遍历
vector<int> midtraversal(TreeNode* root){
    stack<TreeNode*>st;
    vector<int>result;
    TreeNode* cur = root;
    //不用了，不然重复了st.push(root)
    
    //先传入后处理
    
    while(!st.empty()||cur!=NULL)
    {
        if(cur!=NULL)
        {
            st.push(cur);
            cur = cur->left;
        }else{
            cur = st.top();   //
            result.push_back(cur->val);  //处理 中
            st.pop();  
            cur=cur->right;
        }
    }
    return result;
}

//后续遍历
vector<int> pastraversal(TreeNode* root){
    stack<TreeNode*>st;
    vector<int>result;
    TreeNode* cur = root;
    st.push(root)
    while(!st.empty())
    {
		cur = st.top();
        st.pop();
        result.push_back(cur->val)
        if(cur->left!=NULL)st.push(cur->left);
        if(cur->right!=NULL)st.push(cur->right);
        
    }
    reverse(result.begin(),result.end());
    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
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
//前序遍历
//因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
vector<int> preordertraversal(TreeNode* root){
    vector<int>result;

    if(cur==NULL)return;
    stack<TreeNode*>st;
    st.push(cur);
    while(!st.empty())
    {
        TreeNode* cur = st.top();                       // 中
        st.pop();
        result.push_back(cur->val);   //处理中间节点
        if(cur->right!=NULL)st.push(cur->right);
        if(cur->left!=NULL)st.push(cur->left);      
    }
    return result
}

//中序遍历
vector<int> inordertraversal(TreeNode* root){
    vector<int>result;
   	TreeNode* cur = root;
    if(cur==NULL)return;
    stack<TreeNode*>st;
   
    while(!st.empty()||cur!=NULL)
    {
        if(cur!=NULL)
        {
            st.push(cur);
            cur = cur->left;
        }else{
            cur = st.top();
            st.pop();
            result.push_back(cur->val);//处理部分
            cur = cur->right;   
        }
    }
}

//后序遍历
vector<int> postordertraversal(TreeNode* root){
    vector<int>result;
   	TreeNode* cur = root;
    if(cur==NULL)return;
    stack<TreeNode*>st;
    st.push(cur);
    while(!st.empty())
    {
        cur = st.pop();
        result.push_back(cur->val);   //处理中间节点
        if(cur->left!=NULL)st.push(cur->left);    
        if(cur->right!=NULL)st.push(cur->right);      
    }
    reverse(result.begin(), result.end());  //巧妙处理
    return result
}






迭代统一遍历

无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况
两种标记法
空指针标记法

image-20250825173145457

中序遍历

空指针标记法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> midtraversal(TreeNode* root){
    vector<int>result;
    TreeNode* cur= root;
    stack<TreeNode*>st;
    if (root != NULL) st.push(root);
    while(!st.empty())
    {
        cur = st.top();
        st.pop();
        if(cur!=NULL)
        {
         	if(cur->right)st.push(cur->right);
            st.push(cur);
            st.push(NULL);
            
            if(cur->left)st.push(cur->left);                    
        }else{
            cur = st.top();
            result.push_back(cur->val);
            st.pop();
        }
    }
    return result;
}

boolean标记法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> midtraversal(TreeNode* root){
    vector<int>result;
    stack<pair<TreeNode*,bool>>st;
    if(root!=nullptr)st.push(make_pair(root,false));
    while(!st.empty())
    {
        auto curnode = st.top().first;
        auto visited = st.top().second;
        st.pop();
        if(visited)
        {
            result.push_back(curnode->val);
            continue;
        }
        
        //初次访问
        if(curnode->right)st.push(make_pair(curnode->right,false));
        st.push(make_pair(curnodet,true));
        if(curnode->left)st.push(make_pair(curnode->left,false));
        }
    }
	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
vector<int> pretraversal(TreeNode* root){
    vector<int>result;
    TreeNode* cur= root;
    stack<TreeNode*>st;
    if (root != NULL) st.push(root);
    while(!st.empty())
    {
        cur = st.top();
        if(cur!=NULL)
        {
         	st.pop();
            if(cur->right)st.push(cur->right);
            if(cur->left)st.push(cur->left);  
            st.push(cur);
            st.push(NULL);
            
                              
        }else{
            st.pop();
            cur = st.top();
            result.push_back(cur->val);
            st.pop();
        }
    }
    return result;
}

boolean标记法

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
vector<int> pretraversal(TreeNode* root){
    vector<int>result;
    stack<pair<TreeNode*,bool>>st;
    if(root!=nullptr)st.push(make_pair(root,false));
    while(!st.empty())
    {
        auto curnode = st.top().first;
        auto visited = st.top().second;
        st.pop();
        if(visited)
        {
            result.push_back(curnode->val);
            continue;
        }
        
        //初次访问
        if(curnode->right)st.push(make_pair(curnode->right,false));
        if(curnode->left)st.push(make_pair(curnode->left,false));
        st.push(make_pair(curnodet,true));
        
        }
    }
	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
vector<int> pastraversal(TreeNode* root){
    vector<int>result;
    TreeNode* cur= root;
    stack<TreeNode*>st;
    if (root != NULL) st.push(root);
    while(!st.empty())
    {
        cur = st.top();
        if(cur!=NULL)
        {
         	st.pop();
            st.push(cur);
            st.push(NULL);
            if(cur->right)st.push(cur->right);
            if(cur->left)st.push(cur->left);  
        }else{
            st.pop();
            cur = st.top();
            result.push_back(cur->val);
            st.pop();
        }
    }
    return result;
}

boolean标记法

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
vector<int> pastraversal(TreeNode* root){
    vector<int>result;
    stack<pair<TreeNode*,bool>>st;
    if(root!=nullptr)st.push(make_pair(root,false));
    while(!st.empty())
    {
        auto curnode = st.top().first;
        auto visited = st.top().second;
        st.pop();
        if(visited)
        {
            result.push_back(curnode->val);
            continue;
        }
        
        //初次访问
        st.push(make_pair(curnodet,true));
        if(curnode->right)st.push(make_pair(curnode->right,false));
        if(curnode->left)st.push(make_pair(curnode->left,false));
        
        
        }
    }
	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
//先看sb递归法   //这个有点像是深度优先了，因为先从上到最左下，再回去
void order(TreeNode* cur, vector<vector<int>>& result, int depth)
    {
        if (cur == nullptr) return;
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }

//迭代法-------------------注意记住队列就行
vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {  //一个while一层，
            int size = que.size();  //因为要把当前层遍历完
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();  //取出来
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }

反向层序遍历（迭代法）(正向遍历reverse一下就行)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {  //一个while一层，
            int size = que.size();  //因为要把当前层遍历完
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();  //取出来
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
    	reverse(result.begin(),result.end());
        return result;
    }

对称二叉树的判断

递归

层序遍历

队列

1

栈

二叉树的高度与深度

后续遍历 从下到上求高度

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int getdepth(TreeNode* node) {
        if (node == NULL) return 0;
        int leftdepth = getdepth(node->left);       // 左
        int rightdepth = getdepth(node->right);     // 右
        int depth = 1 + max(leftdepth, rightdepth); // 中
        return depth;
    }
    int maxDepth(TreeNode* root) {
        return getdepth(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
class Solution {
public:
    int result;
    void getdepth(TreeNode* node, int depth) {
        result = depth > result ? depth : result; // 中

        if (node->left == NULL && node->right == NULL) return ;

        if (node->left) { // 左
            depth++;    // 深度+1
            getdepth(node->left, depth);
            depth--;    // 回溯，深度-1
        }
        if (node->right) { // 右
            depth++;    // 深度+1
            getdepth(node->right, depth);
            depth--;    // 回溯，深度-1
        }
        return ;
    }
    int maxDepth(TreeNode* root) {
        result = 0;
        if (root == NULL) return result;
        getdepth(root, 1);
        return result;
    }
};

迭代法 层序遍历

1
代过

隐藏回溯：if (cur->left) traversal(cur->left, path + “->”, result); // 左 回溯就隐藏在这里

那么在如上代码中，貌似没有看到回溯的逻辑，其实不然，回溯就隐藏在traversal(cur->left, path + "->", result);中的 path + "->"。 每次函数调用完，path依然是没有加上”->” 的，这就是回溯了。

map排序

sort cmp给的是前两个（或者相邻两个（从前往后））应满足的关系

map先转化成数组

1
2
3
4
5
6
bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {
    return a.second > b.second; // 按照频率从大到小排序
}

vector<pair<int, int>> vec(map.begin(), map.end());
sort(vec.begin(), vec.end(), cmp); // 给频率排个序

二叉搜索树

找众数，即出现最多次，可以用

1
2
3
4
5
6
//当等于的时候加入结果集
if (count > maxCount) { // 如果计数大于最大值
    maxCount = count;   // 更新最大频率
    result.clear();     // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
    result.push_back(cur->val);
}

遍历一条边和搜索整个数的区别？

找到了就一路返回

二叉搜索树是从上到下找公共祖先

二叉搜索树可以尝试用迭代法，因为只有一条路径，不需要回溯

回溯

横纵方向，横向集合大小for循环处理，纵向递归处理树的深度

image-20250401221921171

在递归的过程中增加闸门 backtracking

五大类问题

组合 切割 子集 排列 棋盘

组合问题

回溯三部曲

回溯模板

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {   //终止条件是搜寻终止，但是收获开始
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归     -----上面那个结果是哪里来的
        回溯，撤销处理结果
    }
}

组合问题剪枝

1
n-(k-path.size())+1来代替n;可以用n=4,k=3来举例子，当.size()=0的时候，只需要遍历1，234都被剪掉了   这里用<=要方便一些

由于无法控制嵌套的for循环层数，所以要用回溯算法。回溯算法抽象成一个n叉树

组合问题（取k个数控制树的深度），for循环的范围是集合宽度

组合剪枝，条件剪枝和组合个数剪枝

输出细节

1
[""]不合法，需要转化成[]，可以用.clear()

private中不需要传参也可以用

1
2
3
backtracking(candidates, target, i);  // 允许重复选择当前数字

backtracking(candidates, target, i + 1);  // 不允许重复选择
1
2
3
4
5
6
7
8
9
10
11
12
13
//日常bug:
//将字符串去重复
//字符串数组中找到某个字符串
find(result.begin(), result.end(), path) != result.end()
//显式初始化数组
vector<int> digits = {}
//vector刚创建出来的时候是unfind的，
set转数组
unordered_set<int> set = {5, 2, 8, 1}
vector<int> vec(set.begin(), set.end());
set添加元素
unordered_set<int, int> people;
people.emplace(1);

分割问题

可以把判断放在单层搜索逻辑中

字符串操作：’’是char “”是string

在某点插入某个符号 s.insert(s.begin() + i + 1 , ‘.’);

字符串删除：注意

s.erase(s.begin() + i + 1); 这里s.begin()是迭代器，所以删除的是那一位置的元素

s.erase(1); 这里删除的是第一个索引包括之后的所有元素

子集问题

直接加进去就行

排列问题

采用used数组，used数组用来去重或者排列

最主要的是去重

数层去重和树枝去重：组合总和2视频

image-20250405235349182

棋盘问题

N皇后 字符串初始化

1
2
3
//vector<string> board = { "....", "....", "....", "...." }; 
int n = 4;  // 棋盘大小
vector<string> board(n, string(n, '.'));  // ✅ 创建 n×n 的棋盘，初始为 "...."

数独

二维递归

贪心算法

动态规划

默写

二叉树递归遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void pretraversal(TreeNode* cur,vector<int>&vec){
    if(cur==NULL)return;
    vec.push_back(cur->val);
    pretraversal(cur->left,vec);
    pretraversal(cur->right,vec);
}
void midtraversal(TreeNode* cur,vector<int>&vec){
    if(cur==NULL)return;
    pretraversal(cur->left,vec);
    vec.push_back(cur->val);
    pretraversal(cur->right,vec);
}
void pastraversal(TreeNode* cur,vector<int>&vec){
    if(cur==NULL)return;
    pretraversal(cur->left,vec);
    pretraversal(cur->right,vec);
    vec.push_back(cur->val);
}

二叉树的统一迭代遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int>itertraversal(TreeNode* root){
    vector<int>result;
    stack<pair<TreeNode*,bool>>st;
    if(root!=nullptr)st.push(make_pair(root,false));
    
    while(!st.empty())
    {
        
        auto curnode = st.top().first;
        auto visited = st.top().second;
        st.pop();
        if(visited){
            //访问过
            result.push_back(curnode->val);  //或者这里用 if continue也可以
        }else{
            //初次访问
            if(curnode->right)st.push((make_pair(curnode->right,false));
            if(curnode->left)st.push((make_pair(curnode->left,false));
            st.push(make_pair(curnode,true));
        }
    }
    return result;
}

二叉树的迭代层序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>>leveltraversal((TreeNode* root){
    vector<vector<int>>result;
    queue<int>que;
    if(root!=nullptr)que.push(root)
    while(!que.empty())
    {
        vector<int>vec;
        int len = que.size();
        for(int i = 0;i<len;i++)
        {
            TreeNode* cur = que.front();
            que.pop();
            vec.push_back(cur->val);
            if(cur->left)que.push(cur->left);
            if(cur->right)que.push(cur->right);
        }
        result.push_back(vec);
    }
    return result;
}