一、滑动窗口类

可能需要上滑动窗口策略的方法：

这个问题的输入是一些线性结构：比如链表呀，数组啊，字符串啊之类的

让你去求最长/最短子字符串或是某些特定的长度要求

面对的题：满足一定条件的连续区间的性质（长度）等

由于区间连续，因此当区间发生变化时，可以通过旧有的计算结果对搜索空间进行剪枝，这样便减少了重复计算，降低了时间复杂度。往往类似于“请找到满足xx的最x的区间（子串、子数组）的xx”这类问题都可以使用该方法进行解决。

二、双指针类型

双指针是这样的模式：两个指针朝着左右方向移动（双指针分为同向双指针和异向双指针），直到他们有一个或是两个都满足某种条件。双指针通常用在排好序的数组或是链表中寻找对子。比如，你需要去比较数组中每个元素和其他元素的关系时，你就需要用到双指针了。

使用双指针的招数：

一般来说，数组或是链表是排好序的，你得在里头找一些组合满足某种限制条件

这种组合可能是一对数，三个数，或是一个子数组

同向的双指针，初始化一般是：

int l = 0, r = -1; //滑动窗口为s[l...r]   窗口长度是r-l+1

三、快慢指针

在解决有环的链表和数组时特别有用。

问题需要处理环上的问题，比如环形链表和环形数组

当你需要知道链表的长度或是某个特别位置的信息的时候

下面是这种的代码

顺便 dummphead的新建：

然后一般return是 return dummyHead->next

四、区间合并

区间合并模式是一个用来处理有区间重叠的很高效的技术

当你需要产生一堆相互之间没有交集的区间的时候

当你听到重叠区间的时候

先排序 注意排序的写法 特别是cmp

也可以这么写

sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {

            return u[0] < v[0];

        });

五、循环排序

可以用来处理数组中的数值限定在一定的区间的问题。这种模式一个个遍历数组中的元素，如果当前这个数它不在其应该在的位置的话，咱们就把它和它应该在的那个位置上的数交换一下。你可以尝试将该数放到其正确的位置上，但这复杂度就会是O(n^2)。这样的话，可能就不是最优解了。因此循环排序的优势就体现出来了。

这些问题一般设计到排序好的数组，而且数值一般满足于一定的区间

如果问题让你需要在排好序/翻转过的数组中，寻找丢失的/重复的/最小的元素

一般例如

这种题

方法太多了，包括用hashmap强搜 或者就交换位置这样

六、链表翻转

需要你去翻转链表中某一段的节点。通常，要求都是你得原地翻转，就是重复使用这些已经建好的节点，而不使用额外的空间。这个时候，原地翻转模式

七、BFS和DFS

BFS 宽度优先

适用于需要遍历一颗树。借助于队列数据结构，从而能保证树的节点按照他们的层数打印出来。打印完当前层所有元素，才能执行到下一层。所有这种需要遍历树且需要一层一层遍历的问题，都能用这种模式高效解决。

这种树上的BFS模式是通过把根节点加到队列中，然后不断遍历直到队列为空。每一次循环中，我们都会把队头结点拿出来（remove），然后对其进行必要的操作。在删除每个节点的同时，其孩子节点，都会被加到队列中。

DFS 深度优先 dfs一般就是和递归联系在一起的

咱们可以用递归（或是显示栈，如果你想用迭代方式的话）来记录遍历过程中访问过的父节点。

该模式的运行方式是从根节点开始，如果该节点不是叶子节点，我们需要干三件事：

1.需要区别我们是先处理根节点（pre-order，前序），处理孩子节点之间处理根节点（in-order，中序），还是处理完所有孩子再处理根节点（post-order，后序）。

2.递归处理当前节点的左右孩子。

识别树形DFS：

你需要按前中后序的DFS方式遍历树

如果该问题的解一般离叶子节点比较近。

八、双堆类型

我们被告知，我们拿到一大把可以分成两队的数字

如果问题让你找一组数中的最大/最小/中位数

有时候，这种模式在涉及到二叉树数据结构时也特别有用

判断双堆模式的秘诀：

这种模式在优先队列，计划安排问题（Scheduling）中有奇效

如果问题让你找一组数中的最大/最小/中位数

有时候，这种模式在涉及到二叉树数据结构时也特别有用

如果我们可以用以下方式维护两个堆：

用于存储输入数字中较小一半的最大堆

用于存储输入数字的较大一半的最小堆

这样就可以访问输入中的中值：它们组成堆的顶部！

添加一个数 num：

将 num 添加到最大堆 lo。因为 lo 收到了一个新元素，所以我们必须为 hi 做一个平衡步骤。因此，从 lo 中移除最大的元素并将其提供给 hi。

在上一个操作之后，最小堆 hi 可能会比最大堆 lo 保留更多的元素。我们通过从 hi 中去掉最小的元素并将其提供给 lo 来解决这个问题。

延迟删除：

九、子集

问题需要咱们去找数字的组合或是排列

一般都是使用多重DFS，一般用回溯来解

注意unorered_map里string的取用

十、优化后的二分

需要解决的问题的输入是排好序的数组，链表，或是排好序的矩阵，要求咱们寻找某些特定元素。这个时候的不二选择就是二分搜索

十一、前K个

任何让我们求解最大/最小/最频繁的K个元素的题，都遵循这种模式。用来记录这种前K类型的最佳数据结构就是堆了

识别最大K个元素模式：

如果你需要求最大/最小/最频繁的前K个元素

如果你需要通过排序去找一个特定的数

#include<queue>

#include<vector>

std::priority_queue<int> big_heap;  // 构造一个默认最大堆

