算法训练营 - 学习笔记 - 第八周

生了二胎之后，感觉最缺的就是时间。。。随着年龄的增长，扮演的角色越来越多，不断打怪、升级，人生而苦难，至死方已。坚持！

划重点

失败只有一种，那就是半途而废！

比别人多一点执着，你就会创造奇迹！

第 14 课 字典树(Trie)和并查集

Trie 树的基本实现和特性

树、二叉树：左、右子树

• 遍历：

• BFS：层次遍历

• DFS：前序（根左右）、中序（左根右）、后序（左右根）

• 二叉搜索树：左子树小于根节点，右子树大于根节点

• 查找效率更高

• 
  

高频题目：二叉树的层次遍历

字典（Trie） 树 - 基本结构

字典树，即 Trie 树，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎用于文本词频统计。

优点：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

基本性质

1. 节点本身不存完整单词；

2. 从根节点到某一节点，路径上经过的字符链接起来，为该节点对应的字符串；

3. 每个节点的所有子节点路径代表的字符都不相同。

核心思想

空间换时间

利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

Trie 树实战题目解析：单词搜索 2

1. word 遍历 -> board search O(N*m*m*4^k)

2. trie

3. all words -> Trie 构建起 prefix

4. board, DFS

并查集(Disjoint Set)的基本实现、特性和实战题目解析

关键要：记住、写熟

适用场景

1. 组团、配对问题

2. group or not?

基本操作

• makeSet(s): 建立一个新的并查集，其中包含 s 和单元素集合。

• unionSet(x, y)

• find(x)

查询、合并(UnionFind)

判断两辆元素是否在一个集合中

def init(p):  # for i = 0..n:p[i] = i;  p = [i for i in range(n)]  def union(self, p, i, j):  p1 = self.parent(p, i)  p2 = self.parent(p, j)  p[p1] = p2  def parent(self, p, i):  root = i  while p[root] != root:    root = p[root]  while p[i] != i: # 路径压缩    x = i; i = p[i]; p[x] = root  return root

实战题目解析

• Friend Circles 朋友圈

• M[i][j]: i 是 j 的朋友

• 类似于 Number of islands 算法，把连通的都打通。

第 15 课 红黑树和 AVL 树

AVL 树和红黑树的实现和特性

二叉树，二叉树遍历: Pre-Order/In-Order/Post-Order

二叉搜索树，非平衡二叉树，最坏情况下会退化成一个链表，查找时间复杂度为 O(n)

B+, B- 树, 2-3 树

AVL 树：

1. 平衡因子：在[-1, 0, 1] 之间，左右子树高度差

2. 保持平衡因子不超过 1

3. 通过旋转操作来进行平衡（四种）

4. 左旋

5. 右旋

6. 左右旋

7. 右左旋

带有子树的旋转

AVL 总结

1. 平衡二叉搜索树

2. 每个节点存 balance factor = {-1, 0, 1}

3. 四种旋转操作

不足：节点需要存储额外信息、且调整次数频繁

红黑树 Red-Black Tree（近似平衡二叉树）

红黑树是一种近似平衡的二叉搜索树(二叉搜索树）它能确保任何一个节点的左右子树的高度差小于两倍。

维护旋转频次降低。

• 每个节点要么是红色，要么是黑色

• 根节点是黑色

• 每个叶节点（NIL 节点，空结点）是黑色的。

• 不能右相邻接的两个红色节点

• 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点。

AVL vs Red-Black Tree

AVL: faster lookups, more strictly balanced

Red Black Tree: faster insertion and removal

Database: 读操作较多，AVL 树

Set, Map 实现: 红黑树

第 16 课 位运算

位运算基础及实战要点

• 位运算符

• 算数位移与逻辑移位

• 位运算的应用

计算机内部使用二进制来存储和表示

移位

• 左移： <<

• 右移： >>

位运算符

• 按位或: |

• 按位与: &

• 按位取反: ~

• 按位异或: ^

位运算实战题目解析

1. 位 1 的个数 —— 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）

2. for loop: 0 -> 32

3. %2, /2

4. &1, x = x >> 1

5. x = x&(x-1) 清零最低位的 1

6. while (x > 0) { count++; x = x&(x-1)}

7. Power of 2, 2 的幂

8. return n != 0 && n & (n -1) == 0

9. Reverse bits

10. N queens - 位运算，终极解法

11. 比特位计数