ACWing——算法根本课
置顶思考：算法的本质是什么样的思想？
这种思想可以解决哪类问题？
有没有其他的解决思绪？
关注数值范围，思考可不可以针对性解决问题？
https://i-blog.csdnimg.cn/direct/ae82de4582c1448fa7b37583698d9cf5.png
目次
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;
void quickSort(int q[],int low,int high){
if(low>=high)return;
int i=low-1;
int j=high+1;
int temp=q;
while(i<j){
do i++;while(temp>q);
do j--;while(temp<q);
if(i<j) swap(q,q);
}
quickSort(q,low,j);
quickSort(q,j+1,high);
}
787. 归并排序
妥妥nlogn
const int N = 1e6+10;
int q;
int temp;
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=q<=q?q:q;
while(i<=mid) temp=q;
while(j<=high) temp=q;
for (i=low,j=0; i <= high; i ++,j++ ) q=temp;
}
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的位置
https://i-blog.csdnimg.cn/direct/e90e0c14400f476f8e9ddba1483d623b.png
注意学习Vector
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]