std::priority_queue<int, std::vector<int>, std::greater<int> > small_heap; //构造一个最小堆

十二、多路并合

涉及到多组排好序的数组的问题  合并多个排好序的集合，或是需要找这些集合中最小的元素

每当你的输入是K个排好序的数组，你就可以用堆来高效顺序遍历其中所有数组的所有元素。你可以将每个数组中最小的一个元素加入到最小堆中，从而得到全局最小值。当我们拿到这个全局最小值之后，再从该元素所在的数组里取出其后面紧挨着的元素，加入堆。如此往复直到处理完所有的元素。

十三、0/1背包

十四、拓扑排序

90% 的字符串问题都可以用动态规划解决，并且90%是采用二维数组

因为树是一种递归的结构 所以用递归解决往往很容易

BFS广度优先搜索往往对应一个queue？ 例如 首先让根节点入队 然后出队所有节点，同时把节点的左右子树入队，具体可以看104

哈希表 也就是unordered_map  可以建立键值对 然后快速返回map里是否包含某个值:  m.count(t)

定义dummy头的时候注意 dummy并不是一个指针

一般比如  ListNode * p = head；

但dummy是： ListNode dummy；

                        dummy.next = head;

二叉搜索树的中序遍历是升序序列

2.1构成递归需具备的条件：

子问题须与原始问题为同样的事，且更为简单；

不能无限制地调用本身，须有个出口，化简为非递归状况处理。

2.2递归的基本原理

第一：每一级的函数调用都有自己的变量。

第二：每一次函数调用都会有一次返回。

第三：递归函数中，位于递归调用前的语句和各级被调用函数具有相同的执行顺序。

第四：递归函数中，位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反。

第五：虽然每一级递归都有自己的变量，但是函数代码并不会得到复制。

回溯： 核心思想就是递归

设计思路

注意看 在主函数combinationSum里，第一次进入dfs时需要的参数，ans是结果保存，combine是当前状态，第一次进入的时候只需要给一个空就行，0是index，我感觉基本所有回溯法都需要这些参数：最终结果保存、当前状态（当前状态构建完成之后就是结果之一），遍历的Index（用来记录我们遍历到原始数据的第几项了）；

所以，idx=原始数据.size时 肯定就return（但不加入结果，这时意味着我们这次回溯没有找到可行解）

而target满足时，肯定就return 而且加入结果

但这里没有显式的for循环 有点不好理解

更好理解的是这种：

注意，这里必须满足t-c[i]>0 这其实就是标准解法里该用if去限定的 但这里把它和for循环的条件放在了一起

多叉树的遍历框架

动态规划：

编程注意：

vector初始化赋值 

或者

three-sums 为了不重复 一般直接先排个序

sort(nums.begin(), nums.end());

数组最后一位的指针是   int right = size-1；

迭代器和auto基本用法：

注意 iter可以直接+1，以及iter是个指针 用*iter可以直接取值

二分搜索:

二分搜索最主要的循环就是这个while

注意，l初始化为0  r初始化为n-1  循环的条件为l<=r  mid值为(l+r)/2   分出来的两个区间是 「l , mid-1」和「mid+1，r」  (mid已经是target的话直接返回)

一般递归的方法 都自己再定义一个函数 因为接口肯定不一样

stack:

stack<int> stk;   stk.push   stk.pop   stk.length   stk.empty()

动态规划：

注意自己dp的选择

比如 题目要求 ：

给你一个只包含 '('和 ')'的字符串，找出最长有效（格式正确且连续）括号子串的长度。

那我们你的dp「i」就是 字符串从0到第i项时 最长的子串长度吗？  显然不能是这个 因为这时 dp[i]和字符串第i项可能有关1，也可能无关（因为最长子串很可能根本不用字符串第i项的值），这会使得我们的递推很难写

所以我们定义dp[i]为以下标 i字符结尾的最长有效括号的长度，这样，我们最终的结果就只是一个maxdpi

注意两个循环的写法，以及二维vector的初始化如下

以及注意，初始化一个m*n的vector  最后一项是m-1 n-1

pair的定义和使用

数组初始化：

静态数组

这种真的是正确的吗,是错的，这不是c++

这才是对的  int i[5] = {1,2,3,4,5}; 一定是正确的  或者 int i[]={1,2,3,4,5}

一般干脆直接用vector：
vector<int> values={1000,900,500,400,100,90,50,40,10,9,5,4,1};

树的建立：

首先 建立根节点肯定是 TreeNode * root = new TreeNode(value);

一般 在有所谓前序遍历或者各种遍历的时候，value = preoreder[index];

然后建立左右子树

root->left = xxxxx

二叉树最好是和父节点的值比较 因为有当前节点 那就一定有父节点而且有值  

如果写  root->value == root->right->value 的话 我反正还没想好怎么写其中的越界判断

最大堆最小堆：

priority_queue<int, vector<int>, less<int>> big_heap;

队列：

queue<TreeNode*> nodeQueue;

双向队列（可以用push_back 和push_front）  deque<int> levelList;  看情况决定从哪个方向加入 最后输出直接：

ans.emplace_back(vector<int>{levelList.begin(), levelList.end()});

一般重新建立一个dfs函数 目的是做从根节点到子节点的信息传递（prevSum）

单调栈主要回答这样的几种问题

比当前元素更大的下一个元素

比当前元素更大的前一个元素

比当前元素更小的下一个元素

比当前元素更小的前一个元素

单调递增栈可以找到左起第一个比当前数字小的元素:

弹出的意思是 这个数已经找到右边第一个比他小的数了 不需要找了

动态规划、dfsbfs、回溯、分治