置顶思考：
算法的本质是什么样的思想？
这种思想可以解决哪类问题？
有没有其他的解决思路？
关注数值范围，思考可不可以针对性解决问题？
目录
https://leetcode.cn/circle/discuss/RvFUtj/
滑动窗口与双指针（定长/不定长/单序列/双序列/三指针）
二分算法（二分答案/最小化最大值/最大化最小值/第K小）
单调栈（基础/矩形面积/贡献法/最小字典序）
网格图（DFS/BFS/综合应用）
位运算（基础/性质/拆位/试填/恒等式/思维）
图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
链表、二叉树与一般树（前后指针/快慢指针/DFS/BFS/直径/LCA）
排序
785.快速排序
原地算法，不需要额外开辟空间
const int N = 1000010;可以写成 1e6+10；
c++中用scanf接受数据很快，不要用cin
Java中用buffer read，不要用scanner
基准元素取端点在某些数据增强的情况下会超时，建议取中点
平均nlogn,最差n方
const int N=1e6+10;
int q[N];
void quickSort(int q[],int low,int high){
if(low>=high)return;
int i=low-1;
int j=high+1;
int temp=q[low+high>>1];
while(i<j){
do i++;while(temp>q[i]);
do j--;while(temp<q[j]);
if(i<j) swap(q[i],q[j]);
}
quickSort(q,low,j);
quickSort(q,j+1,high);
}
787. 归并排序
妥妥nlogn
const int N = 1e6+10;
int q[N];
int temp[N];
void mergeSort(int q[],int low,int high){
if(low>=high) return;
int mid=low+high>>1;
int k=0;
int i=low;
int j=mid+1;
mergeSort(q,low,mid);
mergeSort(q,mid+1,high);
while(i<=mid && j<=high) temp[k++]=q[i]<=q[j]?q[i++]:q[j++];
while(i<=mid) temp[k++]=q[i++];
while(j<=high) temp[k++]=q[j++];
for (i=low,j=0; i <= high; i ++,j++ ) q[i]=temp[j];
}
788. 逆序对的数量(归并)
归并子题
注意范围超限，要使用long long
从两个元素起，计算逆序对数，子数组排序，外部的相对位置关系并没有改变
二分法
剪枝思想，缩小遍历范围，以降低时间复杂度
有单调性的题目一定可以二分法降低时间复杂度
无单调性有时也可以二分
二分问题的关键是边界问题，需要考虑边界范围采用两套模板
二分问题无非以下两类：
左边界问题：找满足某个条件的第一个数——找大于等于某个数的第一个位置——r=mid;l=mid+1;
右边界问题：找满足某个条件的最后一个数——找小于等于某个数的最后一个位置——l=mid;r=mid-1;
//查找左边界 SearchLeft 简写SL
int SL(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; //找左边界，r就要等于mid
else l = mid + 1;
}
return l;
}
//查找右边界 记忆方面：有加必右减（有+1，r就要mid-1）
int SR(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1; //需要+1 防止死循环
if (check(mid)) l = mid;//找右边界，l要等于mid
else r = mid - 1;
}
return r;
}
789. 数的范围（二分）
790. 数的三次方根
逆向思维，将求根的问题转化为，求幂的问题
printf(“%lf”,flo)默认输出六位小数
当你要求六位精度时，计算时要增加两位，至少求八位精度
高精度整数问题
加法：位数1e6
减法：位数1e6
乘法：位数1e6，数值1e9
除法
python和java自带高精度函数
c++的vector作为数组存储有size属性，很方便
‘9’-‘0’=9(数字)
适当添加引用&，可以防止整个数组的复制，加快速度
思想：把数的每一位存入数组，从低位到高位存，个位放a[0]的位置
注意学习Vector