ACWing——算法根本课

置顶思考：
算法的本质是什么样的思想？
这种思想可以解决哪类问题？
有没有其他的解决思绪？
关注数值范围，思考可不可以针对性解决问题？

目次

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方

1. const int N=1e6+10;
2. int q[N];
3. void quickSort(int q[],int low,int high){
4.         if(low>=high)return;
5.         int i=low-1;
6.         int j=high+1;
7.         int temp=q[low+high>>1];
8.        
9.         while(i<j){
10.                 do i++;while(temp>q[i]);
11.                 do j--;while(temp<q[j]);
12.                 if(i<j) swap(q[i],q[j]);
13.         }
14.         quickSort(q,low,j);
15.         quickSort(q,j+1,high);
17. }

复制代码

787. 归并排序
妥妥nlogn

1. const int N = 1e6+10;
2. int q[N];
3. int temp[N];
5. void mergeSort(int q[],int low,int high){
6.     if(low>=high) return;
7.     int mid=low+high>>1;
8.     int k=0;
9.     int i=low;
10.     int j=mid+1;
11.    
12.     mergeSort(q,low,mid);
13.     mergeSort(q,mid+1,high);
14.    
15.     while(i<=mid && j<=high) temp[k++]=q[i]<=q[j]?q[i++]:q[j++];
16.     while(i<=mid) temp[k++]=q[i++];
17.     while(j<=high) temp[k++]=q[j++];
18.    
19.     for (i=low,j=0; i <= high; i ++,j++ ) q[i]=temp[j];       
20. }

复制代码

788. 逆序对的数量(归并)
归并子题
注意范围超限，要使用long long
从两个元素起，计算逆序对数，子数组排序，外部的相对位置关系并没有改变
二分法

剪枝思想，缩小遍历范围，以低落时间复杂度
有单调性的题目肯定可以二分法低落时间复杂度
无单调性偶然也可以二分
二分问题的关键是边界问题，需要考虑边界范围接纳两套模板
二分问题无非以下两类：
左边界问题：找满足某个条件的第一个数——找大于即是某个数的第一个位置——r=mid;l=mid+1;
右边界问题：找满足某个条件的最后一个数——找小于即是某个数的最后一个位置——l=mid;r=mid-1;

1. //查找左边界 SearchLeft 简写SL
2. int SL(int l, int r)
3. {
4.     while (l < r)
5.     {
6.         int mid = l + r >> 1;
7.         if (check(mid)) r = mid; //找左边界，r就要等于mid
8.         else l = mid + 1;
9.     }   
10.     return l;
11. }
13. //查找右边界 记忆方面：有加必右减（有+1，r就要mid-1）
14. int SR(int l, int r)
15. {
16.     while (l < r)
17.     {                  
18.         int mid = l + r + 1 >> 1; //需要+1 防止死循环
19.         if (check(mid)) l = mid;//找右边界，l要等于mid
20.         else r = mid - 1;
21.     }
22.     return r;
23. }

复制代码

789. 数的范围（二分）
790. 数的三次方根
逆向头脑，将求根的问题转化为，求幂的问题
printf(“%lf”,flo)默认输出六位小数
当你要求六位精度时，计算时要增加两位，至少求八位精度
高精度整数问题

加法：位数1e6
减法：位数1e6
乘法：位数1e6，数值1e9
除法
python和java自带高精度函数
c++的vector作为数组存储有size属性，很方便
‘9’-‘0’=9(数字)
适当添加引用&，可以防止整个数组的复制，加速速率
思想：把数的每一位存入数组，从低位到高位存，个位放a[0]的位置

注意学习Vector

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。