算法专题|并查集
并查集(Union-find Data Structure)是一种树型的数据结构。它的特点是由子结点找到父亲结点,用于处理一些不交集(Disjoint Sets)的合并及查询问题。
……记录所学所思所想,专注于Go语言、软件架构
并查集(Union-find Data Structure)是一种树型的数据结构。它的特点是由子结点找到父亲结点,用于处理一些不交集(Disjoint Sets)的合并及查询问题。
……前缀和可以简单理解为「数列的前 n 项的和」,是一种重要的预处理方式,能大大降低查询的时间复杂度。
……图相关的算法练习,需要掌握图的基本数据结构,图的连通性,图的遍历,最短路径,最小生成树等问题。
……贪心算法没有固定的模板,基本思路是找到问题的一个切入点,虽然证明这个解法是最优的。
……滑动窗口,这个算法思路非常简单,就是维护一个窗口,不断滑动,然后更新答案。
……双指针是一种简单而又灵活的技巧和思想,单独使用可以轻松解决一些特定问题,和其他算法结合也能发挥多样的用处。
……二分查找 (Binary Search) 也称折半查找,它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
……回溯 (backtracking) 是暴力搜索的方法之一。
……动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程。总结有以下特征和解题步骤:
……