1 Leetcodegaogaotwo       1.1 链表          1.1.1 分割链表          1.1.2 反转链表          1.1.3 快慢指针 链表的中间节点          1.1.4 链表的倒数第k个节点          1.1.5 回文链表          1.1.6 链表的删除          1.1.7 链表反转2          1.1.8 链表的第一个相交节点       1.2 dfs          1.2.1 岛屿数量          1.2.2 机器人的运动范围          1.2.3 字符串的全排列(回溯算法)          1.2.4 判断一个数字是否可以表示成三的幂的和          1.2.5 不同路径III dfs+回溯          1.2.6 组合总和 dfs+回溯          1.2.7 子集 dfs or 状态枚举       1.3 bfs       1.4 双指针          1.4.1 奇数在前，偶数在后       1.5 二维矩阵的前缀和          1.5.1 1074. 元素和为目标值的子矩阵数量          1.5.2 304. 二维区域和检索 - 矩阵不可变       1.6 数组变化          1.6.1 大数加减法          1.6.2 717. 1 比特与 2 比特字符       1.7 排序算法          1.7.1 把数组排成最小的数          1.7.2 根据字符出现的次数频率进行排序          1.7.3 最大数          1.7.4 969. 煎饼排序       1.8 dp动态规划          1.8.1 斐波那契数列          1.8.2 俄罗斯套娃信封问题          1.8.3 分割回文串          1.8.4 01背包          1.8.5 打家劫舍II          1.8.6 青蛙过河          1.8.7 最长回文子串          1.8.8 目标和 （01背包）          1.8.9 最大子序和       1.9 滑动窗口          1.9.1 绝对差不超过限制的最长连续子数组          1.9.2 三数之和       1.10 二叉树性质          1.10.1 二叉树的最小深度          1.10.2 二叉树的层次遍历          1.10.3 二叉树的镜像翻转          1.10.4 二叉树的最大深度          1.10.5 二叉搜索树节点最小距离          1.10.6 二叉树重构从小到达 按照->right情况          1.10.7 二叉搜索数的范围和          1.10.8 N叉树的前序遍历       1.11 递归          1.11.1 1+2...+n       1.12 并查集          1.12.1 并查集连通分量          1.12.2 并查集城市连通       1.13 堆栈          1.13.1 通过队列来实现栈          1.13.2 下一个更大元素 II          1.13.3 删除字符串中的所有相邻重复项          1.13.4 基本计算机          1.13.5 计算机          1.13.6 逆波兰表达式          1.13.7 接雨水          1.13.8 柱状图中最大矩形面积          1.13.9 反转每对括号间的子串       1.14 队列（or 优先队列）          1.14.1 最大平均通过率          1.14.2 最大的团队表现值          1.14.3 找出第K大的异或坐标值          1.14.4 1.2滑动窗口的最大值          1.14.5 二叉搜索数的范围和          1.14.6 员工的重要性       1.15 Hash查询匹配          1.15.1 猜灯谜          1.15.2 720. 词典中最长的单词       1.16 前缀树          1.16.1 实现Trie(前缀树)          1.16.2 添加与搜索单词 - 数据结构设计       1.17 位运算          1.17.1 比特位计数          1.17.2 不用加减乘除做加法          1.17.3 可被 5 整除的二进制前缀          1.17.4 汉明距离总和       1.18 二分法          1.18.1 在D天内送达包裹的能力          1.18.2 第一个错误的版本       1.19 数据结构性质       1.20 回溯法思想       1.21 字符串处理(模拟)          1.21.1 Excel 表列序号进制转换          1.21.2 838.推多米诺       1.22 模拟       1.23 数学定理          1.23.1 1828. 统计一个圆中点的数目

