CPP树

$$\theta=5$$

description和keywords都是给爬虫看的

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

//插入，访问，查找，删除
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 只允许存储唯一的元素，列表去重

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直接传参，减少内存开销，避免完整拷贝，占用额外空间。

二分查找

无敌公式

int searchInsert(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
    while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
        int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
        if (nums[middle] > target) {
            right = middle - 1; // target 在左区间，所以[left, middle - 1]
        } else if (nums[middle] < target) {
            left = middle + 1; // target 在右区间，所以[middle + 1, right]
        } else { // nums[middle] == target
            return middle; // 数组中找到目标值，直接返回下标
        }
    }
    // 未找到目标值
    return left;
    
}

(right - left) >>1相当于(right - left) / 2

left是插入位置，注意在多维搜索的时候要在索引不为0的情况下取前一行

注意越界检查，移动查重的时候可以左边先移动再右边先移动

while(a>=0&&a<nums.size()&&nums[a]==target||b>=0&&b<nums.size()&&nums[b]==target)
{
    if(a>=0&&a<nums.size()&&nums[a]==target)
    {
        a--;
    }
    if(b>=0&&b<nums.size()&&nums[b]==target)
    {
        b++;
    }
}

改成
// 专门向左找边界
while(a >= 0 && nums[a] == target) {
    a--;
}
// 专门向右找边界
while(b < nums.size() && nums[b] == target) {
    b++;
}

result[0] = a + 1;
result[1] = b - 1;
return result;

其余情况

注意等号的位置和情况的分类

class Solution {
public:
    int search(vector<int>& nums, int target) {
        //折叠二分查找
        int left = 0;
        int right = nums.size()-1;

        while(left<=right)
        {
            int mid = (left+right)/2;
            if(nums[mid]==target)return mid;
            if(nums[0]>nums[mid])
            {
                if(target>nums[mid]&&target<=nums[nums.size()-1])
                {
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }else{
                if(target>=nums[0]&&target<nums[mid])
                {
                    right = mid-1;
                }else{
                    left = mid+1;
                }
            }
        }
        return -1;
    }
};

非对称更新

int findMin(vector<int>& nums) {
    int left =0;
    int right=nums.size()-1;
    if(nums[left]<nums[right])return nums[left];
    while(left<right)
    {
        int mid = (left+right)/2;
        if(nums[left]<=nums[mid]&&nums[right]>=nums[mid])break;
        if(nums[mid]>=nums[left])
        {
            left = mid+1;
        }else{
            right =mid;
        }
    }
    return min(nums[left],nums[right]);
}

栈和队列

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

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

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

deque 是双端队列

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

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

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也可以直接＋；

//字符串配套使用
string result;

result+=st.top();

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

switch不支持string判别

哈希表转vector

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

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

std::sort(
    sortedPairs.begin(),   // 起始迭代器
    sortedPairs.end(),     // 结束迭代器
    [](const auto& a, const auto& b) {  // Lambda 比较函数
        return a.second < b.second;     // 按 pair 的 second（Value）升序
    }
);

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是有序的默认升序，都是按照键来排序

传参直接用{，}

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

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

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

判断multimap是否有重复

if (mmap.count(1) > 1)

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

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

//哈希表转数组
  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是右子

二叉树的节点定义

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

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int a):val(a),left(NULL),right(NULL){}//构造函数
}

//使用
TreeNode* newtree = new TreeNode(1);

二叉树真勾八抽象呀，老子今天下午一定给你啃下来

递归遍历

//默写
//前序遍历
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);  //处理阶段
}

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

//前序遍历  从上到下
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.有不为空，先左后右
    //都遍历完了，再把中间节点塞入
}

二叉树的迭代遍历

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

//默写
//前序遍历
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;
}

//前序遍历
//因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
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
}

迭代统一遍历

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

中序遍历

空指针标记法：

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标记法

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;
    
}

前序遍历

空指针标记法：

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标记法

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;
    
}

后序遍历

空指针标记法：

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标记法

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;
    
}

层序遍历

广度优先遍历/层序遍历（迭代法和递归法）（正向）

//先看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一下就行)

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;
    }

对称二叉树的判断

递归

层序遍历

队列

栈

二叉树的高度与深度

后续遍历 从下到上求高度

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);
    }
};

前序遍历 从上到下求深度

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;
    }
};

迭代法 层序遍历

代过

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

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

map排序

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

map先转化成数组

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); // 给频率排个序

二叉搜索树

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

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

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

找到了就一路返回

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

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

回溯

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

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

五大类问题

组合 切割 子集 排列 棋盘

组合问题

回溯三部曲

回溯模板

void backtracking(参数) {
    if (终止条件) {   //终止条件是搜寻终止，但是收获开始
        存放结果;
        return;
    }

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

组合问题剪枝

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

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

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

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

输出细节

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

private中不需要传参也可以用

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

backtracking(candidates, target, i + 1);  // 不允许重复选择

//日常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视频

棋盘问题

N皇后 字符串初始化

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

数独

二维递归

贪心算法

动态规划

图论

默写

二叉树递归遍历：

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);
}

二叉树的统一迭代遍历：

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;
}

二叉树的迭代层序遍历：

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;
}