第一章基础算法（一）

发表于2024-11-02|更新于2024-11-02|cshsuwindowDIY算法和数学AcWing算法基础课

|浏览量:

z

文章作者: hsuwindow

文章链接: http://hsuwindow.vip/cshsuwindowDIY/%E7%AE%97%E6%B3%95%E5%92%8C%E6%95%B0%E5%AD%A6/AcWing/%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E8%AF%BE/AcWing%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E8%AF%BE06/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 hsuwindowBlogs！

相关推荐

第一章基础算法（一）

快速排序快速排序的主要思想是基于分治 ==确定分界点==:q[l], q[r], q[(l + r )/ 2], q[随机] ==调整区间==: 把整个区间通过x的值划分成两部分,这两部分的长度不一定相等,使得第一个区间里面的所有数都<=x,第二个区间里面的所有数都>=x.注意x不一定在两个区间的交界处.(如果和x相等的话,可能在x左边,也可能在x右边,所以前面的表述都是<=和>=) ==递归处理左,右两段==.只要左边排好顺序,右边排好顺序,那么左右两边拼到一块形成的整个就是拍好序了.(因为左边的最大值是<=右边的最小值) 2.调整区间是最难的地方,有很多种实现方法. 方法一开两个额外的数组a[] 和 b[] 扫描q[l —-...

第一章基础算法（二）

高精度高精度的几种情况两个大整数相乘A * B或者相除A / B考的用到的不是很多,就不讲了 . ①大整数存储大整数在C++里面或者在C里面是如何存下来的.其实是把大整数的每一位存到数组里面去.存的话有一个问题,是高位在前还是低位在前(存在数组里面) 考虑到两个整数相加可能会有进位,这个时候我们把进位放到数组的末尾就是最方便的;如果想在数组的开头补上一个数,就要把整个数组往后移动一位,这是非常麻烦的. 那么我们就决定数组下标是零的元素存储大整数的个位,数组下标是一的元素存储大整数的十位,以此类推. 一句话总结:==就是数组从零开始往后依次存储大整数的从低到高位== ②大整数计算就是模拟小学的加法,Ai + Bi + 进位 mod 10 pS:a <= 10 和a的位数<= 10...

第一章基础算法（三）

双指针算法第一类,两个指针分别指向两个序列(归并排序) 第二类,两个指针指向一个序列(快速排序的划分的过程) 基本上双指针算法的通用模板 12345for(i = 0, j = 0; i < n; i++){//i整个扫描一遍 while (j < i && check(i, j))//每次i更新完之后,我们要更新我们的j j ++; //根据意义do something} 虽然循环长成这个样子,看上去是两重循环,但是每一个指针在所有循环里面总共的移动次数是不超过n的,两个指针的总共移动次数就不超过2 * n ==双指针算法最核心的性质就是可以将下面的朴素算法优化到O(n).我们运用了某些性质, 本来要枚举O(n * n)种情况,现在只需要枚举O(n)种情况== 核心思想: 12for (int i = 0; i < n; i ++) for (int j = 0; j < n; j ++) 时间复杂度是O(n *...

第二章数据结构（一）

这一和二都是以数组模拟为主.因为用数组模拟效率高, 链表与邻接表(lin邻) 栈和队列 kmp ①单链表:单链表最大的用途是用来写邻接表.邻接表最大的两个用途是来存储图和树. ②双链表:优化某些题目单链表单链表用数组模拟的情况如图所示用数组模拟链表,被称为静态链表不要害怕自己听不懂,听不懂就背嘛,无所谓的. 刚刚自己拿笔和纸花了画图,写了写可能的代码,结果就很清晰,一点疑问都没有.而且还总结出来一个东西,就是对于指针之间的相互赋值,我一开始总是觉得理解的不够顺畅,现在我明白了. 将指针a赋值给指针b如b = a;其实就是让==b指向 a指向的地方== 通过这段思考,我自己写出了和y总一样的代码,同时可以看到y总一直在说话,所以我也要一直在说话.而且y总也是在不停重复让指针b指向指针a指向的地方就是写成 b =...

第二章数据结构（二）

z 💡 有关AcWing算法基础课笔记的问题，欢迎您在底部评论区留言，一起交流~