所有的套路都只是提供一种思想，列出来的是典型的格式，切不可每道题都生搬硬套
提高语言表达能力：不管这个想法是否正确，把自己的想法用代码快速表示出来的能力
总结出每一种套路的特性，每种套路分别需要知道哪些信息、条件才能使用这种套路，从题目中抽取这些信息
不要一开始就想着用什么套路可以解题，要从问题出发按照自己的思路去寻找切入点（实在想不出来再试试往哪个套路上靠，看看哪个套路可以解），然后看看自己想的这种方法对应哪种套路，如果都对不上，那就要想一想是否还有其他方法（但也不能太生硬的使用套路，套路只是提供了一种典型的思路），慎用自己的解法，因为用自己的野路子很可能行不通
当我不知道遍历一个序列何时才能找到我想要的那个元素时，可以用while()来作为结束遍历的条件，也可以用for(){if(){break;}}，如果是对序列中的每一个元素都做相同的处理时，一般用for来遍历所有元素，也可以用while(n<len)来设置结束条件
一般习惯用前者
先考虑一般情况的处理再考虑特殊情况的处理
找出问题的一般规律，再套用合适的算法
先实现一般场景流程，再补充特殊场景流程
先实现灵感中的关键步骤，再补充其余步骤
不要一开始就妄想写出完整的代码，先实现主体框架，再补充细节
字符串与数字间的相互转换？
常见题型：
贪心算法？
动态规划？
递归？
最短路径？
排序
回溯算法
二分查找及其变种
二分查找必须是在一个有序序列中才能使用吗？
1019 单调栈？
序列问题：贪心，栈，滑动窗，动态规划，双指针，并查集，前缀和
处理链表的中间元素：
1. 快慢指针（LeetCode 2095 删除链表的中间节点）
环形链表、求两个链表的相交节点,要求空间效率为O(1)：把2个链表拼接起来，用2个指针p1,p2分别遍历2个链表，总有一次处理他们会相遇（p1==p2）
判断是否要用动态规划：序列中后出现的元素会影响前面的子序列的解
二叉树：
2种不同顺序遍历二叉树：
1. 把二叉树上的点摊平到一条水平轴上，则对二叉树而言，在递归函数中，如果先对左节点进行递归调用，则处理顺序就是依次对水平轴上的点从左到右进行处理。同理如果是先对右节点进行递归调用，则是从右往左的处理顺序。(其实就是DFS)
注意！在递归函数中，先调用递归函数，还是先处理当前节点，决定了节点的处理顺序！
例如：
1 void traverse(treeNode * node){
2
3 /****A****/
4
5 traverse(node->left);
6
7 /****B****/
8
9 traverse(node->right);
10
11 /****C****/
12
13 }
选择在A,B,C三个不同的区域处理当前节点，得到的整棵树的节点处理顺序是不同的！！
一般我们把处理当前节点流程放在B，这样就表示整棵树的节点平铺到水平轴上时，以从左到右的顺序处理节点！（先right后left的话就表示从右到左）
2. 利用BFS算法，将队列头部节点的左节点先放入队列，右节点后放入，则逐个处理队列头（处理完后将其弹出）即逐层以从左到右的顺序处理，反之从右到左（2312完全二叉树）
贪心算法:
所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择，只考虑对当前这一步迭代中的问题做出最佳的选择，每作一次贪心选择就将所求问题简化为规模更小的子问题，并且保证以同样的处理方式处理每一步迭代最终得到的解就是最优解，即问题的关键是，每次迭代中所作的处理，可以将问题变为规模更小的相同的问题(也就是可以反复做同样的处理)，并且这个处理到最后可以得到正确答案。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
应用场景：每次都进行同样的操作可以得到当前问题域的最优解
Greedy(C) //C是问题的输入集合即候选集合
{
S={ }; //初始解集合为空集
while (not solution(S)) //集合S没有构成问题的一个解
{
x=select(C); //在候选集合C中做贪心选择
if feasible(S, x) //判断集合S中加入x后的解是否可行
S=S+{x};
C=C-{x};
}
return S;
二分查找经典应用：当我们以单步+1的方式逐渐去寻找我们想要的数行不通时（太慢），可以考虑能否通过二分查找来快速查找（要先确定好取值范围）（1011）
大数相加/相乘/相除（直接算会溢出的那种，一般需要用到与字符串相转换，或者模拟人手算过程）（989）
双指针问题（986）
并查集/图（990,1722）
dfs（）
bfs（994）
哈希（997, 1002）
模拟（999）
矩阵/数组（999）
栈
序列处理：一般使用单调栈、回溯、贪心、滑动窗
1. 使用单调栈时，不是说非得用栈来实现，而是要使用单调栈思想，栈功能可以用其他容器来实现（1081（2种方法都提交了））
处理一个序列时，有些可以边遍历边处理，有些是一定要知道序列全貌后才能进行下一步处理，有2种方法：
1) 先把序列遍历一遍，知道序列全貌后再进行下一步逐个处理；（1054，1090）
2) 也有些是可以一边遍历一边处理：但是每遍历一个元素就要往前或往后观察这个元素是否满足，相当于变相地观察了全貌（1081）
2. 处理以空格为分隔符的字符串序列时可以用stringstream（1078）
3. 处理以某个字符为分隔符来分割字符串可以用 istringstream + getline （71）
前缀和问题
在一个序列{a0,a1,a2,...,an-1}中，如果要对第p到第q项加上某一值m(0<=p<q<=n-1)，
对第x到第y项加上某一值k(0<=x<y<=n-1)，...(p,q,x,y为下标)
则可设前缀和数组{b0,b1,b2,...,bn-1}（初始化为0）第p,q项：
bp += m；
if(q != n-1) //注意这种情况
bq+1 += -m;
bx += k;
if(y != n-1)
by+1 += -k;
...
就可以通过累加的方式一次性处理前缀和数组，并将其加到目标序列中：
for(int i=1; i<n; ++i){
bi += bi-1;
}
for(int i=0; i<n; ++i){
ai += bi;
}
滑动窗问题（注意下面内部嵌套的while也可以用其他的代替，）：
例1：
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left=0, right = 0, len = nums.size(), znum=0, cur = 0, fi = 0;
if(k==0){
int cur = 0;
for(auto iter = nums.begin(); iter != nums.end(); ++iter){
if(*iter != 0)cur++;
else {
fi = fi>cur?fi:cur;
cur = 0;
}
}
return fi>cur?fi:cur;
}
while(right < len){
if(nums[right] == 0)
znum++;
cur++; // 挪动右指针的同时滑动窗的一些参数也要跟着变化
// 这里这个满足条件设置的不是很好，znum固定为k和nums[right+1]==0，没有考虑k可能为0，right到达尽头的情况（所以才要补充right == len -1 和 前面k为0的情况）
while(znum==k && (right == len -1 || nums[right+1]==0)){ // 设置滑动窗的满足条件很关键！（挪动右指针，直到满足条件时挪动左指针，直到再次不满足条件）
fi = fi>cur?fi:cur; //每挪动一次左指针都要更新一次结果
if(nums[left]==0)znum--;
cur--; // 注意在挪动左指针的同时滑动窗的一些参数也要跟着变化 （注意看这里滑动窗的参数： znum 和 cur ， 在挪动右值针时也同样是这些参数在变化，且方向正好相反）
left++; // 在内部while 中挪动左指针
}
right++; // 把当前指向的元素处理完后，最后才挪动指针到下一个元素
}
return fi>cur?fi:cur;
}
};
例2：
class Solution {
public:
int longestOnes(vector<int>& A, int K) {
int cnt=0,left=0,right=0,len=A.size();
while(right<len){
if(!A[right]) ++cnt;
++right;
if(cnt>K) { //使用 cnt>K 适配了 K=0 的特殊情况
if(!A[left]) --cnt;
++left;
}
}
return right-left;
}
};
遍历顺序容器时
下标？ 需要求出容器的长度，确保不会访问越界
迭代器？只有用迭代器遍历时可以增删元素（因为增删后容器长度发生变化容易导致越界，而只有iter!=c.end()这个是不以c的长度作为结束条件的，erase入参为迭代器），但是要慎用（容易用乱）
范围for循环？ 遍历整个容器，可以修改元素，但不能增删元素
无论哪种方式，都不能在遍历容器的时候对容器增删元素！否则会导致遍历发生错乱！
小技巧：
如果实在想不到什么方法，可以看一下题目给的问题规模，如果不是很大的话就用最笨的方法，在保证不会超时或者不会超出给定的内存大小的情况下，一个一个遍历，或者用一块可能性最大的内存来保存结果
慎用迭代器！如果要增加/删除序列中的元素，不要采用遍历整个序列的方式，容易把迭代器用乱！可以在循环外创建一个副本，然后再增删这个副本，循环结束后用这个副本取代原来的序列。
或者用这样的方法（不推荐）：
if(XXX){
iter = s.insert(iter);
//or iter = s.erase(iter)-1;
}
不是万不得已不要用反向迭代器，因为像insert，erase这样的方法不支持反向迭代器(556)
（或者直接使用c++自提供的函数__gcd(a,b)）
gcd(a,b)可用于求最a,b的最大公约数：
int gcd(int a, int b) {
if (a % b == 0) return b;
return gcd(b, a%b);
}
回文特性：
正序和倒序一样
所给的序列中，数量为奇数的字符的数量有n个，就意味着这个序列的字符组成的回文串数量不可能少于n个
回文串中数量为奇数的字符至多有1个
回文串左右同等缩进得到的子串也是回文串(对称位置的元素相等),或者说如果下标为i,j的子串为回文串，那么如果下标为i-1,j+1的元素相同，下标为i-1,j+1的子串也是回文串
可以用栈的思想处理回文
sort还能这么用：
sort(mp.rbegin(), mp.rend()); //从大到小排序
二分查找：
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意
while(left <= right) { // 注意
int mid = (right + left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}
当循环退出时，除非找到了target，否则一定有left==right+1，且left或right都有可能越界（left==nums.length 或right==-1）
这里right 初始化为nums.length - 1，所以while中的条件是left <= right（即left可以等于right）,每次循环搜索的区间是[left, right]，所以right更新是right = mid - 1。
但是：
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length; // 注意
while(left < right) { // 注意
int mid = (right + left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}
如果right 初始化为nums.length，所以while中的条件是left < right（即left不能等于right）,每次循环搜索的区间是[left, right)，所以right更新是right = mid。（如果是 mid - 1的话，则下一次循环搜索的区间是[left, mid-1)，就会错过mid-1这个数）
综上：
l right初始化为nums.length对应while(left < right)对应right更新方式为right = mid，循环结束时一定有left==right（中途没有break的话）且有可能越界（left=right=nums.length）
l right初始化为nums.length-1对应while(left <= right)对应right更新方式为right = mid-1,循环结束时一定有right+1==left（中途没有break的话），且有可能越界（left=nums.length或right=-1）
二分查找可分为三大类：
1. 找指定的target
初始化right=nums.length,退出循环后先判断是否越界(即left是否等于nums.length),
再判断nums[left]是否等于target(判断left就行了，因为left==right)，不等的话说明序列中没有target
2. 找左边界
初始化right=nums.length,退出循环后先判断是否越界(即left是否等于nums.length),
然后再判断nums[left]是否等于target(当循环结束时如果不越界，nums[left]一定是大于等于target的最小者)，不等的话说明序列中没有target
while(left < right){
int mid = left +(right-left)/2;
if(letters[mid] < target)
left = mid+1;
else
right = mid;
}
3. 找右边界
初始化right=nums.length,退出循环后先判断是否越界(即left是否等于nums.length),
然后再判断nums[left-1]是否等于target（注意先判断left-1是否越界）(当循环结束时如果不越界，nums[left]一定是大于target(注意没有等于)的最小者)，不等的话说明序列中没有target
while(left < right){
int mid = left +(right-left)/2;
if(letters[mid] > target)
right = mid;
else
left = mid + 1;
}
//注意一定不能left和right的更新方式都等于mid，否则可能陷入死循环
寻找左/右边界时也可以先判断左端点/右端点是否大于/小于target，如果是的话就不用进入循环了
vector, 数组索引的意义：arr[pos]，表示pos这个索引的数前面有pos个数，例如当我们获得string中某个字符的索引pos后，我们可以用string::substr(0, pos)来截取这个字符前的子字符串。
大小写转换：
方法一：
小写字母比大写字母大32，所以：
小写字母 = 大写字母+32
方法二：
大小写转换函数：
toupper （入参可以是int也可以是char）
tolower
下面的函数入参必须是char：
判断是否是字母、小写、大写、数字：
isalpha()
islower()
isupper()
isdigit()
判断是否是字母或数字（a~z||A~Z||0~9）：
isalnum()
经典回文处理：头尾双指针
记得multimap中是不能用key来做索引的，其他该有的性质和map一样
multiset暂时没发现有什么禁忌
求最值的min_element, max_element
迭代器遍历，反向迭代器
都能用
unordered_map不能用pair来做key,除非重定义 operator==()
iota(s.begin(), s.end(), T)
这个函数前两个参数是一对迭代器，第三个参数是这个迭代器范围的初始值，随后的值会调用T类型的operator++()来自增后依次填入，有点像Python的列表生成式（但是只能自增1），例如1：
std::vector<double> data(9);
double initial {-4};
std::iota (std::begin (data) , std::end (data) , initial);
std::copy(std::begin(data), std::end(data),std::ostream_iterator<double>{std::cout<< std::fixed << std::setprecision(1), " "});
std::cout << std::endl; // -4.0 -3.0 -2.0 -1.0 0.0 1.0 2.0 3.0 4.0
例如2：
string text {"This is text"};
std::iota(std::begin(text), std::end(text), 'K');
std::cout << text << std::endl; // Outputs: KLMNOPQRSTUV
例如3：
std::vector<string> words (8);
std::iota(std::begin(words), std::end(words), "mysterious");
std::copy(std::begin(words), std::end(words),std::ostream_iterator<string>{std::cout, " "});
std::cout << std::endl; // mysterious ysterious sterious terious erious rious ious ous
//这里因为入参是一个字符串常亮，相当于char *p,自增p相当于指向下一个字符，但如果是一个string的话就不像，因为string没有定义operator++()
处理异位字符串：老老实实用map统计字符串中各个字符的数量，然后比较map是否相等（map也支持==运算符）！不要想着用set/multiset/unordered_set或者把序列排序后再比较！
（eg: 438. 找到字符串中所有字母异位词）
unordered_set/unordered_map里元素顺序是不固定的，增/删元素都有可能导致排序发生变化！(iter=st.begin(); iter != st.end(); ++iter)这种方式只能遍历元素！
例如：
int main(){
string s = "zxcvvbnm";
unordered_set<char> st(s.begin(), s.end());
for(auto &item : st){
cout << item << " "; // 你会发现st中字符的顺序和s不一样！所以你如果想通过st.erase(st.begin())来删掉z的话会出错！
}
cout << endl;
}
蓄水池抽样算法：解决这样一个问题：
当一个数据流很大（比如一串长度不知道多少的序列，假设长度为n），且不知道各个不同的元素在序列中占比多少，要想随即从序列中抽取m个不同的元素，且被抽中的概率等于每个元素在序列中的占比.
https://www.jianshu.com/p/7a9ea6ece2af
dfs还有这种用处呢：列出所有可能排列 (剑指 Offer 38. 字符串的排列)
判断质数的方法（0，1都不是质数）：
bool isPrime(int x) {
if (x < 2) {
return false;
}
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) {
return false;
}
}
return true;
}
统计一个数a在二进制下的”1”的个数：
__builtin_popcount(a)
获取一个序列的所有子集（LeetCode 面试题 08.04. 幂集）：
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
int len = nums.size();
vector<vector<int>> res(1,vector<int>({}));
for(auto &item : nums){
vector<vector<int>> tmp = res; //
for(auto &vt : res){ // 遍历当前集合中的所有序列，在每个序列尾部加上新的元素，得到新的序列再加入到现有集合中
vt.push_back(item);
tmp.push_back(vt);
}
swap(tmp, res);
}
return res;
}
};
当问题解的可能情况较多，且问题域较小时，有可能是让你暴力解出所有的可能性
回溯（n叉树的遍历）:
1. 列出所有组合情况（面试题 08.04. 幂集（经典滴酱油法））
2. 列出所有排列情况（剑指 Offer 38. 字符串的排列）
3. 列出所有排列组合情况（即全排列：子序列的所有排列组合情况也列出来，本质还是第2类题）
4. 列出所有组合情况中满足某个条件的情况，每个元素可以无限重复（剑指 Offer II 081. 允许重复选择元素的组合）
5. 列出所有子串（可以使用双指针嵌套for循环来解决）
取3个数的最大者：
max(a, max(b,c))
一． 动态规划的关键一步是找出问题域为i时的状态dp[i]所表示的含义
常见线性模型DP方程形式：
1. dp[i]表示以nums[i]为结尾的最优子串的最优值(一般用于求最长/最大子序列)
2. 每次只能从序列的最左或最右端选择，则dp[i][j]表示左边取i个，右边取j个时的最优值（一般需要设dp大小为(len+1)*(len+1)）
3. 找出序列中符合条件的最长子串，一般可以设dp[i][j]表示序列中下标i到下标j的子串的目标值（也可能是布尔值）
结合以上形式推导dp方程时，别忘了dp方程有可能是：
dp[i]=F(dp[i+n]或dp[i-n])(eg:leetcode比特位计数，旋转函数)
还有可能是类似：
dp[i]=F(best{dp[i-1],dp[i-2],...,dp[0]})，也有可能是先把dp[i+n]求出来再求dp[i] （LeetCode完全平方数,最大整除子集，最长子序列）
有时候需要注意推导dp[i]的遍历顺序，例如LeetCode 最长回文子串，设dp[i][j]为从下表i到下标j的子串是否为回文串，是回文串的条件为s[i]==s[j]且dp[i+1][j-1]为true，那么我们知道dp[i][j]是依赖于dp[i+1][j-1]的，所以遍历的时候需要先把i,j差值小的dp求出来
结合以上，有时候还有可能需要维护多个dp（LeetCode 乘积最大子数组）
使用某个符号将元素分割开，可以这样做：
for (int i = 0; i < arr.size() - 1; i++) {
res.append(to_string(arr[i]) + ",");
}
res.append(to_string(arr.back()));
这样就不用怕末尾再带个逗号了
二叉树：
1. 二叉搜索树查找某个元素target时，如果树中没有这个target，则越往下查找（越靠近叶子节点），则值越接近target（当然，如果树不是满的（某些非叶子节点为null），则有可能出现最接近target的元素是非叶子节点），理论上每往下一个节点挪动，就排除掉一半的候选节点
2. 插入新的数一定是放在最底层（叶子节点的子节点）
删除指定节点：教科书式的做法（《算法》P261）：
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(root==nullptr)return root;
if(root->val > key)
root->left = deleteNode(root->left, key);
else if(root->val < key)
root->right = deleteNode(root->right, key);
else { //关键就在这里，代码思路：将val==key的这个target节点的右子树中的最小值节点（也就是最接近key的节点）替换到target的位置
//auto tmp = root;
if(root->left==nullptr)return root->right;
if(root->right==nullptr)return root->left;
auto min_node = getmin(root->right);
// 注意！下面一定要先处理min_node->right再处理min_node->left， 否则报错：Error - Found cycle in the TreeNode
min_node->right = delmin(root->right);
min_node->left = root->left;
return min_node;
}
return root;
}
TreeNode* getmin(TreeNode* node){
if(node->left==nullptr)return node;
return getmin(node->left);
}
TreeNode* delmin(TreeNode* node){
if(node->left==nullptr)return node->right;
node->left = delmin(node->left); // 如果递归函数有返回值时，那么注意在调用递归函数的代码里要有变量接收递归函数的返回值
return node;
}
};
在二叉树里，当要将某个值设为某个节点的子节点时，一般通过递归函数返回值的形式将这个新增的节点返回去给父节点，而不是用prev指针，或者在递归函数参数里把父节点传进来之类的费劲巴拉的操作（654. 最大二叉树，450. 删除二叉搜索树中的节点, 669. 修剪二叉搜索树）,一般是这种形式：
traverse(treenode* node){
if(node==nullptr)return node;
if(XXX){
//当前节点不满足要求，则跳过这个节点，将他的子树的叶子节点（因为叶子节点的值最接近当前节点）作为它的父节点的子节点
//右区间满足要求时，取当前节点的右子树的最小节点
auto newnode = getmin(node->right);
//左区间满足要求时，取当前节点的左子树的最大节点
//or: auto newnode = getmax(node->left);
...
return newnode;
}
node->left = traverse(node->left);
node->right = traverse(node->right);
return node; // 当前节点依然满足要求时，返回这个节点（即这个节点的父节点还是不变）
}
保留某个区间教科书式做法：
class Solution {//把小于low,大于high的节点都删掉
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
root = traverser(root, high);
root = traversel(root, low);
return root;
}
TreeNode * traverser(TreeNode *node, int r){
if(node==nullptr)return node;
if(node->val < r){
node->right = traverser(node->right, r);
}
else if(node->val == r){
node->right=nullptr;
}
else {
/*
auto max_node = getmax(node->left); // 为什么不像删除指定节点那样做？因为删除指定节点后，指定节点的左右子树还需要有别的节点来承接，以顶替指定节点（因为它的父节点不可能同时接收它的两个子树），而这里因为是一个范围，如果节点值已经大于r了，那么它的右子树肯定也都大于r，整个右子树都不要了，所以直接返回左子树就行（在删除指定节点中的红色字体部分其实也是同样的处理，如果其中一个子树是null的话直接返回另一个就行）
if(min_node==nullptr)return min_node;
max_node->left = traverse(node->left);
return max_node;
*/
return traverser(node->left, r);
}
return node;
}
TreeNode * traversel(TreeNode *node, int l){
if(node==nullptr)return node;
if(node->val > l){
node->left = traversel(node->left, l);
}
else if(node->val == l){
node->left=nullptr;
}
else {
return traversel(node->right, l);
}
return node;
}
};
注意下面的式子要加括号：
if(A && (num&1)==0)) //判断奇偶性, (num&1)不加括号的话num&1永远为true（表示这个式子计算没发生错误）
int a=1,b=2;
// 这样做： int c = 5 + b==1?a:b; // c等于2！！
//应该这样：
int c = 5 + (b==1?a:b);
向上取整的方法：
hours += pile % speed == 0 ? pile / speed : (pile / speed)+1;
变为：
hours += (pile-1) / speed + 1;
或者：
(pile + speed - 1) / speed
如果要确定大量元素中每一个是否在一个序列里，最好先把把这个序列存到关系容器里(map或set)，再在关系容器中查找，这样访问关系容器比直接访问序列容器会快很多。（lc817. 链表组件）
标签：node,right,nums,int,算法,小结,节点,left From： https://www.cnblogs.com/tan-wm/p/17071672.html