边界条件
- $10^{9}$需要额外注意，通常会出现int溢出的问题
- 256MB内存大约可以存储 8000 * 8000 的32位数据
- 如果内存允许，有时可以使用数组替代unordered_map，因为unordered_map需要编写额外的哈希函数来计算pair等复杂类型键的哈希值
- 回溯问题通常可以使用空间换时间，记录各个分支的解，减少重复计算
二叉树
完全二叉树
数组表示的完全二叉树中，第i个节点与其左右子节点的关系为（i从0开始）：
$$
\begin{align}
& i_{left}=2i + 1 \\
& i_{right} = 2i + 2
\end{align}
$$
二叉搜索树
二叉搜索树有一个很好的性质，即其中序遍历的结果严格升序。
二叉树遍历
前序、后序、中序遍历可以用栈来进行实现，且前中序的迭代代码类似，如下：
vector<int> traversal(TreeNode* root) {
stack<TreeNode*> stk;
vector<int> res;
while (root || !stk.empty()) {
while (root) {
stk.push(root);
// 前序：res.push_back(root->val);
root = root->left;
}
root = stk.top();
stk.pop();
// 中序：res.push_back(root->val);
root = root->right;
}
return res;
}而后序的代码较为复杂，代码如下（修改自本文提供的代码）：
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
vector<int> res;
TreeNode* cur = root;
TreeNode* pre = nullptr;//用来记录上一个已经结点
while(!s.empty() || cur){
while(cur){
s.push(cur);
cur = cur->left;
}
cur = s.top();
//下面的判断是说明，右子树当前的cur的右子树已经遍历完了，可以进行遍历当前的结点了
if(!cur->right || cur->right==pre){
res.push_back(cur->val);
s.pop();
pre = cur;
cur = nullptr;//这一步很重要，这一步能够使得在遍历完当前的cur以及其左右子树之后能够进一步往树的上方回溯
}else{
cur = cur->right;
}
}
return res;
}数组
子序列
异位词的判别方法
通常将字符串转化为统计各个字母出现次数的array，比较时只需要比较两个array是否相等。（$O(n)$）
或者利用排序的方式，将字符串进行排序后比较。（$O(nlongn)$）
更进一步的，还可以对上述两者求散列值进一步的加速相关操作。
回文串的处理技巧
破坏偶数回文串只需要搜索相邻两个相同的字符，删去其中一个即可。
链表
删除/插入
由于删除和插入都有可能改变头指针，因此通常会创建一个假头，将真头作为其后继，从而便于统一处理。
环
通常利用快慢指针的方式对环进行相关处理。
排序
常见排序汇总表
| 名称 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 稳定性 | 说明 |
| 冒泡 | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | T | 有序情况下最好，倒序情况下最坏。 |
| 插入 | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | T | 有序情况下最好，倒序情况下最坏。 适用于数据量少、基本有序的情况。 |
| 选择 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | F | 虽然时间复杂度高，但是交换次数少。因此比冒泡效率要高。 找最值进行交换导致不稳定。 |
| 希尔 | $O(n^{1.3~2})$ | $O(n^{1.3~2})$ | $O(n^{1.3~2})$ | $O(1)$ | F | 缩小增量插入排序。 增量可以自行选择，会对时间复杂度产生影响。 跨元素交换导致不稳定。 |
| 堆 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(1)$ | F | 建堆$O(n)$，排序$O(nlong)$。 相对于快排的交换次数多、访存不连续 |
| 归并 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(n)$ | T | 每次都先放左侧的数，即可保证稳定。 |
| 快速 | $O(nlogn)$ | $O(n^2)$ | $O(nlogn)$ | $O(logn ~ n)$ | F | 正序、倒序情况最坏（时间空间都是）。 可以利用栈实现。 中心点的选取非常重要，可以利用三数取中、随机选取的方法进行优化。 也可以在元素少于一定数值时做插入排序。 还可以利用三向切分的方法，跳过相同元素。 |
| 桶 | $O(n)$ | $O(n^2)$ | $O(n)$ | $O(n)$ | T | 桶内使用链表插入排序 |
快速排序
快速排序的不同实现方法
本科上课且个人一直觉得比较好理解的是空穴法，即下述这种实现方法：
int quickSelect(vector<int>& nums, int i, int j, int k) {
int left = i, right = j;
int pivot = nums[right];
while (left < right) {
while (left < right && nums[left] >= pivot) left++;
if (left < right) nums[right] = nums[left];
while (left < right && nums[right] <= pivot) right--;
if (left < right) nums[left] = nums[right];
}
nums[left] = pivot;
if (left == k) {
return nums[left];
}
else if (left < k) {
return quickSelect(nums, left + 1, j, k);
}
else {
return quickSelect(nums, i, left - 1, k);
}
}这种方法存在一个问题，即如果数组中存在大量的相同元素，例如考虑一个全为0的数列，那么在右移左指针时，就会直接将左指针移动到最右边，使得快排的时间复杂度退化到$O(n^2)$。
相反的，如果使用交换法，就可以解决上述情况：
int quickSelect(vector<int>& nums, int i, int j, int k) {
if (i == j) return nums[k];
int pivot = nums[i];
int left = i - 1, right = j + 1;
while (left < right) {
do left++; while(nums[left] > pivot);
do right--; while (nums[right] < pivot);
if (left < right) swap(nums[left], nums[right]);
}
if (right >= k) {
return quickSelect(nums, i, right, k);
}
else {
return quickSelect(nums, right + 1, j, k);
}
}
int findKthLargest(vector<int>& nums, int k) {
return quickSelect(nums, 0, nums.size() - 1, k - 1);
}可以看到，如果使用这种实现方式，全零的数列最终的中心点位置将会位于数组中央，使得时间复杂度保持在$O(nlogn)$。
不过需要注意，这种方法无法得到每次划分时中心点的最终位置，该方法只能保证区间$[i, right]$和区间$[right + 1, j]$中的元素分别小于等于/大于等于中心点。只有在i==j时，中心点位置才能确定。
参考：
[1] 快速排序 Wiki
图论
图遍历时已访问的记录位置
在进行图遍历时，应当注意，更新已访问数组应该发生在入栈/队时，而不是出栈/队，后者虽然不会导致死循环，但是会导致一个节点被多次访问。
数学
最大公约数和最小公倍数满足：$ab=lcm(a.b)gcm(a,b)$
约瑟夫环的递推公式：$x^\prime = (x + k) % n$，其中$k = m % n$。该递归式把子问题的获胜者编号映射到上层。