双向队列 deque<>q; q.empty() 判断队列是否为空 q.front() 返回队头属性 q.back() 返回队尾属性 q.pop_front() 弹出队头元素 q.pop_back() 弹出队尾元素 q.push_front() 从队列头添加元素 q.push_back() 从队列尾部添加元素 优先队列 大小根堆 priority_queue<结构类型> 队列名; 自动排序 默认从大到小排序 q.size();//返回q里元素个数 q.empty();//返回q是否为空，空则返回1，否则返回0 q.push(k);//在q的末尾插入k q.pop();//删掉q的第一个元素 q.top();//返回q的第一个元素 priority_queue <int,vector<int>,less<int> > p; // 大顶堆 <int,vector<int>,greater<int> > q; // 小顶堆 struct node { int x,y; node(int a,int b){ x = a,y = b; } bool operator < (const node & t) const //函数重载 { return x-t.x < 0 降序 } }; string back() 返回尾巴 front() 返回头 pop_back() 尾巴弹出 push_back() 压入尾巴 erase(pos) 从 字符串下标 pos开始删除，一直到结尾 erase(pos,len) 从 字符串下标 pos开始删除len个长度字符 s.compare(xxx) 字符串比较，若相等则返回值为零 substr有2种用法： 假设：string s = "0123456789"; string sub1 = s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾：sub1 = "56789" string sub2 = s.substr(5, 3); //从下标为5开始截取长度为3位：sub2 = "567" 返回值： string，包含s中从pos开始的len个字符的拷贝。pos的默认值是0，len的默认值是s.size() - pos，即不加参数会默认拷贝整个s。 substr(size_type _Off = 0,size_type _Count = npos) 异常 ：若pos的值超过了string的大小（注意是超过了，并不是等于，并且它会自动的去调整），则substr函数会抛出一个out_of_range异常；若pos+n的值超过了string的大小，则substr会调整n的值，只拷贝到string的末尾 vector （1）a.assign(b.begin(), b.begin()+3); //b为向量，将b的0~2个元素构成的向量赋给a （2）a.assign(4,2); //是a只含4个元素，且每个元素为2 （3）a.back(); //返回a的最后一个元素 （4）a.front(); //返回a的第一个元素 （5）a[i]; //返回a的第i个元素，当且仅当a[i]存在2013-12-07 （6）a.clear(); //清空a中的元素 （7）a.empty(); //判断a是否为空，空则返回ture,不空则返回false （8）a.pop_back(); //删除a向量的最后一个元素 （9）a.erase(a.begin()+1,a.begin()+3); //删除a中第1个（从第0个算起）到第2个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+ 3（不包括它） （10）a.push_back(5); //在a的最后一个向量后插入一个元素，其值为5 （11）a.insert(a.begin()+1,5); //在a的第1个元素（从第0个算起）的位置插入数值5，如a为1,2,3,4，插入元素后为1,5,2,3,4 （12）a.insert(a.begin()+1,3,5); //在a的第1个元素（从第0个算起）的位置插入3个数，其值都为5 （13）a.insert(a.begin()+1,b+3,b+6); //b为数组，在a的第1个元素（从第0个算起）的位置插入b的第3个元素到第5个元素（不包括b+6），如b为1,2,3,4,5,9,8 ，插入元素后为1,4,5,9,2,3,4,5,9,8 （14）a.size(); //返回a中元素的个数； （15）a.capacity(); //返回a在内存中总共可以容纳的元素个数 （16）a.resize(10); //将a的现有元素个数调至10个，多则删，少则补，其值随机 （17）a.resize(10,2); //将a的现有元素个数调至10个，多则删，少则补，其值为2 （18）a.reserve(100); //将a的容量（capacity）扩充至100，也就是说现在测试a.capacity();的时候返回值是100.这种操作只有在需要给a添加大量数据的时候才 显得有意义，因为这将避免内存多次容量扩充操作（当a的容量不足时电脑会自动扩容，当然这必然降低性能） （19）a.swap(b); //b为向量，将a中的元素和b中的元素进行整体性交换 （20）a==b; //b为向量，向量的比较操作还有!=,>=,<=,>,< vector<string> xxx 去重 or vector<vector<int>>xxx 需要sort()排序 ans.erase(unique(ans.begin(),ans.end()),ans.end()); "unique"是C++语言中的STL函数，包含于<algorithm>头文件中。功能是将数组中相邻的重复元素去除。 配合erase 进行相关删除操作， 其本质是将重复的元素移动到数组的末尾， 返回迭代器指向第一个重复元素的下标。 取容器内部最大值 int mx = *max_element(nums.begin(), nums.end()); sort(s.begin(),s.end(),[](string &a,string &b){ return a+b>b+a;}); 队列 queue<>q; q.pop() 弹出队列头 q.push() 压入队尾 q.front() 队列头元素 q.back() 队列尾元素 stack常用函数实例解析 （1）push() push(x)将x入栈，时间复杂度为O(1)，实例见“ stack容器内元素的访问”。 （2）top() top()获得栈顶元素，时间复杂度为O(1)，实例见“ stack容器内元素的访问”。 （3）pop() pop()用以弹出栈顶元素，时间复杂度为O(1) （4）peek() 返回栈顶元素并且 不删除 红黑树的平衡二叉检索树的数据结构（set）无重复值 multiset篇（平衡二叉树，允许重复值） 这里使用multiset维护一个滑动窗口，用multiset的好处是自动排序，所以在计算是否超出限制时，直接把multiset的头和尾相减即可进行判断，multiset的缺点就是太耗费内存了，但是为了更好理解本题，牺牲一下内存也是可以理解的 multiset<>st *st.rbegin() 返回一个逆向迭代器，指向逆向迭代的第一个元素 *st.begin() 返回一个随机存取迭代器，指向第一个元素 st.insert(...) 插入元素 st.erase(...) 移除元素 位置 or 元素 st.find(...) 返回元素值为elem的第一个元素，如果没有返回end() /* 删除头元素 mt.erase(mt.begin()); 删除尾元素 mt.erase(std::prev(mt.end())); 遍历序列元素 for(auto it = mt.begin(); it != mt.end(); it++){ avg += *it; } 【优点、缺点、使用场景】 map 优点：有序性，可以简化很多操作，效率较高 缺点：空间占用率高，因为为了保存有序性，需要额外保存父节点，孩子结点以及红黑性质，使得每一个节点都占用大量的空间。 适用性：对于顺序要求高的问题，使用map会更加高效一些 unordered_map 优点：内部实现了哈希表，因此查找速度非常快 缺点：哈希表的建立时间比较耗时 适用性：对于查找问题更加高效。 */ 完成类似这样的调用！ unordered_map<int, vector<int>> pos; auto &res = pos[target]; return res[rand() % res.size()]; 1. //遍历输出 umap 容器中所有的键值对 2. for (auto iter = umap.begin(); iter != umap.end(); ++iter) { 3. cout << "<" << iter->first << ", " << iter->second << ">" << endl; 4. } An=A1+(n-1)d An=Am+(n-m)d d是公差 等差数列的前n项和： Sn=[n(A1+An)]/2 Sn=nA1+[n(n-1)d]/2 反转数字 int rev(int num){ int res = 0; while(num != 0){ res = (num % 10) + (res * 10); num /= 10; } return res; } unordered_map< , >xx =================迭代器=========================  begin 　　返回指向容器起始位置的迭代器（iterator）  end 　　   返回指向容器末尾位置的迭代器  cbegin　   返回指向容器起始位置的常迭代器（const_iterator）  cend 　　 返回指向容器末尾位置的常迭代器  =================Capacity================  size  　　 返回有效元素个数  max_size  返回 unordered_map 支持的最大元素个数  empty        判断是否为空  =================元素访问=================  operator[]  　　   访问元素  at  　　 　　　　访问元素  =================元素修改=================  insert  　　插入元素  erase　　 删除元素  swap 　　 交换内容  clear　　   清空内容  emplace 　构造及插入一个元素  emplace_hint 按提示构造及插入一个元素  ================操作=========================  find 　　　　　　通过给定主键查找元素,没找到：返回unordered_map::end count 　　　　　返回匹配给定主键的元素的个数  equal_range 　　返回值匹配给定搜索值的元素组成的范围  ================Buckets======================  bucket_count 　　　返回槽（Bucket）数  max_bucket_count    返回最大槽数  bucket_size 　　　   返回槽大小  bucket 　　　　　　返回元素所在槽的序号  load_factor　　　　 返回载入因子，即一个元素槽（Bucket）的最大元素数  max_load_factor 　  返回或设置最大载入因子  rehash　　　　　　 设置槽数  reserve 　　　　　  请求改变容器容量 ———————————————— unordered_set 哈希表 unordered_set的迭代器 函数声明 功能介绍 begin 返回unordered_set第一个元素的迭代器 end 返回unordered_set最后一个元素下一个位置的迭代器 cbegin 返回unordered_set第一个元素的const迭代器 cend 返回unordered_set最后一个元素下一个位置的const迭代器 4、unordered_set的操作 函数声明 功能介绍 bool empty() const 检测unordered_set是否为空 size_t size() const 获取unordered_set的有效元素个数 iterator find(const key_type& k) 返回k在哈希桶中的位置 size_t count(const key_type& k) 返回哈希桶中关键码为k的键值对的个数 insert 向容器中插入键值对 erase 删除容器中的键值对 void clear() 清空容器中有效元素个数 void swap(unordered_set&) 交换两个容器中的元素 size_t bucket_count()const 返回哈希桶中桶的总个数 size_t bucket_size(size_t n)const 返回n号桶中有效元素的总个数 size_t bucket(const key_type& k) 返回元素key所在的桶号 ———————————————— 状态压缩 一个二进制数 int 类型 int iscut(string s){ int n=s.length(); int ans=0; for(int i=0;i<n;i++){ ans|=(1<<(s[i]-'a')); } return ans; } 枚举一个二进制数的子集 int sub = k; do { sub = (sub - 1) & k; }while(sub != k); set 有序列表的集合 begin()     　　 返回set容器的第一个元素 end() 　　　　 返回set容器的最后一个元素 clear()   　　    删除set容器中的所有的元素 empty() 　　　判断set容器是否为空 max_size() 　 返回set容器可能包含的元素最大个数 size() 　　　　 返回当前set容器中的元素个数 rbegin　　　　 返回的值和end()相同 rend()　　　　 返回的值和rbegin()相同 count() 用来查找set中某个键值是否有出现过（0，1）。 equal_range()  erase(iterator) ,删除定位器iterator指向的值 erase(first,second),删除定位器first和second之间的值 erase(key_value),删除键值key_value的值 find() ，返回给定值值得定位器，如果没找到则返回end()。 insert(key_value); 将key_value插入到set中 ，返回值是pair<set<int>::iterator,bool>，bool标志着插入是否成功，而iterator代表插入的位置，若key_value已经在set中，则iterator表示的key_value在set中的位置。 inset(first,second);将定位器first到second之间的元素插入到set中，返回值是void. lower_bound(key_value) ，返回第一个大于等于key_value的定位器 end() 返回最后元素的下一个元素。 upper_bound(key_value)，返回最后一个大于等于key_value的定位器 pair pair<T1,T2>    p; 创建一个pair，包含两个已经被默认初始化的，类型分别为T1、T2的成员 pair<T1,T2>    p(v1,v2); 创建一个pair，first成员的类型为T1，值为v1，second成员的类型为T2，值为v2 pair<T1,T2>    p={v1,v2}; 创建一个pair，first成员的类型为T1，值为v1，second成员的类型为T2，值为v2 make_pair(v1,v2); 返回一个用v1和v2初始化的pair，pair的类型从v1和v2的类型推断出来 p.first; 返回p的first数据成员 p.second; 返回p的second数据成员 sscanf() sprintf()