抱佛脚一时爽，一直抱佛脚一直爽！这篇文章总结常见的思路&提示，具体的解法参考本系列其他文章~

常见思路

是否有路径，其累加和为目标值

题目：lc112（二叉树）
思路：把路径包含的节点的值累加到当前节点

求全排列

题目：lc46（排列组合）；lc78（排列组合）；lc39（排列组合）
思路1：每次取出一个数a，把a插入到当前res中的每个result中
思路2：遍历每个元素，与第一个元素交换，求从第二个元素开始的全排列；记得要换回来！

要求返回结果集

题目：lc22（排列组合）；lc93（排列组合）；lc17（排列组合）；lc113（排列组合）；jz34（二叉树）
拓展：完全背包：lc39（排列组合）；lc139（排列组合）
思路：把当前结果cur引用传递给递归函数，在它后面添加字符/元素，符合条件再push进result；若cur是string，则在调递归时用右值（比如cur + '.'），不改变原cur的值；若cur是vector，则先push入cur，调用完递归之后在cur.pop_back

有序+范围确定+时间复杂度是logN

题目：求n的平方根、截断木头...
思路：二分搜索

在矩阵中搜索路径/面积等

思路1：dfs
思路2：动态规划

删除重复元素

题目：lc82（链表）；lc83（链表）；lc26（数组）
思路1：从前往后遍历，用start记录首个重复元素，用cur记录遍历到的位置，用第一个不重复的元素覆盖start或start+1即可
思路2：递归

大数相加

题目：lc445（链表）；lc415（字符串）
思路：从后往前相加，不要忘了最后incre不等于0时要添加最高位

子串/子数组

题目：lc3（字符串）；lc209（数组）
思路1：动态规划
思路2：双指针，左右指针都从最左边开始，只会向右移动、不会回退；左、右指针移动要从当前结果中去除、增加元素
题目：lc560（数组）
思路：用累加和数组之差来求子数组的和
题目：lc718（数组-子数组）；lc1143（数组-子序列）
思路：动态规划，要做padding；若为子数组：dp表示以某个位置结尾的子数组/串的性质；若为子序列：dp表示某个位置之前的子序列的性质

求满足某条件的子数组的起点、终点、长度

题目：lc739（数组）
思路：把在数组中的位置而不是元素的值放入栈中

注意事项

总提醒

看到有序就要想到二分搜索
只要遇到字符串的子序列或配准问题首先考虑动态规划DP，只要遇到需要求出所有可能情况首先考虑用递归
返回空二维vector时不要用{{}}！这样返回的是[[]]而不是[]！(见lc103的第一次提交)
最开始的返回条件可以最后写，在写函数体的时候考虑只有一个元素（比如left=right）的情况就知道返回条件是什么了
想不出思路时：可以用dp吗？可以用递归吗？可以用双指针吗？可以用栈/队列吗？可以先排序吗？可以用二分吗？
求中位数的小trick：分别找第 (n+1) / 2 个，和 (n+2) / 2 个，然后求其平均值即可，这对奇偶数均适用
凡是能用 dp 解的题，一般也有用记忆数组的递归解法

往递归函数中传要处理的范围

题目：lc108（二叉树）
注意：通过数组大小为1的情况考虑：
1. 是if(left > right)还是(left >= right) return
2. left和right可能的越界情况，return

非法访问

只要有p->next，一定要保证p不为空
栈和队列一定要先判断是否为空才能取top/front
形如 while(i < n && v[i]) 的遍历一定要记得 i < n 这个条件
用substr时要先判断字符串有没有那么长

链表处理

若对链表中的某一段进行处理，且处理后需要把这一段接回原链表：一定要用last记录被处理的那段的最后一个节点，并把它接回原链表
判断环形链表/求入口时，slow = head->next（注意不是slow = head！）、fast = head->next->next

一些cpp常用接口

all

std::advance(it, index); // 让it向后移动index个位置
^：异或
比较

auto cmp = [](vector<int>& v1, vector<int>& v2) {
          if (v1[0] == v2[0]) return v1[1] < v2[1];
          else return v1[0] > v2[0];
      };
sort(people.begin(), people.end(), cmp);

stack/queue
- queue.back/front/pop/push
- stack.top/pop/push
- pop返回空
vector
- v.erase(v.begin() + j)
- v.erase(iter1, iter2); //删除[iter1,iter2)区间
- v.insert(v.begin() + i, tmp)
- v.insert(iter, n, x); //把n个x插入到iter前
- v.insert(iter, b.iter1, b.iter2); //把b的[iter1,iter2)区间插入到iter前
- v.back()
- v.front()
- v.pop_back()
- v.clear()
- swap(v[i], v[j]);
- v.assign(b.iter1, b.iter2); //先删除a中所有元素，把b的[iter1,iter2)区间插入
- reverse(v.iter1, v.iter2); //翻转[iter1,iter2)区间
- sort(v.iter1, v.iter2, [](int x, int y) {return x<y;}); //将[iter1,iter2)区间升序排列
string
- vec转str：str1.assign(Vec.begin(), Vec.end());
- str转vec：Vec.assign(Str.begin(), Str.end());
- int转str：to_string(n)
- str转int：stoi(str)
- s.substr(i, len)
- s.substr(i) // 从i到最后
- s.pop_back()
- s.push_back(c)
- s.back()
- s.erase(iter)
- s.resize(n)
set
- set.insert(n)
- s.insert(iter1, iter2)
- set转vector：vector<string>(st.begin(), st.end());
- set.erase(n)
- set.erase(iter)
- s.erase(iter1,iter2)
- set.count(n)
- set.find(n)
list
- l1.splice(l1.begin(), l2); // 把l2所有元素插到l1.begin前
- l1.splice(l1.begin(), l2, iter); // 把l2的iter插到l1.begin前
- l1.splice(l1.begin(), l2, iter1, iter2); // 把l2的[iter1,iter2)插到l1.begin前
- l.push_front
- l.push_back
- l.pop_back()
- l.pop_front()
- l.erase(iter)
- l.erase(iter1, iter2);
- l.insert(iter, x);
- l1.insert(iter, l2.iter1, l2.iter2);
- l.back()
- l.front()
- l.reverse()
- l.sort()
map
- map.erase(key)
- map.erase(iter)
- map.count(key)
- m.find(key)
- 注意：for (auto x : map)得到的x不是指针，用x.key而不是x->key
堆
- top/pop/push
- priority_queue<int> p; //max heap
- priority_queue<int, vector<int>, less<int>> p; //max heap
- priority_queue<int, vector<int>, greater<int>> p; //min heap
- priority_queue<int> p(begin(a), end(a)); //a是一个vector
```
auto cmp = [](ListNode*& a, ListNode*& b) {
   return a->val > b->val;
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)>  q(cmp);
```

抱佛脚-刷题系列之思路&提示

抱佛脚-刷题系列之思路&提示

常见思路

是否有路径，其累加和为目标值

求全排列

要求返回结果集

有序+范围确定+时间复杂度是logN

在矩阵中搜索路径/面积等

删除重复元素

大数相加

子串/子数组

求满足某条件的子数组的起点、终点、长度

注意事项

总提醒

往递归函数中传要处理的范围

非法访问

链表处理

一些cpp常用接口