左神算法基础课学习笔记

时间复杂度：

​

异或运算 不同为1 相同为0

取一个数最右侧的1 eor & (~eor + 1)

image-20220308211917740

image-20220308211953725

mid=L + (R-L)/2 取中点 不会溢出

mid=L + ((R-L) >> 1)

image-20220312130559319

image-20220312165213887

image-20220314092102690

快排1 <=num >num

快排2 <num =num >num

快排3 随机取num <num =num >num

image-20220314150202017

手写堆

堆排序

image-20220314153756940

image-20220314122621445

基于比较的排序，只和俩个数比较大小有关

不基于比较的排序 要根据数据具体状况进行定制

计数排序

基数排序 低位到高位依次排序 N进制需准备N个桶。设最高M位，则出入桶的次数为M

image-20220314155032440

image-20220314172958431

快速排序用的最多

image-20220314173254103

image-20220314173354701

利用各算法优势排序 为综合排序

HashSet

HashMap

image-20220315120344022

image-20220315121215420

HashSet HashMap

TreeSet TreeMap

中等难度算法提不会涉及原理

image-20220315121412356

image-20220315121616567

image-20220315121627823

image-20220315121722698

快慢指针，控制慢指针指向的位置

慢指针指向：

1. 奇数 中点；偶数 靠后

fast !=null && fast.next!=null

2. 奇数 中点；偶数 靠前

 fast.next !=null && fast.next.next!=null

3. 奇数 中点靠后；偶数 靠后

slow = head.next;//慢指针先走一步 
fast.next !=null && fast.next.next!=null

4. 奇数 中点考前；偶数 靠前

fast = head.next //快指针先走一步 
fast.next !=null && fast.next.next!=null

5. 奇数 中点考前；偶数 靠前再靠前

fast = head.next.next;//快指针先走两步 
fast.next !=null && fast.next.next!=null

image-20220315121919161

image-20220315122535838

image-20220315123118968

image-20220315123952701

找第一个入环节点：

1. 使用额外数据结构 set
1. 快慢指针。 快慢指针一定在环上相遇，之后快指针回到head,然后快慢指针都同时走一步，之后快慢指针相遇的位置即为第一个入环节点。

image-20220315181101569

递归序

非递归实现先序、中序、后序 ：

先序，后序

															1. 栈弹出
															1. 打印 处理
															1. 先压右，再压左
															1. 循环

中序：

​ 使用左边界分解整颗数

左头右[左头]

深度优先遍历是先序遍历

宽度优先遍历使用队列实现

image-20220315185702850

树型DP 【一个套路解决】

左右子树提供信息，动态处理。

image-20220315202152383

image-20220315203759234

image-20220315204459141

image-20220315205030708

image-20220316102119792

用最喜欢的图的表达方式，实现所有的算法

实际应用时 只需要完成图结构的转换即可。

image-20220316111552089

image-20220316112800142

依赖包的引入顺序

image-20220316113525239

image-20220316113536359

k算法 p算法 用来生成图的最小生成树

image-20220317105837717

====================================================================================================

image-20220317183328517

image-20220319210655844

image-20220319211325932

image-20220319213530316

image-20220319213555518

image-20220319213659918

image-20220319213727732

image-20220403090439199