算法刻意练习之字典树/并查集

ゝ一纸荒年。 2022-12-21 06:09 171阅读 0赞

## 1 字典树 ##

### 1.1 特点 ###

**又叫Trie树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构**

### 1.2 对比树、二叉搜索树 ###

（1）树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center]  
（2）二叉搜索树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 1]

### 1.3 基本结构 ###

（1）基本结构  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 2]  
（2）真实的字典树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 3]  
上图是一棵Trie树，表示了**关键字集合\{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”\}** 。从上图可以归纳出Trie树的基本性质。

### 1.4 基本性质 ###

![在这里插入图片描述][20201115112140728.png_pic_center]

### 1.5 核心思想![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 4] ###

### 1.6 场景 ###

（1）搜索前缀匹配、字符串检索、词频统计、字符串排序等  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 5]

### 1.8 结点的内部实现 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 6]

### 1.9 典型案例 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 7]

LogUtils.d(TAG, "208. 实现 Trie (前缀树) + 插入：${trie.insert("apple")}")
    LogUtils.d(TAG, "208. 实现 Trie (前缀树) + 查找：${trie.search("apple")}")

class Trie {
    
        private var root: TrieNode = TrieNode()
    
        /**
         * 插入
         *
         * 时间复杂度：O(m)，其中m为键长。在算法的每次迭代中，我们要么检查要么创建一个节点，直到到达键尾。只需要m次操作。
         * 空间复杂度：O(m)。最坏的情况下，新插入的键和Trie树中已有的键没有公共前缀。此时需要添加m个结点，使用O(m)空间。
         *
         * @param word
         */
        fun insert(word: String) {
            var node: TrieNode? = root
            for (c in word) {
                if (!node!!.containsKey(c)) {
                    node.put(c, TrieNode())
                }
                node = node.get(c)
            }
            node!!.isEnd = true
        }
    
        /**
         * 在trie中搜索前缀或整个键，返回搜索结束的节点
         *
         * 时间复杂度 : O(m)。算法的每一步均搜索下一个键字符，最坏的情况下需要m次操作。
         * 空间复杂度 : O(1)。
         *
         * @param word
         * @return
         */
        private fun searchPrefix(word: String): TrieNode? {
            var node: TrieNode? = root
            for (c in word) {
                node = if (node!!.containsKey(c)) { node.get(c) } else { return null }
            }
            return node
        }
    
        /**
         * 返回单词是否在单词中
         *
         * @param word
         * @return
         */
        fun search(word: String): Boolean {
            val node = searchPrefix(word)
            return node != null && node.isEnd
        }
    
        /**
         * 返回trie中是否有以给定前缀开头的任何单词
         *
         * 时间复杂度 : O(m)
         * 空间复杂度 : O(1)
         *
         * @param prefix
         * @return
         */
        fun startsWith(prefix: String?): Boolean {
            val node = searchPrefix(prefix!!)
            return node != null
        }
    
       class TrieNode {
            var array = arrayOfNulls<TrieNode>(26)
            var isEnd = false
    
            fun containsKey(ch: Char): Boolean {
                return array[ch - 'a'] != null
            }
    
            fun get(ch: Char): TrieNode? {
                return array[ch - 'a']
            }
    
            fun put(ch: Char, node: TrieNode?) {
                array[ch - 'a'] = node
            }
        }
    }

## 2 并查集 ##

### 1.1 场景 ###

![在这里插入图片描述][20201115143710168.png_pic_center]

### 1.2 基本操作 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 8]

### 1.3 步骤 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 11]

### 1.4 模板 ###

class UnionFind(n: Int) {
    
        private var count = 0
        private var parent: IntArray
    
        /**
         * 用 parent 数组记录每个节点的父节点，相当于指向父节点的指针，所以 parent 数组内实际存储着一个森林（若干棵多叉树）
         * 构造函数，n 为图的节点总数
         * @param x
         * @return
         */
        init {
            // 一开始互不连通
            count = n
            parent = IntArray(n)
            // 父节点指针初始指向自己
            for (i in 0 until n) parent[i] = i
        }
    
        /**
         * 返回某个节点 x 的根节点
         * @param x
         * @return
         */
        fun find(x: Int): Int {
            // 根节点的 parent[x] == x
            var x = x
            while (parent[x] != x) {
                // 进行路径压缩
                parent[x] = parent[parent[x]]
                x = parent[x]
            }
            return x
        }
    
        /**
         * 合并
         * @param p
         * @param q
         */
        fun union(p: Int, q: Int) {
            val rootP = find(p)
            val rootQ = find(q)
            if (rootP == rootQ) return
    
            // 将两棵树合并为一棵
            parent[rootP] = rootQ
            count--
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/c0b002f8bcc84a9395847104e4d3e1db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/5af9953d68aa405a83a469a1e6d537a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/1268b5deb31345f08b9357f62c82ce94.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/465477cb69234688a47f1e67f5550edf.png
[20201115112140728.png_pic_center]: https://img-blog.csdnimg.cn/20201115112140728.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201115112412734.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20201115111006880.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20201115120116783.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20201115113932914.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4=,size_16,color_FFFFFF,t_70#pic_center
[20201115143710168.png_pic_center]: https://img-blog.csdnimg.cn/20201115143710168.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20201115143747672.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20201115143811525.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/20201115143820414.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/202011151438318.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4=,size_16,color_FFFFFF,t_70#pic_center