强化2（Union Find, Trie, sweep line)

Union Find

1. 解决集合查询合并的数据结构，支持O（1） find O(1) union

2. 用hashmap

3. father 可以指向自己或者0，如果指向0, index需要从1开始， INDEX:1~n+1

4. 并查集1不能拆开，2是放射状结构的数，子都指向父亲

5. time complexity : worst o(n) 一条直线时候，best o(logn) by rank: https://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/

6. 需要计算block里个数时候，可以加个size和rank数组：Max Area of Island

7. 比较Unionfind,dfs能得到一个Group内具体的点。

8. 在并查集（Union-Find）算法中，rank 是一个优化手段，用于减少树的高度，从而加速查找（find）和合并（union）操作。rank 数组中每个元素的值表示集合树的近似高度（也可以理解为深度）。注意，这并不是严格的树高度，而是一个近似值。初始化时，每个集合（单个元素）都是一个独立的树，高度为1。

   作用：在进行 union 操作时，rank 用于决定如何合并两个集合的根节点：

   • 将 rank 较小的树挂载到 rank 较大的树上。这会保证合并后的树不会变得太高，从而保持树的平衡。

   • 如果两棵树的 rank 相同，则任选一棵作为新树的根，并将其 rank 增加 1，因为树的高度增加了。

self.rank = [1] * n

def union(self, p, q):
    rootP = self.find(p)
    rootQ = self.find(q)
    if rootP != rootQ:
        # Union by rank
        if self.rank[rootP] > self.rank[rootQ]:
            self.parent[rootQ] = rootP
        elif self.rank[rootP] < self.rank[rootQ]:
            self.parent[rootP] = rootQ
        else:
            self.parent[rootQ] = rootP
            self.rank[rootP] += 1

代码模板

public class UnionFind{
    private int[] father = null;
    //放射状，路径压缩
    public int find(int x){     
        if(father[x] == 0)          
            return x;     
        return father [x] = find(father[x]);//全部直接指向father，压缩路径，从列状到放射状 O（1）     

    }
//union合并key father之间合并，和子没关系
    public void union(int a, int b){     
        int root_a = find(a);     
        int root_b = find(b);     
        if(root_a != root_b){          
            father(root_a) = root_b;     
        }
    }
}

Connecting Graph 问题总结

并查集原生操作

• 查询两个元素是否在同一个集合内

• 合并两个元素所在的集合

并查集派生操作

• 查询某个元素所在集合的元素个数,加一个map: size=int[N],操作步骤与father map同步，每次合并更新当前Node的size：size[m]=size[m]+size[n]

• 查询当前集合的个数，加一个count=N, 每次合并都--

图的问题很可能是并查集

并查集可以用来判断数是否有环，如果2个端点已经在一个集合，则有环

Trie 字典树

from retrieve

一个字符对应一个node，查Node的孩子，char的index插入孩子相应的pos.树深就是单词的长度。

缺点：占内存

1.字典放入哈希表查询 2.字典建成Trie树（单词插入trie树）

Hash vs Trie

• 时间复杂度 o(1) o(1) 都对于一个字符串

• 空间复杂度Trie更好

通常用Hash 因为有库函数实现，trie要自己实现

Trie考点

• 一个一个字符串/字母遍历

• 需要节约空间

• 查找前缀

代码：

这是对单个word来说！！！！！！！Trie的insert和find都是3层代码，for里面也是3层。
1 先定点初始this或者新建起点，cur = this;
2 for loop里就是找pos往下走，从父到子的过程。find 和insert区别就是for loop里子空，一个新建一个返回.
3 最后返回结果不同。

sweep-line 扫描线

扫描问题思路

1. 事件以区间的形式存在

2. 区间两端代表事件开始和结束。拆成两个。

3. 需要排序

总结

数据结构题目

Union Find: 集合合并，查找元素在集合里面

Trie：一个字母一个字母查找，快速判断前缀

Sweep-line: 区间拆分

Other tips

java 栈空间 32M

(x,y)->id    
id = m*x+y 
-> 
x = id/m     
y = id%m (M是矩阵宽）