近期正在观看和学习第四期左程云牛客算法视频，记录学习过程。
（持续更新）
第一课～
讲解时间复杂度，衡量算法的标准之一。
讲解了排序算法，首先是比较类型的排序算法。
1.冒泡排序
2.选择排序
选择最大/最小，交换到已排序的后面一个为止。
3.插入排序
当前最大/最小与已排序的比较，插入到第一个符合条件为止。
4.归并排序（小和问题，逆序对问题）
5.快速排序（通过荷兰国旗问题引入）
6.堆排序（中位数问题）
堆，完全二叉树的逻辑结构，可以用数组模拟其建立过程。
首先建立堆，之后调整堆。
总结:4，5，6的排序算法重要的前提下，其思想会用到之后很多问题。
非交换排序
1.桶排序（桶的思想）
2.计数排序
3.基数排序（未讲）
第二课 ～
栈/队列
首先是数组模拟队列/栈的建立（通过引入当前数组的size变量，解耦队列两个指针的关系）
队列实现栈/栈实现队列问题
通过两个队列/两个栈模拟栈/队列。
判断是否为回文字符串（利用栈结构）
猫狗队列（新建时间戳封装）
二维数组
回字打印，旋转数组，之字打印，有序二维数组找数。
链表
反转单向链表/双向链表
1.单向链表反转（三种方法）
其中一种的模板
判断cur.next不为空
循环
tmp＝cur.next
cur.next=pre
pre=cur
cur=tmp
2.链表结构判断是否为回文（快慢指针）
3.判断两个单向链表是否相交
首先判断是否为有环链表，hashset方法或快慢指针方法
分三种情况，无环单链表，有环单链表，一个有环一个无环。
4.拷贝特殊结构的链表（hashmap/后续嵌入结点）
第三课～
树结构
1.二叉树的前序，中序，后序遍历（递归版本）
非递归版本：
前序，需要依赖于一个栈结构，打印栈顶，右子树入栈后，左子树入栈。
curr = head
stack.push(curr)
while(!stack.isempyt()){
curr = stack.pop()
print curr.value
if curr.right! = null
stack.push(curr.right())
if curr.left ! = null
stack.push(curr.left())
}
中序，首先让左子树入栈，之后为左子树为空后，弹出当前，打印，右子树入栈。循环（栈空/结点空）
curr = head()
while(curr!=null||!stack.isempty()){
if curr!=null:
stack.push(curr)
curr = curr.left()
else:
curr = stack.pop()
print(curr)
curr = curr.right()
}
后序，依赖于两个栈实现，首先左子树入栈，之后右子树入栈，弹出栈顶，入第二个栈。
curr = head
stack.push(curr)
while(!stack.isempty()){
curr = stack.pop()
stack2.push(curr)
curr.left!=null
stack.push(curr.left)
curr.right!=null
stack.push(curr.righr)
}
2.二叉树的前驱和后继（中序遍历的结果）
前驱：
if curr.right!=null:
ger_curr_left_node(curr.right)
else:
parent = curr.parent
while parent.left != curr
curr = parnet
parent = curr.parent
后继：
3.二叉树的序列化与反序列化
4.判断二叉树是否为平衡二叉树，搜索二叉树，完全二叉树
判断是否为平衡二叉树（二叉树递归）
struct{
node node;
bool isB;
int h;
}
def process(head)
if node == null:
return struct(true,0)
left = process(node.left())
if(！left.isb) return struct(false,0)
right = process(node.right())
if(！right .isb) return struct(false,0)
return struct(true,max(left.h,right.h)+1)
判断是否为搜索二叉树，根据搜索二叉树的特点，中序遍历后为升序。
curr = head
while(curr!=null | !stack.empty)
if curr !=null:
stack.push(curr)
curr = curr.left()
else
curr = stack.pop()
比较节点的关系
curr = curr.right()
判断是否为完全二叉树（递归）
完全二叉树的特点,采用层次遍历
如果有右节点，无左边返回false
left = false
queue.push(head)
while(queue!=empyt)
head = queue.pop()
l = head.left
r = head.right
if((left==true)&(l!=null|r!=null|)){
return false;
}
if(r!=null,left==null){
return false
}
if l!=null
queue.push(l)
if r!=null
queue.push(r)
else:
left = true
计算完全二叉树的结点个数
遍历左边到最后，计算最大深度
遍历右边到最后，计算左边深度
比较左边深度和左边深度
if l＝h
return 1
if 左边等于左边
左边深度＋递归（node.right，l＋1，h）
else
右边深度＋递归（node.left,r＋1，h）
第四课～
哈希函数，哈希表
布隆过滤器
一致性哈希
前缀树
第五课～
递归与动态规划
第六课~
KMP：两个字符串比对，长字符串是否含有短字符串
1.next数组构建
两个变量，i=2，j=0
遍历短字符串长度求得next数组
if str[i-1] = str[0]:
next[i++] = ++j
else if j > 0
j = next[j]
else
next[i++] = 0
2.利用next数组加速匹配过程
遍历长短字符串的长度
if str1[i1] == str2[i2]
i1++
i2++
else if next[i2]!=-1
i2 = next[i2]
else
i1++
If i2==str2.length
return true
else
return false
3.manacher算法
4.BFPRT
5.双端队列
6.单调栈
7.搜索树
