第七周算法总结

1.字典集

手动实现trie类

• search方法
• insert 方法

2.并查集

disjoint set

• 判断是不是朋友 （朋友圈）
• 判断你是不是互相包含的关系
• 多练dfs 岛屿数量

3. 剪枝

• 括号问题（剪枝解决，DP解决）
• 爬楼梯
• 零钱兑换（未完成）
• 八皇后问题 （未完成）

以上多写几遍

• 数独问题（未完成）
  1. 判断棋盘是不是合法
  2. 填写数独
  3. 启发式搜索，优先级搜索，A*搜索 （数独中少的格子先填，速度更快）

4. 双向DFS

概念

在dfs基础上，增加了从尾节点的查找逻辑，比原有效率高
例子：单词接龙

5.启发式搜索（A*搜索）

概念

在深度优先的基础上，告知搜索方向

曼哈顿距离：横坐标差+纵坐标差 就会找到离目标最近的点
汉明距离：什么意思？
估价函数：用于指引搜索结果，更快的找到答案

6.AVL树、旋转树

概念

• 平衡二叉搜索树
• 每个节点存平衡因子{-1,0,1},超出就需要旋转
• 四种旋转操作

不足的地方：

• 额外的存储信息
• 调整频繁

平衡因子怎么得来？
为什么需要旋转二叉树？

旋转逻辑

1. 左树 ：右旋
2. 右树 ：左旋
3. 左右树 ：左右旋（从下往上）
4. 右左树 ：右左旋（从下往上）

7.红黑树

概念

• 根节点黑色
• 每个叶子节点是黑色
• 不能有相邻的两个红色节点
• 从任一节点到其每个叶子所有路劲都包含相同数目的黑色节点

特征

• 高度差小于两倍
• 查找性能 nlogn

应用场景

• Db 一般用AVL 因为读多写少
• 一般的字典 map 都是用红黑树实现，读和写基本是一半一半 的